我试图理解二叉树的属性。但我不确定一件事:
定义。一个二叉树的状态是:
二叉树是平衡的,如果对于每个节点,它认为左子树中的内部节点数和右子树中的内部节点数最多相差1。
如果任意两个叶的深度差为ast most 1,则二叉树是平衡的。
我在问这两个定义。是等价的,我是说Def1个状态定义。2和维切弗萨?... 对我来说似乎是的……但是谁能用例子来确切地解释这些性质的(非)等价性呢?
谢谢,
帕特里克

最佳答案

不,这两个不相等。

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

是满足属性2但不满足属性1的树。
然而,属性1表示属性2。
命题:在根据属性1和n内部节点进行平衡的二叉树中,所有叶子都位于
k如果n = 2^k - 1
kk+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内部节点。
如果2^k <= m < 2^(k+1)-1,则具有m内部节点的子树在深度k+1处有叶,并且根据归纳假设可能在深度k处有叶。具有m+1内部节点的树在深度k+1处也有叶子,并且可能(如果m+1 < 2^(k+1)-1)在深度k处有叶子。
如果m = 2^k - 1,则具有m内部节点的子树仅在深度k处有叶,而具有m+1内部节点的子树在深度k+1处有叶,并且可能在深度k处有叶。

关于algorithm - 二叉树属性-平衡,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/14882306/

10-11 23:19
查看更多