数据结构习题

1. 已知一颗完全二叉树共有2018个节点，则该二叉树共有_______个叶子结点。
   题解：
     根据公式可知，说明该完全二叉树共有11层，前10层总节点数根据公式可知共有1023个节点。
     则有：总结点数-前10层总结点数=第11层节点数，所以第11层有2018-1023=995个节点，995个节点需要挂在第10层节点上，所以会占用第10层的995÷2=497.5，由于不能占用半个节点，所以向上取整占用第10层498个节点。
     根据公式得出第10层节点个数为为512个节点，所以第10层有512-498=14个节点没挂任何节点，所以该节点也是叶子节点。
     则得出结果：第10层的叶子结点有14个，第11层的叶子节点有995个，共有：995+14=1009个叶子结点。
   答案：1009

也可以直接使用结论快速得到答案：

• 如果完全二叉树总结点个数为偶数个，叶子节点等于总节点除以2，即
• 如果完全二叉树总结点个数为奇数个，叶子节点等于总节点+1除以2, 即

2. 已知森林F及与之对应的二叉树T，若F的先根遍历序列为abcdef，后根遍历序列为badfec，则T的后序遍历序列为（）
   A.badfec
   B.bdfeca
   C.bfedca
   D.fedcba
   题解：

森林先根等价二叉树先序。
森林中根等价二叉树中序。
森林的后根等价森林中根。
树先根等价二叉树先序。
树后根等价二叉树中序。

F的先根和后根则对应二叉树的先序和中序。
通过中序序列badfec，结合前序序列abcdef可以判断出，a是根节点，中序中a后面的序列dfec是a的右子树的中序序列，可以初步得出二叉树的样子：

同理，在剩余中序序列dfec中，结合剩余前序序列cdef可以得到c为根，而在中序中的c的左边没有序列，所以dfe是c的左子树。推理可以得出c是一个没有右子树的节点，现在可以进一步确认二叉树的样子：

同理，在剩余中序序列dfe中，结合剩余前序序列def推出d为根，在中序中d左边没有序列，所以d没有左子树，右子树为fe，进一步得到二叉树的样子：

同理，在剩余中序序列fe中，结合剩余前序序列ef可以知道e是根，中序中e右边没有序列，所以得出f是e的左子树。则最终二叉树的样子为：

根据二叉树结构得出二叉树的后序遍历序列为bdfeca
答案：B