《数据结构课后习题及解析》由会员分享，可在线阅读，更多相关《数据结构课后习题及解析（24页珍藏版）》请在金锄头文库上搜索。
1、第六章习题1. 试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。2. 对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。3. 已知一棵度为k的树中有ni个度为1的结点，n2个度为2的结点，；nk个度为k的结点， 则该树中有多少个叶子结点并证明之。4. 假设一棵二叉树的先序序列为 EBADCFHGIKJ中序序列为ABCDEFGHIJK请画出该二叉树。5. 已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？6. 给出满足下列条件的所有二叉树： 前序和后序相同 中序和后序相同 前序和后序相同7. n个结点的K叉树，若用具有k个child域的等长链结点存储树的一
2、个结点，则空的Child 域有多少个？8. 画出与下列已知序列对应的树T:树的先根次序访问序列为GFKDAIEBCHJ树的后根次序访问序列为DIAEKFCJHBG9 .假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为：0.07, 0.19，0.02，0.06，0.32，0.03，0.21，0.10请为这8个字母设计哈夫曼编码。10. 已知二叉树采用二叉链表存放，要求返回二叉树T的后序序列中的第一个结点指针，是否可不 用递归且不用栈来完成？请简述原因.11. 画出和下列树对应的二叉树：12已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目 13编写递归算法：对于
3、二叉树中每一个元素值为 x 的结点，删去以它为根的子树，并释放相应 的空间。14分别写函数完成：在先序线索二叉树 T中，查找给定结点*p在先序序列中的后继。在后序线 索二叉树T中，查找给定结点*p在后序序列中的前驱。15分别写出算法，实现在中序线索二叉树中查找给定结点*p 在中序序列中的前驱与后继。16编写算法，对一棵以孩子 - 兄弟链表表示的树统计其叶子的个数。17对以孩子 - 兄弟链表表示的树编写计算树的深度的算法。 18已知二叉树按照二叉链表方式存储，利用栈的基本操作写出后序遍历非递归的算法。 19设二叉树按二叉链表存放， 写算法判别一棵二叉树是否是一棵正则二叉树。 正则二叉树是指： 在
4、二叉树中不存在子树个数为 1 的结点。20计算二叉树最大宽度的算法。二叉树的最大宽度是指：二叉树所有层中结点个数的最大值。 21已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。22. 证明：给定一棵二叉树的前序序列与中序序列，可唯一确定这棵二叉树；给定一棵二叉树的后序序列与中序序列，可唯一确定这棵二叉树；23. 二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。24. 二叉树按照二叉链表方式存储，编写算法，将二叉树左右子树进行交换。实习题1. 问题描述 建立一棵用二叉链表方式存储的二叉树， 并对其进行遍历（先序、中序和后序），打印输出遍历结果。 基
5、本要求 从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立） 并对其进行遍历（先序、中序、后序），然后将遍历结果打印输出。要求采用递归和非递归两种 方法实现。测试数据ABC巾巾D邱G巾巾F巾巾巾（其中巾表示空格字符）输出结果为： 先序： ABCDEGF中序： CBEGDFA后序： CGBFDBA2已知二叉树按照二叉链表方式存储， 编写算法， 要求实现二叉树的竖向显示 （竖向显示就是二 叉树的按层显示）。3如题1要求建立好二叉树，按凹入表形式打印二叉树结构，如下图所示0FEADB【解答】设树中结点总数为n,则n=no + ni + rk2. 按凹入表形式打印树形结构，如下图
6、所示ABEFCGD第六章答案6.1分别画出具有3个结点的树和3个结点的二叉树的所有不同形态【解答】具有3个结点的树具有3个结点的二叉树6.3已知一棵度为k的树中有ni个度为1的结点，n2个度为2的结点，,nk个度为k的结点, 则该树中有多少个叶子结点？树中分支数目为B,贝U B=ni + 2n2 + 3n3 + + knk因为除根结点外，每个结点均对应一个进入它的分支，所以有n= B + 1即 no + ni + + nk = ni + 2n2 + 3n3 + + knk + 1由上式可得叶子结点数为：no = n2 + 2n3 + + (k-1) nk + 16.5 已知二叉树有 5o 个叶
7、子结点，贝该二叉树的总结点数至少应有多少个？【解答】no表示叶子结点数，n2表示度为2的结点数，贝U no = n2+1所以n2= no -1=49，当二叉树中没有度为1的结点时，总结点数n=no+n2=996.6 试分别找出满足以下条件的所有二叉树 :(1) 前序序列与中序序列相同 ;(2) 中序序列与后序序列相同 ;(3) 前序序列与后序序列相同。【解答】(1) 前序与中序相同：空树或缺左子树的单支树；(2) 中序与后序相同：空树或缺右子树的单支树；(3) 前序与后序相同：空树或只有根结点的二叉树。6.9 假设通讯的电文仅由 8 个字母组成，字母在电文中出现的频率分别为：o.o7， o.1
8、9， o.o2， o.o6， o.32， o.o3， o.21， o.1o 请为这 8 个字母设计哈夫曼编码。【解答】构造哈夫曼树如下：1ID1610.210.280.1n.n0 .05n io0.020.1P0.03:11111丨5： 1100I 2： 11110丨6： 10:1110I 7 : 01:1101I 8: 00O.Ofi0.07哈夫曼编码为:III1346.11画出如下图所示树对应的二叉树【解答】(a)BC(b)AD0(06.15分别写出算法，实现在中序线索二叉树 T中查找给定结点*p在中序序列中的前驱与后继。 在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。在后序线
9、索二叉树T中，查找给 定结点*p在后序序列中的前驱。(1)找结点的中序前驱结点BiTNode *ln Pre (BiTNode *p)/*在中序线索二叉树中查找p的中序前驱结点，并用pre指针返回结果*/ if (p-Ltag= =1) pre = p-LChild; /*直接利用线索 */else/*在p的左子树中查找“最右下端”结点*/for ( q=p-LChild; q-Rtag= =0; q=q-RChild);pre = q;return (pre);2)找结点的中序后继结点BiTNode *InSucc (BiTNode *p)/*在中序线索二叉树中查找 p 的中序后继结点，并用
10、 succ 指针返回结果 */ if (p-Rtag= =1) succ = p-RChild; /* 直接利用线索 */else/*在 p 的右子树中查找“最左下端”结点 */for ( q=p-RChild; q-Ltag= =0; q=q-LChild);succ= q;return (succ);(3) 找结点的先序后继结点BiTNode *PreSucc (BiTNode *p)/*在先序线索二叉树中查找 p 的先序后继结点，并用 succ 指针返回结果 */ if (p-Ltag= =0) succ = p-LChild;else succ= p-RChild;return (su
11、cc);(4) 找结点的后序前驱结点BiTNode *SuccPre (BiTNode *p)/*在后序线索二叉树中查找 p 的后序前驱结点，并用 pre 指针返回结果 */ if (p-Ltag= =1) pre = p-LChild;else pre= p-RChild;return (pre);6.21 已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法解答】Void PreOrder(BiTree root) /*先序遍历二叉树的非递归算法 */InitStack(&S);p=root;while(p!=NULL | !IsEmpty(S) ) if(p!=N
12、ULL)Visit(p-data);push(&S,p);p=p-Lchild;elsePop(&S,&p);p=p-RChild;6.24 已知二叉树按照二叉链表方式存储，编写算法，将二叉树左右子树进行交换【解答】算法(一)Void exchange ( BiTree root )p=root;if ( p-LChild != NULL | p-RChild != NULL )temp = p-LChild;p-LChild = p-RChild;p-RChild = temp;exchange ( p-LChild );exchange ( p-RChild );算法(二)Void exc
13、hange ( BiTree root )p=root;if ( p-LChild != NULL | p-RChild != NULL )exchange ( p-LChild );exchange ( p-RChild );temp = p-LChild;p-LChild = p-RChild;p-RChild = temp;第六章 习题解析1试分别画出具有 3 个结点的树和 3 个结点的二叉树的所有不同形态2对题 1 所得各种形态的二叉树，分别写出前序、中序和后序遍历的序 列。3 .已知一棵度为k的树中有ni个度为1的结点，“2个度为2的结点，nk 个度为 k 的结点，则该树中有多少个叶子结点？提示：参考 P.116 性质 3n=n + ni + +nkB=n i + 2n 2 + 3n 3 + +kn kn= B + in + n i + +n k = n i + 2n 2 + 3n 3 + + kn k + 1n = n 2 + 2n 3 + + （k-i）n k + i4.假设一棵二叉树的先序序列为EBADCFHGIKJ ，中序序列为ABCDEFGHIJK ，请画出该二叉树。提示：参考 P.i486 已知二叉树有 50 个叶子结点，则该二叉树的总结点数至少应有多 少个？提示：方法 i（i ）一个叶子结点，总结点数 至多 有多少个？结论：可压
