玛丽苏扭转系统[快穿:有道“完全二叉树”的题不会做,急求人帮忙!!!
来源:百度文库 编辑:中科新闻网 时间:2024/08/30 06:05:07
我正在学ACCESS,准备9月考二级,但有道题怎么也做不出来,原题是:
“设一棵完全二叉树有700个结点,则在该二叉树中有___个叶子结点.”
(参考答案说有350个,但我不知道是怎么求出来的。)
希望好心人帮忙告诉我解题步骤,感激不尽!!!~~~
“设一棵完全二叉树有700个结点,则在该二叉树中有___个叶子结点.”
(参考答案说有350个,但我不知道是怎么求出来的。)
希望好心人帮忙告诉我解题步骤,感激不尽!!!~~~
根据二叉树的性质:对于一棵非空的二叉树,如果叶子节点数为n0,度为2的结点数为n2,则no=n2+1.
根据完全二叉树的定义可得:在完全二叉树中度为1的结点n1只能取两种情况,要么为0,要么为1.
所以:n0+n1+n2=700
n0=n2+1;
2n0=701-n1;
因为结点数为整数,所以n1=1,no=350
不只这样回答你是不是满意,如果满意请采纳。
一共有700个结点。这要看你掌握二叉树的性质掌握的怎么样了。。。
N0+N1+N2=700
N0=N2+1;
2N0=701-N1;
结点数一定是整数。。所以N1=1,N0=350
完全二叉树的叶子结点数是总结点数的一半
你画图看看就知道了
假设画个16个结点的完全二叉树,第1行1个结点,第2行2个,第3行4个,第4行8个,那么还多一个结点,放到第5行去,第5行1个
然后第5行的那个结点+第4行不是根结点的结点有7个,总共8个叶子结点
楼上好几位答案都不错,不过 撅啊撅 说“完全二叉树的叶子结点数是总结点数的一半”,这有点问题吧。如果结点总数为奇数呢?
2的0次方+2的1次方+.....+2的n次方>=700(n为整数)
n求出取最小值
答案就是700-(2的0次方+2的1次方+.....+2的n-1次方)