2

我一直在寻找如何计算二叉搜索树的高度，我的研究使我得到了以下实现。我仍在努力思考为什么它应该起作用，但我也不确定它为什么不起作用。这是我的高度函数。

int BinaryTreeNode::height() const {
    int lefth = left->height();
    int righth = right->height();
    if(lefth > righth) {
        return lefth + 1;
    } else {
        return righth + 1;
    }
}

这是我对节点的类定义

class BinaryTreeNode {
  public:
    Data * nodeData;
    BinaryTreeNode * left;
    BinaryTreeNode * right;

当我尝试运行它时，我的程序锁定并崩溃。我错过了一些明显的东西吗？

编辑：为什么这不起作用？

int BinaryTreeNode::height() const {
    int l = 0;
    if (left != NULL) {
        left->height();
    }
    int r = 0;
    if (right != NULL) {
        right->height();
    }
    if (l > r) {
        return l + 1;
    }
    else {
        return r + 1;
    }
}
4

3 回答 3

10

Your tree is not infinite. So, I suppose some nodes do not have left or right childs, and the pointers left and/or right are null in this case. You have to check for their existence before trying to use them.

Try that function instead:

int BinaryTreeNode::height()
{
    int l = left ? left->height() : 0;  // height of left child, if any
    int r = right ? right->height() : 0; // idem for right child
    return 1 + max(l, r);
}

Note: I have simplified your computations of height.

于 2013-03-30T21:28:16.320 回答
2

问题是您的函数从不检查子指针是否为NULL，因此除了取消引用无效指针之外，您还有一个缺少基本情况的递归函数：

试试这个版本：

int BinaryTreeNode::height() const 
{
    int lefth = 0;
    if (left != NULL) { lefth = left->height(); }

    int righth = 0;
    if (righth != NULL) { righth = right->height(); }

    if (lefth > righth) { return lefth + 1; } 
    else { return righth + 1; }
}
于 2013-03-30T21:26:14.443 回答
0

Even I was facing the same problem, well the problem with your code is that in your function you are using recurssion twice and you are going to the left and right extremities, but you arent checking the possibility if the right child of one of the parent node in left subtree has its own children, hence your are not traversing to the last leaf node in your tree! hope this helps

于 2017-01-03T03:13:32.743 回答