二叉树的性质一
在二叉树的第i层上最多有2^(i-1)个结点(i>=1)
第i层上最多有2^(i-1)个结点(i>=1)
二叉树的性质二
深度为k的二叉树最多有2^k-1个结点(k>=1)
注意 这里是2^k再减1
深度为k的二叉树最多有2^k-1个结点(k>=1)
二叉树的性质三
对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2,则n0=n2+1
推导过程：
- 假设度为1的结点数为n1，则二叉树T的结点总数为
n=n0+n1+n2 - 其次我们发现
连接数总数等于总结点数n-1，并且等于``n1+2*n2 - 所以
n-1=n1+2*n2 n0+n1+n2-1=n1+2*n2- 得出结论
n0=n2+1
二叉树的性质四
具有n个结点的完全二叉树的深度为⌊log₂n⌋+1
推导过程:略
二叉树的性质五
如果对一棵有n个结点的完全二叉树的结点按层序编号，对任一结点i(1<=i<=n)有以下性质：
- 如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点⌊i/2⌋
- 如果2i > n，则结点 i 无做左孩子(结点 i 为叶子结点)；否则其左孩子是结点2i
- 如果2i+1 > n，则结点 i 无右孩子；否则其右孩子是结点2i+1
网友评论