数据结构c语言版期末考试 - 图文

（4） 画出该二叉树的中序线索二叉树； （5） 画出该二叉树的后序线索二叉树； （6） 画出该二叉树对应的森林；

17

10．已知一棵树边的集合为{,,,,,,,,,,, ,}，画出这棵树。

11．假设二叉树采用顺序存储结构，如图所示。 （1） 画出二叉树表示；

（2） 写出先序遍历、中序遍历和后序遍历的结果；

（3） 写出结点值c的双亲结点，其左、右孩子；（1）：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 e a f d g c j h i b （4） 画出把此二叉树还原成森林的图。

18

12．已知一棵二叉树的中序序列为cbedahgijf，后序序列为cedbhjigfa，画出该二叉树的先序线索二叉树。

19

13．某二叉树的先序遍历序列是abdgcefh，中序遍历序列是dgbaechf，给出其后序遍历序列。

后序遍历序列：gdbehfca

14．将下图所示森林转换成为二叉树，并写出转化后二叉树中序遍历结果。 GLA

H CBMNO

J IKPDEF RQ

15．有一份电文中共使用8个字符：a、b、c、d、e、f、o、i，它们的出现频率依次为10，20，15，32，40，60，26，18。试画出对应的哈夫曼树（请按左子树根结点的权小于等于右子树根结点的权的次序构造），并求出每个字符的哈夫曼编码。

16．已知某系统在通信联络中只可能出现A,B,C,D,E,F,G,H八种字符，其频率为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11试设计哈夫曼编码。

20