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

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
• 二叉搜索树最大深度
• 这两个代码在寻找二叉树的最大深度方面有什么区别?
• 如何计算二叉搜索树的深度

但是使用return 0给出的是节点的数量而不是边的数量(节点的数量=边的数量+ 1)，不应该是return -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/> http://algs4.cs.princeton.edu/32bst/BST.java.html

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

~算法(第4版)作者:Robert Sedgewick和Kevin Wayne

在"算法导论"第3章第490页可见根深度为0的例子。版，托马斯·h·科曼，查尔斯·e·雷瑟森，罗纳德·l·里维斯特，克利福德·斯坦。

有人能帮我澄清一下吗?

Answer 1

Sedgewick的实现是正确的。

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

所以树的高度与路径的长度有关(以边来衡量，而不是节点)。仅包含根节点的树的高度为0，甚至不包含根节点的树(如果允许的话)的高度定义为-1。

参考:树(数据结构)