首页 > 编程知识 正文

二叉树的度结点,10个结点的完全二叉树的深度

时间:2023-05-03 22:58:53 阅读:255751 作者:599

二叉树的性质

1.二叉树中,第 i 层最多有 2i-1 个结点。
2.如果二叉树的深度为 K,那么此二叉树最多有 2K-1 个结点(k>=1)。
3.二叉树中,终端结点数(叶子结点数)为 n0,度为 2 的结点数为 n2,则 n0=n2+1
证明:n0=n2+1
设n1为二叉树中度为1的结点数。因为二叉树中所有结点的度均小于或者等于2,所以结点总数为 n=n0+n1+n2
设A为分支总数,因为除了根结点外,其余结点都有一个分支进入,所以n=A+1.由于这些分支是由度为1或2的结点射出的,所以又有A=n1+2n2
可得:n=n1+2n2+1

n=n0+n1+n~2n=n1+2n2+1
有两个式子可得:终端结点(叶子结点)n0=n2+1
拓展
一个度为m的树中,叶子结点个数为:n0=n2+2n3+3n4+(m-1)nm+1
【例题3】一颗完全二叉树上又1001个结点,其中叶子结点的个数是( )
A.250 B.254
C.500 D.501
解析:因为完全二叉树度为1的结点只能是1个或0个,当总结点个数n为偶数的时候n1=1;当总结点个数n为奇数的时候n1=0。再利用公n0=n2+1①和n=n0+n1+n2②可以得出n=n1+2n2+1③,因为1001是一个奇数所以n1=0,带入得1001=0+2n2+1,则n2=500,再将n2=500带入①中可得叶子结点n0=501.
答案选:D

【课后习题8】在一颗度为4的树T中,若有20个度为4的结点,10个度为3的结点,1个度为2的结点,10个为1的结点,则树T的叶节点个数是( )
A.41 B.82
C.113 D.122
解析:利用拓展公式n0=n2+2n3+3n4+(m-1)nm+1带入,n0=1+2x10+3x20+1=82.
答案选:B

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。