c++ - 计算二叉搜索树的高度

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

注意:我已经简化了您的高度计算。