algorithm - 二叉树高度的不同解释

Question

我是学数据结构和算法的，这个东西真的让我很迷惑

二叉树的高度，因为它也用于 AVL 搜索树。

根据我正在关注“Lipschutz 的数据结构”这本书，它说“树 T 的深度(或高度)是 T 的一个分支中的最大节点数。结果是 1 比T 的最大层数。图 7.1 中的树 7 的深度为 5。"

图 7.1:

             A 
            / \
           /   \           
          /     \
         /       \
        B         C
       / \       / \
      D   E     G   H
         /         / \
        F         J   K
                 /
                L

但是，在其他几个资源中，虽然给出了相同的定义，但高度的计算方式有所不同。例如，当我从互联网上阅读时 http://www.cs.utexas.edu/users/djimenez/utsa/cs3343/lecture5.html

"这是一个示例二叉树:

                   1
                  / \
                 /   \
                /     \
               /       \
              2         3
             / \       / \
            /   \     /   \
           /     \   /     \
          6       7 4       5
         / \     /         /
        9  10   11        8

树的高度是所有节点深度的最大值。所以上面的树的高度是 3。"

另一个来源http://www.comp.dit.ie/rlawlor/Alg_DS/searching/3.%20%20Binary%20Search%20Tree%20-%20Height.pdf

说，“二叉树的高度对于只有一个节点的树，即根节点，高度定义为0，如果有2高度为 1 的节点级别，依此类推。空树(除空节点外没有其他节点)被定义为具有 –1 的高度。 "

现在这最后两个解释相互符合，但与书中给出的例子不符。

另一个来源说“有两种约定来定义二叉树的高度1) 从根节点到最深节点的最长路径上的节点数。2) 从根节点到最深节点的最长路径上的边数。

在这篇文章中，遵循第一个约定。例如，下面树的高度是 3。

              1
             / \
            2   3
           / \
          4   5

"在此，我想问一下根和叶之间的节点数和边数如何相同？而叶子节点的高度是多少，按照书上应该是1(因为最大层数是0，所以高度应该是0+1=1，但通常说叶节点的高度为0。另外为什么这本书提到深度和高度是同一回事？这件事真的让我很困惑，我尝试从多个来源进行澄清，但似乎无法在两种解释之间做出选择。请帮忙。

==> 我想补充一下，因为现在我接受了本书的约定， 在 AVL 搜索树的主题中，我们需要计算平衡因子(即左右子树的高度差)它说:

            C (-1)
           / \
      (0) A   G (1)
             /
            D (0)

括号内的数字为平衡系数。

现在，如果我要按照书上的 D 的高度为 1，而 G 的右子树的高度为 (-1) 因为它是空的，所以 G 的平衡因子应该 = 1-(-1)=2!

现在为什么这里 D 的高度为 0？

请帮忙。

Answer 1

如果您关心的是平衡因素，那么高度的确切定义并不重要。回想一下，平衡因子是

height(left) - height(right)

因此，如果两者都比您最喜欢的高度定义大一或小一，则平衡因子不会改变，只要您相应地重新定义一棵空树的高度。 p>

现在的问题是“分支中的最大节点数”定义都是递归的，但没有指定基本情况。但由于根据此定义单元素树的高度为 1，因此零元素树的高度显然选择为零，如果你计算出这些公式，你会发现这是可行的。

您还可以通过观察另一个定义的基本情况是 -1 来得出零值，否则它总是给出比“分支中的最大节点数”定义小 1 的值。