0

这是 12 年级二叉树作业中的一道题。它需要一个 BTree 类的方法来返回树的高度。我假设树中有一个节点时高度为0，不确定，我今天会问我的老师。

但无论如何，这是我的代码，我不知道它有什么问题。

public int height(){
    if(root == null){
        return -1;
    }
    return height(root, 0, 0);
}
public int height(BNode branch, int depth, int ans){
    if(depth>ans){
        ans=depth;
    }
    if(branch.getLeft()!=null){
        depth+=1;
        return height(branch.getLeft(), depth, ans);
    }
    else if(branch.getRight()!=null){
        depth+=1;
        return height(branch.getRight(), depth, ans);
    }
    return ans;
}

这是测试类：

    BTree bTree = new BTree();
    bTree.add(50);
    bTree.add(60);
    bTree.add(40);
    bTree.add(35);
    bTree.add(55);
    bTree.add(45);
    bTree.add(51);
    bTree.display();
    System.out.println(bTree.height());

这棵树的高度应该为 3，但它正在返回：35 40 45 50 51 55 60 2

任何帮助将不胜感激，谢谢。

4

2 回答 2

2

你喜欢你的左节点而不是你的右节点。节点的高度应该是：

MAX(height(left), height(right)) + 1

但是相反，您实际上是在说：

if (left)
   return height(left) + 1
else if (right) 
   return height(right) + 1

因此，如果一个节点的左腿短而右腿长，那么您会得到错误的答案。

于 2013-03-25T05:21:57.977 回答
0

只是一个提示。在遍历树进行一些计算时，您需要递归处理两个子树。

所以任何非空给定树节点的高度应该是 

max( (  height of left sub tree) , (height of right  sub tree)) + 1

如其他答案中所述，您的遍历不正确。

如果节点为空，则其高度为 0。

同样，任何非空节点的大小都是 sizeof(left)+sizeof(right)+1 等

于 2013-03-25T05:27:49.883 回答