七、二叉树(二)、二叉树的性质

数据结构目录

二叉树的性质一

在二叉树的第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. 假设度为1的结点数为n1，则二叉树T的结点总数为n=n0+n1+n2
2. 其次我们发现连接数总数等于总结点数n-1，并且等于``n1+2*n2
3. 所以 n-1=n1+2*n2
4. n0+n1+n2-1=n1+2*n2
5. 得出结论n0=n2+1

二叉树的性质四

具有n个结点的完全二叉树的深度为⌊log₂n⌋+1
推导过程:略

二叉树的性质五

如果对一棵有n个结点的完全二叉树的结点按层序编号，对任一结点i(1<=i<=n)有以下性质：

1. 如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点⌊i/2⌋
2. 如果2i > n，则结点 i 无做左孩子(结点 i 为叶子结点)；否则其左孩子是结点2i
3. 如果2i+1 > n，则结点 i 无右孩子；否则其右孩子是结点2i+1