《数据结构 - C语言描述》习题及答案 耿国华 2

（3）可能的最大满二叉树是几层？有多少叶结点？

如何增补？

25<50<26

可能的最大满二叉树是6层 有 25 = 32个叶结点

假设将其中x个变为2度结点后，总叶结点数目为

50

则：2x + (32 – x) = 50 得：x = 18

此时总结点数目= ( 26 – 1) + 18×2 [方法2]

假设完全二叉树的最大非叶结点编号为m， 则最大叶结点编号为2m+1, (2m+1)-m=50 m=49

总结点数目=2m+1=99 [方法3]

a

由性质3：n0=n2+1 即：50=n2+1 所以：n2=49

令n1=0得：n= n0 + n2=99

7． 给出满足下列条件的所有二叉树： a) 前序和中序相同 b) 中序和后序相同 c) 前序和后序相同 [提示]：去异存同。

a) D L R 与L D R 的相同点：D R，如果无 L，则完全相同, 如果无 LR，…。

b) L D R 与L R D 的相同点：L D，如果无 R，则完全相同。

c) D L R 与L R D 的相同点：D，如果无 L R，则完全

a