问二叉树属性-平衡

EN

不，这两者不是等同的。

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

是满足属性2的树，而不是属性1。

然而，属性1意味着属性2。

命题:二叉树中的，该二叉树根据属性1与n内部节点保持平衡，所有叶子都在

• k if n = 2^k - 1
• k或k+1，如果是2^k <= n < 2^(k+1)-1，有叶子在深度k+1。

证明：(通过对内部节点数目的归纳)

对于n = 1 = 2^1-1，在深度1处有一两片叶子(根位于深度0)。

对于n = 2，一个子树有一个内部节点，该子树中的所有叶子都在深度2，另一个子树是空的，或者是深度为1的叶子。

让n >= 2并考虑一棵根据属性1与n+1内部节点保持平衡的二叉树。

如果n是偶数，n = 2*m，则这两个子树都必须有m内节点，而深度属性则由归纳假设决定。

如果n = 2*m+1是奇数，一个子树有m内部节点，另一个m+1。

1. 如果是2^k <= m < 2^(k+1)-1，则m内部节点的子树在k+1深度处有叶子，根据归纳假设可能在深度k处有叶子。具有m+1内部节点的树在深度k+1中也有叶子，可能在深度k处有(如果m+1 < 2^(k+1)-1)。
2. 如果是m = 2^k - 1，则具有m内部节点的子树仅在深度k处有叶子，而带有m+1内部节点的子树在深度k+1处有叶子，可能在深度k处有叶子。