import java.util.Scanner;
public class BinaryTree {
private int info;
private BinaryTree left;
private BinaryTree right;
private int height = 1;
public BinaryTree()
{
left = null;
right = null;
}
public BinaryTree(int theInfo)
{
Scanner sc = new Scanner(System.in);
int intNum;
String s;
info = theInfo;
System.out.print("Does the node " + info + " have a left child (y or n)? ");
s = sc.next();
if (s.equals("y"))
{
System.out.print ("What value should go in the left child node? ");
intNum = sc.nextInt();
left = new BinaryTree(intNum);
}
System.out.print("Does the node " + info + " have a right child (y or n)? ");
s = sc.next();
if (s.equals("y"))
{
System.out.print ("What value should go in the right child node? ");
intNum = sc.nextInt();
right = new BinaryTree(intNum);
}
}
int heightLeft = 0;
int heightRight = 0;
public int getHeight()
{
int counterOld = 0;
int counter = 0;
if (left != null)
{
counter++;
if (counter > counterOld)
{
counterOld = counter;
}
counter += left.getHeight();
}
if (left == null)
{ System.out.println("counter is: " + counter + " and counterOld is: " + counterOld);
/*if (counter > counterOld)
{
counterOld = counter;
} */
counter = 0;
}
if (right != null)
{
counter++;
if (counter > counterOld)
{
counterOld = counter;
}
counter += right.getHeight();
}
if (right == null)
{ System.out.println("counter is" + counter + " and counterOld is: " + counterOld);
/*if (counter > counterOld)
{
counterOld = counter;
} */
counter = 0;
}
return counterOld;
}
}
import java.util.Scanner;
public class BinaryTester {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
BinaryTree myTree;
Scanner sc = new Scanner(System.in);
int intNum;
System.out.print("What value should go in the root? ");
intNum = sc.nextInt();
myTree = new BinaryTree(intNum);
System.out.println("Height is " + myTree.getHeight());
}
}
400
/
300
/
200
/
100
我使用树高函数计数器得到了混合结果。我想根据最低节点计算树的高度。例如,上面的树的高度应该为 3,根的计数为 0。我得到高度 1 的错误结果。如果我输入如下所示的树,我会得到正确的结果:
400
/ \
300 10
/ / \
100 4 5
/
3
这棵树的高度为 3,这正是我想要的。有人知道我如何调整我的代码以解释所有树吗?
使用树时,递归要容易得多。
public int getHeight(BinaryTree node){
if(node == null){
return 0;
}
int left = getHeight(node.left);
int right = getHeight(node.right);
return Math.max(left, right) + 1;
}
此方法给出一个基于 1 的高度。如果您想从零开始计数,则可以从中减一,例如
getHeight(tree) - 1
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)