C语言,二叉树的问题
1.如果一个二叉树有70个叶子结点,与80个度为1的结点。求此二叉树的总结点!2.如果一个完全二叉树有500个结点,则有多少个叶子结点!求计算方法。。...
1.如果一个二叉树有70个叶子结点,与80个度为1的结点。求此二叉树的总结点!
2.如果一个完全二叉树有500个结点,则有多少个叶子 结点!
求计算方法。。 展开
2.如果一个完全二叉树有500个结点,则有多少个叶子 结点!
求计算方法。。 展开
展开全部
性质:对任何一棵二叉树,度为0的结点(即叶子结点)总是比度为2的结点多一个
所以问题1中,总结点:N = 70 + 80 + 69 = 219
问题2:
深度为9的满二叉树,结点合是:511
深度为8的满二叉树,结点合是:255
由上知要求的这棵树,深度为9,但最后一层不满,
则最后一层的叶子结点数为:500-255=245
则倒数第二层的叶子结点数为:128-123=5
则此树总共叶子结点数为:245+5=250个
所以问题1中,总结点:N = 70 + 80 + 69 = 219
问题2:
深度为9的满二叉树,结点合是:511
深度为8的满二叉树,结点合是:255
由上知要求的这棵树,深度为9,但最后一层不满,
则最后一层的叶子结点数为:500-255=245
则倒数第二层的叶子结点数为:128-123=5
则此树总共叶子结点数为:245+5=250个
已赞过
已踩过<
评论
收起
你对这个回答的评价是?
展开全部
1.219
二叉树的几点只有 0 1 2 三种度数
2度节点 数等于0度节点(即叶子节点)减1
n=n0+n1+n2=70+80+69=219
2.250
满二叉树下 节点数(n)与深度(m)的关系是
n=1+2+4+……+2^(m-1)=(2^m)-1
因为完全二叉树 的节点数n 2^(m-1)-1<n<=2^m-1
所以 m=9 深度为9 满二叉树的叶子是 256 节点一共是511
完全二叉树节点少了11 256-11 =245 因为两个叶子 有一个父亲 11/2 =5 本来的父亲没了孩子 成为叶子 245+5=250
二叉树的几点只有 0 1 2 三种度数
2度节点 数等于0度节点(即叶子节点)减1
n=n0+n1+n2=70+80+69=219
2.250
满二叉树下 节点数(n)与深度(m)的关系是
n=1+2+4+……+2^(m-1)=(2^m)-1
因为完全二叉树 的节点数n 2^(m-1)-1<n<=2^m-1
所以 m=9 深度为9 满二叉树的叶子是 256 节点一共是511
完全二叉树节点少了11 256-11 =245 因为两个叶子 有一个父亲 11/2 =5 本来的父亲没了孩子 成为叶子 245+5=250
本回答被提问者采纳
已赞过
已踩过<
评论
收起
你对这个回答的评价是?
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询