习题7
三、填空题
1．孩子链表表示法、双亲孩子表示法、孩子兄弟表示法。

2．11。

3． FEGHDCB、 BEFCGDH
4．先序、中序。

5．二叉树
四、应用题
1．所给树如下图：
（1）根结点是a，
（2）叶结点是d, m, n, f, j, k, l，
（3）g的双亲是c,
（4）g的祖先是a,
（5）g的孩子是j,k,
（6）e的子孙是m,n,
（7）e的兄弟是d, f的兄弟没有，
（8）结点b和n的层次各是2和5，
（9）树的深度是5，
（10）以结点c为根的子树的深度是3，
（11）树的度数是3。

2．答：度为2的有序树无左右子树之分，而二叉树有左右子树之分。

如含3个结点的有序树只有1棵，含3个结点的二叉树有5棵。

如下图所示。

含3个结点的度为2的有序树含3个结点的二叉树
3．试分别画出具有4个结点的树和4个结点的二叉树的所有不同形态。

解：如下图。

含4
个结点的树
5
棵只有右子树的二叉树
5
棵只有左子树的二叉树
4棵左右子树都有的二叉树
4．第i层的结点数目是k i-1个
（1） 编号为i 的结点的双亲结点（若存在）的编号是⎥⎥⎤⎢⎢⎡k
i （2） 编号为i 的结点的第j 个孩子结点（若存在）的编号是3i+j-1
（3） 编号为i 的结点有右兄弟的条件是结点个数大于⎥⎥⎤
⎢⎢⎡k i k ⨯，其右兄弟的编号是⎥⎥
⎤⎢⎢⎡k i k ⨯+1 与第6章的5、6、8一样
8. 一棵有n(n>0)个结点的d 度树, 若用多重链表表示, 树中每个结点都有d 个链域, 则在
表示该树的多重链表中有多少个空链域? 为什么?
答：dn-n+1个。

因为n 个结点共dn 个指针域，除根节点外，其余n-1个结点使用了n-1个
指针域，所以空闲的指针域共dn-n+1个。

9．一棵共有n 个结点的树，其中所有分支结点的度均为K ，求该树中叶子结点的个数。

10．写出图1所给树的先序和后序遍历序列，并将此树转化成二叉树。

先序序列为：abdegfchijk
后序序列为：dgefbihkjca
对应的二叉树为：
11．写出图2所给森林的先序和中序遍历序列，并将此森林转化成二叉树。

先序为：abcdfeghkijlmno
中序为：cfdebakhiljgnom
对应的二叉树为：
12、二叉树对应的森林如下：。