二叉树属性-平衡

Question

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

二叉树的dev.表示：

>

如果任意两片树叶的深度差最大为1，则二叉树是平衡的。

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

谢谢，帕特里克

Answer 1

不，这两者并不等同。

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

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

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

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

• kifn=2^k-1
• kork 1if2^k

证明：（通过对内部节点数的归纳）

对于n=1=2^1-1，在深度1处有一到两片叶子（根在深度0处）。

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

让n

如果n是偶数，n=2*m，则两个子树都必须具有m内部节点，并且深度属性由归纳假设保持。

如果n=2*m1为奇数，则一个子树具有m内部节点，另一个子树具有m1。

>

如果2^k

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