algorithm - 二叉树属性 - 平衡

Question

我试图了解二叉树的属性。但我不确定一件事：

定义。一棵二叉树指出：

1. 如果对于每个节点，二叉树的左子树中的内部节点数和右子树中的内部节点数最多相差 1，则二叉树是平衡的。

2. 如果任何两个离开差异，则二叉树是平衡的。深度的最大为 1。

我问我这两个是否定义。是等价的，我的意思是Def。1 统计 Def。2 反之亦然？...对我来说似乎是的...但是谁能用示例准确地解释我这个属性的（非）等价性？

谢谢，帕特里克

Answer 1

不，两者不等价。

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

是一棵满足属性 2 但不满足属性 1 的树。

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

命题：在根据性质 1 与内部节点平衡的二叉树中n，所有叶子的深度为

• k如果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 处。

让我们考虑一棵根据属性 1 与内部节点n >= 2平衡的二叉树。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内部节点的树在 depth 也有叶子，k+1并且可能（如果m+1 < 2^(k+1)-1）在 depth k。

2. 如果m = 2^k - 1，具有m内部节点的子树仅在深度处具有叶子k，而具有内部节点的子树m+1在深度处具有叶子，k+1并且可能在深度处具有叶子k。