数据结构习题解答

6.2 一棵度为2的树与一棵二叉树有何区别？

答：度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。即，在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分。

6.3 试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。

答：含3个结点的树只有两种形态：（1）和（2）；而含3个结点的二叉树可能有下列5种形态：（一），（二），（三），（四），（五）。

（2）

（1） A A A B B B C （二） C C （四） B B A A C （一） （三）

C （五） 6.14 找出所有满足下列条件的二叉树：

（1）它们在先序遍历和中序遍历时，得到的结点访问序列相同； （2）它们在后序遍历和中序遍历时，得到的结点访问序列相同； （3）它们在先序遍历和后序遍历时，得到的结点访问序列相同。 答：

（1）任意一个结点都只有右子树或者为叶子结点； （2）任意一个结点都只有左子树或者为叶子结点； （3）只有根结点。

6.19分别画出和下列树对应的各个二叉树。

A A A A B B C B C D C E I J F G H K 答：对应的各个二叉树如下所示：

A A A B B B C C E D A C I F J G K 6.22 对于6.19题中给出的各树分别求出一下遍历序列： （1）先根序列 （2）后根序列 答：

（1）（a）A （b）ABC （c）ABC （d）ABCEIJFGKHD （2）（a）A （b）CBA （c）BCA （d）BIJEFKGHCDA

H 6.26 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为

0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。试为这8个字母设计哈夫曼编码。使用0~7的二进制表示形式是另一种编码方案。对于上述案例，比较两种方案的优缺点。

答：哈夫曼编码方案的带权路径长度为WPLHF=2.61，而等长编码的路径长度为WPLEQ=3，显然前者可以大大提高通信信道的利用率，提高报文发送速度和节省存储空间。下面给出两种编码的对照表及哈夫曼树的逻辑结构。 频数 哈夫曼编码 7 0010 19 10 2 00000 6 0001 32 01 3 00001 21 11 10 011 等长编码 000 001 010 011 100 100 101 110 111 0 60 1 1 17 1 6 1 2

3 0 7 1 10 32 1 40 0 19 1 21 0 28 0 11 0 5 0 6.27 假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。 答：

E B A C D G F H I K J 6.28 假设一棵二叉树的中序序列为DCBGAHFIJK和后序序列为DCEGBFHKJIA。请画出该树。 答：

A B I C G H J D E F K

四、算法设计题

6.42 编写递归算法，计算二叉树中叶子结点的数目。 答：

方法一：核心部分为：

DLR(liuyu *root) /*中序遍历 递归函数*/ {if(root!=NULL)

{if((root->lchild==NULL)&&(root->rchild==NULL)){sum++; printf(\ DLR(root->lchild); DLR(root->rchild); } return(0); } 方法二：

int LeafCount_BiTree(Bitree T)//求二叉树中叶子结点的数目 {

if(!T) return 0; //空树没有叶子

else if(!T->lchild&&!T->rchild) return 1; //叶子结点

else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加 上右子树的叶子数 }//LeafCount_BiTree

6.47 编写按层次顺序（同一层自左至右）遍历二叉树的算法。 或：按层次输出二叉树中所有结点

答：思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法。 这是一个循环算法，用while语句不断循环，直到队空之后自然退出该函数。

技巧之处：当根结点入队后，会自然使得左、右孩子结点入队，而左孩子出队时又会立即使得它的左右孩子结点入队，??以此产生了按层次输出的效果。 level(liuyu*T)

/* liuyu *T,*p,*q[100]; 假设max已知*/