一颗124个叶子结点的完全二叉树，最多有多少个结点？？

yuehongsun

一颗124个叶子结点的完全二叉树，最多有多少个结点？？　我觉得是248　　答案是249

我是这样计算的　
n=n0+n1+n2,n0=n2+1 ==>n=2n0+n1-1
其中在完全二叉树中　n1或为0或者为1　
要使最多结点　则n1为１　所以得到结点n=248

还有一个问题
数的高度和深度是不是两个不同的概念　高度为h　深度为k　则k=h-1  对不对？有些地方是这样写的

严蔚敏的《数据结构（C语言版）》中二叉树的深度定义是这样的,"结点的层次从根开始定义,根为第一层,树中结点的最大层次为树的深度或高度” 　那就是一样的咯

※ 编辑：yuehongsun 于2008-12-28 22:47 编辑本文

jefferykowk

124=2^7-4;
第八层有120个叶子结点，第七层剩余4个叶子结点；
所以节点数=1+2+……+2^6+120=2^8-1-8=247

和答案好像也不一致，哪位高手帮检查一下~~

yuchiakek

答案错了   应该是248   以前帖子讨论过

liyouhaihao

2^7-4=124
原完全二叉树第8层少4个叶子结点
但第七层多了由父结点形成的两个叶子结点
第八层再去两个结点，但两结点的父结点又形成了一个叶子结点
再在第八层去一个结点，以下就是算式
总结点数为2^8-1-4-2-1=248
答案：248
you believe in me!

wenlong1986

应该是248吧，解题的过程是正确的 。