资源预览内容
第1页 / 共24页
第2页 / 共24页
第3页 / 共24页
第4页 / 共24页
第5页 / 共24页
第6页 / 共24页
第7页 / 共24页
第8页 / 共24页
第9页 / 共24页
第10页 / 共24页
亲,该文档总共24页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第六章习题1. 试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。2. 对题1所得各种形态的二叉树,分别写出前序、中序和后序遍历的序列。3. 已知一棵度为k的树中有ni个度为1的结点,n2个度为2的结点,;nk个度为k的结点, 则该树中有多少个叶子结点并证明之。4. 假设一棵二叉树的先序序列为 EBADCFHGIKJ中序序列为ABCDEFGHIJK请画出该二叉树。5. 已知二叉树有50个叶子结点,则该二叉树的总结点数至少应有多少个?6. 给出满足下列条件的所有二叉树: 前序和后序相同 中序和后序相同 前序和后序相同7. n个结点的K叉树,若用具有k个child域的等长链结点存储树的一个结点,则空的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编写递归算法:对于二叉树中每一个元素值为 x 的结点,删去以它为根的子树,并释放相应 的空间。14分别写函数完成:在先序线索二叉树 T中,查找给定结点*p在先序序列中的后继。在后序线 索二叉树T中,查找给定结点*p在后序序列中的前驱。15分别写出算法,实现在中序线索二叉树中查找给定结点*p 在中序序列中的前驱与后继。16编写算法,对一棵以孩子 - 兄弟链表表示的树统计其叶子的个数。17对以孩子 - 兄弟链表表示的树编写计算树的深度的算法。 18已知二叉树按照二叉链表方式存储,利用栈的基本操作写出后序遍历非递归的算法。 19设二叉树按二叉链表存放, 写算法判别一棵二叉树是否是一棵正则二叉树。 正则二叉树是指: 在二叉树中不存在子树个数为 1 的结点。20计算二叉树最大宽度的算法。二叉树的最大宽度是指:二叉树所有层中结点个数的最大值。 21已知二叉树按照二叉链表方式存储,利用栈的基本操作写出先序遍历非递归形式的算法。22. 证明:给定一棵二叉树的前序序列与中序序列,可唯一确定这棵二叉树;给定一棵二叉树的后序序列与中序序列,可唯一确定这棵二叉树;23. 二叉树按照二叉链表方式存储,编写算法,计算二叉树中叶子结点的数目。24. 二叉树按照二叉链表方式存储,编写算法,将二叉树左右子树进行交换。实习题1. 问题描述 建立一棵用二叉链表方式存储的二叉树, 并对其进行遍历(先序、中序和后序),打印输出遍历结果。 基本要求 从键盘接受输入先序序列,以二叉链表作为存储结构,建立二叉树(以先序来建立) 并对其进行遍历(先序、中序、后序),然后将遍历结果打印输出。要求采用递归和非递归两种 方法实现。测试数据ABC巾巾D邱G巾巾F巾巾巾(其中巾表示空格字符)输出结果为: 先序: ABCDEGF中序: CBEGDFA后序: CGBFDBA2已知二叉树按照二叉链表方式存储, 编写算法, 要求实现二叉树的竖向显示 (竖向显示就是二 叉树的按层显示)。3如题1要求建立好二叉树,按凹入表形式打印二叉树结构,如下图所示0FEADB【解答】设树中结点总数为n,则n=no + ni + rk2. 按凹入表形式打印树形结构,如下图所示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 个叶子结点,贝该二叉树的总结点数至少应有多少个?【解答】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.19, 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在先序序列中的后继。在后序线索二叉树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 的中序后继结点,并用 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 (succ);(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!=NULL)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 exchange ( 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 )一个叶子结点,总结点数 至多 有多少个?结论:可压
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号