互联网上关于二叉搜索树深度的大多数代码片段都是错误的吗？

Question

我目前正在实施一个二叉搜索树。我的教材指出，树的深度等于最深的叶子的深度。节点本身的深度定义为从根到该节点的边数量。但是，当我想在互联网上检查我的实现是否正确时，我发现许多实现都是这样的：

int Tree::Depth()
{
    if (!this)
    {
        return 0;
    }

    return max(this->left.Depth(), this->right.Depth()) + 1;
}

• http://codercareer.blogspot.be/2013/01/no-35-depth-of-binary-trees.html
• 二叉搜索树的最大深度
• 这两个代码之间有什么区别来找到二叉树的最大深度？
• 如何计算二叉搜索树的深度

但是使用返回0给出了节点的数量而不是边的数量（节点的数量=边的数量1）。不应该是返回-1吗？Robert Sedgewick似乎也使用了-1：

/**
 * Returns the height of the BST (for debugging).
 *
 * @return the height of the BST (a 1-node tree has height 0)
 */
public int height() {
    return height(root);
}
private int height(Node x) {
    if (x == null) return -1;
    return 1 + Math.max(height(x.left), height(x.right));
}

• http://algs4.cs.princeton.edu/30searching/

释义树的大小是其节点数。树中节点的深度是从它到根的路径上的链接数。树的高度是其节点之间的最大深度。

~罗伯特·塞奇威克和凯文·韦恩的算法(第四版)

深度为0的根的例子可见于第三版“算法简介”的第490页。托马斯·h·科尔曼、查尔斯·e·莱瑟森、罗纳德·L·李维斯特和克利福德·斯坦编辑。

有人能帮我澄清这个困惑吗？

Answer 1

Sedgewick的实现是正确的。

节点的高度是从该节点到叶子的最长向下路径的长度。根的高度就是树的高度。

因此，树的高度大约是路径的长度（以边而不是节点来衡量）。只包含根节点的树的高度为0，甚至没有根节点（如果允许的话）的树被定义为高度为-1。

参考：树（数据结构）