计算二叉搜索树的高度

Question

我一直在寻找如何计算二进制搜索树的高度,我的研究引导我进行以下实现.我仍然试图解决为什么它应该工作,但我也不确定为什么它不起作用.这是我的身高功能.

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;
    }
}

Answer 1

你的树不是无限的.所以,我想一些节点没有左或右子节点,指针left和/或right在这种情况下为空.在尝试使用它们之前,您必须检查它们的存在.

尝试使用该功能:

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);
}

注意:我已经简化了你的身高计算.