读书人

请问一个二叉树的有关问题

发布时间: 2012-02-09 18:22:27 作者: rapoo

请教一个二叉树的问题
一棵有2011个结点的树,其叶结点个数为116,该树对应的二叉树中无右孩子的结点的个数是多少个?

[解决办法]
不可能是确定值,度为一的有1780,而只要对称过去,结点个数不变,而情况却变了,至少115个,至多1895个
[解决办法]
楼上的分析好像是正确的

[解决办法]
转化完全二叉树的模型。。算得应该是454个。。
[解决办法]
116 = 2^6 -1 + 2^5 -1 + 2^4 -1 + 2^3 -1
此时有两个子结点的结点及叶结点的总个数为:
(2^6 + 2^5 + 2^4 + 2^3 + 2^2 +2^1 + 2^0) + (2^5 + 2^4 + 2^3 + 2^2 +2^1 + 2^0) +
(2^4 + 2^3 + 2^2 +2^1 + 2^0) + (2^3 + 2^2 +2^1 + 2^0) = 216
此时可算出只有单个子结点的结点数为2011 - 216 = 1795

读书人网 >软件架构设计

热点推荐