我试图理解二叉树的属性。但我不确定一件事:
定义。一个二叉树的状态是:
二叉树是平衡的,如果对于每个节点,它认为左子树中的内部节点数和右子树中的内部节点数最多相差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
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
内部节点。如果
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/