数据结构(c环境下操作)

已知一棵完全二叉树有657个结点,求:

1)树的高度;

2)叶子结点个数;

3)若从根结点开始以1编号,那么其叶子结点的最小编号是多少?

给出解答步骤或分析过程。

高度:log2(657)+1,结果向下取整,答案是10

结点个数:可以这么理解,除了根节点,每多一个叶子结点,就会多一个非叶子结点,所以算法的话,总结点数为奇数,那就先加一,再除以2就好,如果是偶数,那就直接除以2,结果:(657+1)/2=329

最小编号:无论怎么排,编号最小的叶子结点就是编号最大的非叶子结点的下一个(可以自己画几张图理解一下)。

然后看编号规律,每个结点i的两个子节点分别是2i和2i+1,两个编号一个为奇数,一个为偶数,由于根节点是一个,总结点数也是奇数,所以最后一个结点应该是一个奇数结点(对应两个子节点里的第二个)。最后一个结点必定为叶子结点(这点不需要解释吧)。最后一个叶子结点对应的父节点一定是最后一个非叶子结点(这个应该也好理解,实在不行画个图看下就会明白)。

这样就可以开始解第三题了:最后一个结点编号657,(657-1)/2+1即为所求,结果是329