数据结构第4单元课后练习答案.pptx

1、第四单元 树形结构对于三个结点A，B和C，可分别组成多少不同的无序树、有序树和二叉树？答：（1）无序树：9棵 （2）有序树：12棵 （3）二叉树：30棵高度为h的k叉树的特点是：第h层的节点度为0，其余结点的度均为k。如果按从上到下，从左到右的次序从1开始编号，则： 各层的结点是多少？ 编号为i的结点的双亲的编号是多少？ 编号为i的结点的第m个孩子的编号是多少？ 编号为i的结点的有右兄弟的条件是什么？答： 第i层有ki-1个 (i-1)/k k(i-1)+m+1 根据和的结果有：i k(i-1)/k-1)+k+1即： i k (i-1)/k 设对一棵二叉树进行中序遍历和后序遍历的结果分别为：

2、（1）中序遍历 B D C E A F H G （2）后序遍历 D E C B H G F A 画出该二叉树。写出下面得二叉树的遍历结果。先序：ADEHFJGBCK中序：HEJFGDABKC后序：HJGFEDKCBA设计算法，交换一棵二叉树中每个结点的左、右子树。template void BTree:Exch(BTNode *p) if (p) BTNode *q=Exch(p-lchild); p-lchild=Exch(p-rchild); p-rchild=q; 把下图中的树转换成对应的二叉树。把下图中的二叉树转换成对应的树或森林。设S=A,B,C,D,E,F，W=2,3,5,7,9,

3、12，对字符集合进行哈夫曼编码，W为各字符的频率。（1)画出哈夫曼树（2）计算带权路径长度 (3) 求各字符的编码 A:1010 B:1011 C:100 D:00 E:01 F:11设计一个递归算法，实现对一个有序表的顺序搜索。 templateint SeqList:Search4(const T& x) const elementslength=1000; return Sch4(x,0);templateint SeqList:Sch4(const T& x,int i) const if (xelementsi) return 0; else if (x=elementsi) ret

4、urn +i; else return Sch4(x,i+1);画出对长度为12的有序表进行对半查找的二叉判定树，并求等概率搜索时，成功搜索的平均搜索长度。解：1 二叉判定树如下：成功搜索的平均搜索长度 由于第i层有2i个结点，故平均搜索长度为：ASL log2(n+1)6394117112108652试证明哈夫曼算法的正确性。引理一 在Huffman树中不存在度为1的结点。证明： 假设某个二叉树T中存在度为1的结点a，a的唯一子结点为b，且以a为根的子树的所有叶结点的WPL为。 现在T中删除结点a，以结点b取代a形成一棵新的二叉树T。设以b为根的子树的所有叶结点的WPL为，则必有： 。 所以

5、，WPL(T) WPL(T)。即T不可能是Huffman树。试证明哈夫曼算法的正确性。引理二 在字母表C上，一定存在这样一棵Huffman树：权值最小的两个叶结点互为兄弟结点。证明： 假设二叉树T是字母表C上的一棵Huffman树，权值最小的两个叶结点是a和b。 根据引理一，a必有兄弟结点。假设a的兄弟结点不是b，可设为a。 容易证明a、 a与b有相同的层次，交换a与b形成一棵新的二叉树T 。 可知WPL(T)=WPL(T)。证毕。试证明哈夫曼算法的正确性。引理三 合并一棵Huffman树中权值最小的两个叶结点，将生成一棵新的Huffman树。证明： 假设二叉树T是字母表C上的一棵Huffma

6、n树，权值最小的两个叶结点是x和y，它们的权值分别是f(x)和f(y)，它们的路径长度分别是l(x)和l(y) 。 根据引理二，可假设x与y互为兄弟结点。在二叉树T中删除结点x和y，将字母z以及权值f(z)=f(x)+f(y)赋予x和y在T中的父结点，则生成一棵在字母表C=C-x,y+z上的二叉树T。 易知：l(x)=l(y)， l(z)=l(x)-1。假设T不是字母表C上的最优二叉树。可假设T是。在T中找到叶结点z，在它下面添加两个子结点x和y，形成一棵字母表C上的二叉树。可知： WPL(T)=WPL(T)-f(x)l(x)-f(y)l(y)+f(z)l(z)=WPL(T)-(f(x)+f(

7、y)l(x)+f(z)l(z) =WPL(T)-f(z)l(x)+f(z)(l(x)-1)=WPL(T)-f(x)-f(y)。 同理可知WPL(T)= WPL()-f(x)-f(y)。 由于WPL(T)WPL(T)，可得WPL()WPL(T)。这与“T是字母表C上的一棵Huffman树”的前提条件相矛盾。所以，T是字母表C上的最优二叉树。证毕。试证明哈夫曼算法的正确性。定理 分裂一棵Huffman树的某个叶结点，如果产生的两个叶结点的权值在所有叶结点权值中最小，则将生成一棵新的Huffman树。证明： 假设二叉树T是字母表C上的一棵Huffman树，z是它的一个叶节点。在z的下面添加两个子结点

8、x和y，它们的权值分别是f(x)和f(y)，且满足f(z)=f(x)+f(y)， f(x)和f(y)在字母表C =C-z+x,y上的权值最小，可设新产生的二叉树为T。 在字母表C上存在一棵最优二叉树T，在T上x和y互为兄弟结点。在T中删除结点x和y，将字母z以及权值f(z)=f(x)+f(y)赋予x和y在T中的父结点，得到一棵在字母表C上的二叉树。 根据引理三，可知是字母表C上的最优二叉树，由于T也是字母表C上的最优二叉树，所以WPL()= WPL(T)。 由于WPL()= WPL(T)-f(x)-f(y)， WPL(T)= WPL(T)-f(x)-f(y)，所以WPL(T)=WPL(T)，即，T是字母表C上的最优二叉树。证毕。补充说明：利用Huffman算法构造一棵二叉树T后，单独取出根结点和它的两个子结点，则该子树必是一棵最优二叉树。以后，按照与T的形成过程的相反的顺序依次分解各叶结点，直到再次构造出T，则依据上面的定理可知T是一棵Huffman树。试证明在哈夫曼算法的实施过程中，二叉树森林中的每一棵子树都是Huffman树。证明： 在Huffman算法进行的每一步，都会有一棵新的二叉树产生，它是合并原来森林中根结点权值最小的两棵子树而得来的。假设此二叉树为T。 取T的根为一棵独立的子树，则它是一棵Huffman树，将此结点向