以文本方式查看主题

-  计算机科学论坛  (http://bbs.xml.org.cn/index.asp)
--  『 计算机考研交流 』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  每天一问_2007_10_10  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=53607)

--  作者：xiuluodao
--  发布时间：10/10/2007 10:41:00 PM

--  每天一问_2007_10_10
发现一个好题：
有n个结点的二叉树，已知叶结点的个数为n0,写出求度为1的结点个数n1的计算公式；若此数是深度为k的完全二叉树，写出n为最小的公式；若二叉树中仅有为度为0和度为2的结点，写出该二叉树结点个数n的公式。
--  作者：javacap
--  发布时间：10/11/2007 10:36:00 AM

--  
n1=n-2*n0+1
2^k
2^(k+1)-1
--  作者：xiuluodao
--  发布时间：10/11/2007 8:08:00 PM

--  
以下是引用javacap在2007-10-11 10:36:00的发言：
n1=n-2*n0+1
2^k
2^(k+1)-1


第三问我觉得应该是2*n0-1，你觉得呢？
--  作者：蝶影
--  发布时间：10/11/2007 9:52:00 PM

--  
第三问是2*n0-1,因为在任一二叉树中,度为0的结点比度为2的结点多1,所以度为2的结点是n0-1,因为二叉树中只有度为0的结点和度为2的结点,所以n=n0+n0-1=2*n0-1
--  作者：javacap
--  发布时间：10/11/2007 9:58:00 PM

--  
看怎么问了,如果上下文的意思是问n关于深度k的公式.那就是2^(k+1)-1如果是关于n0的公式,那就是2n0+1
--  作者：xiuluodao
--  发布时间：10/11/2007 11:52:00 PM

--  
以下是引用javacap在2007-10-11 21:58:00的发言：
看怎么问了,如果上下文的意思是问n关于深度k的公式.那就是2^(k+1)-1如果是关于n0的公式,那就是2n0+1


我觉得n与深度k之间不存在公式，比如说深度为2的二叉树的话，可以有5个结点和7个结点两种情况，
设5个点为层次遍历为ABCDE,它们的度数为2,2,0,0,0;设7个点的层次遍历为ABCDEFG,它们的度数分别为2,2,2,0,0,0,0;则与之矛盾。
--  作者：javacap
--  发布时间：10/12/2007 10:20:00 AM

--  
嗯，是我想错了，汗一个。
W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 31.250ms