2022年数据结构课后习题及解析六.docx

精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用第六章习题1试分别画出具有 3 个结点的树和 3 个结点的二叉树的全部不同形状；2对题 1 所得各种形状的二叉树,分别写出前序、中序和后序遍历的序列；3已知一棵度为 k 的树中有 n1个度为 1 的结点, n2 个度为 2 的结点, ,nk个度为 k 的结点,就该树中有多少个叶子结点并证明之；4. 假设一棵二叉树的先序序列为EBADCFHGIKJ,中序序列为 ABCDEFGHIJK,请画出该二叉树；5已知二叉树有 50 个叶子结点,就该二叉树的总结点数至少应有多少个？6给出满意以下条件的全部二叉树：前序和后序相同域的等长链结点储备树的一个结点,就空的Child中序和后序相同前序和后序相同7 n 个结点的 K 叉树,如用具有 k 个 child域有多少个？8画出与以下已知序列对应的树：树的先根次序拜访序列为 GFKDAIEBCHJ树的后根次序拜访序列为 DIAEKFCJHBG9假设用于通讯的电文仅由 8 个字母组成,字母在电文中显现的频率分别为：0.07 ,0.19 ,0.02 ,0.06 ,0.32 ,0.03 ,0.21 ,0.10 请为这 8 个字母设计哈夫曼编码；10已知二叉树采纳二叉链表存放, 要求返回二叉树 T 的后序序列中的第一个结点指针, 是否可不用递归且不用栈来完成 .请简述缘由 .11. 画出和以下树对应的二叉树：名师归纳总结 - - - - - - -第 1 页,共 19 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用12已知二叉树根据二叉链表方式储备,编写算法,运算二叉树中叶子结点的数目；13编写递归算法：对于二叉树中每一个元素值为 的空间；x 的结点,删去以它为根的子树,并释放相应14分别写函数完成：在先序线索二叉树 T 中,查找给定结点 *p 在先序序列中的后继；在后序线索二叉树 T 中,查找给定结点 *p 在后序序列中的前驱；15分别写出算法,实现在中序线索二叉树中查找给定结点*p 在中序序列中的前驱与后继；16编写算法,对一棵以孩子- 兄弟链表表示的树统计其叶子的个数；17对以孩子 - 兄弟链表表示的树编写运算树的深度的算法；18已知二叉树根据二叉链表方式储备,利用栈的基本操作写出后序遍历非递归的算法；19设二叉树按二叉链表存放,写算法判别一棵二叉树是否是一棵正就二叉树；正就二叉树是 指：在二叉树中不存在子树个数为 1 的结点；20运算二叉树最大宽度的算法；二叉树的最大宽度是指：二叉树全部层中结点个数的最大值；21已知二叉树根据二叉链表方式储备,利用栈的基本操作写出先序遍历非递归形式的算法；22. 证明：给定一棵二叉树的前序序列与中序序列,可唯独确定这棵二叉树；给定一棵二叉树的后序序列与中序序列,可唯独确定这棵二叉树；23. 二叉树根据二叉链表方式储备,编写算法,运算二叉树中叶子结点的数目；24. 二叉树根据二叉链表方式储备,编写算法,将二叉树左右子树进行交换；实习题1. 问题描述 建立一棵用二叉链表方式储备的二叉树,并对其进行遍历<先序、中序和后序）,打印输出遍历结果；名师归纳总结 - - - - - - -第 2 页,共 19 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用 基本要求 从键盘接受输入先序序列,以二叉链表作为储备结构,建立二叉树 <以先序来建立）并对其进行遍历 <先序、中序、后序）,然后将遍历结果打印输出；要求采纳递归和非递归两种 方法实现； 测试数据 ABC DE G F <其中 表示空格字符）输出结果为：先序： ABCDEGF 中序： CBEGDFA 后序： CGBFDBA 2已知二叉树根据二叉链表方式储备,编写算法,要求实现二叉树的竖向显示 <竖向显示就是二 叉树的按层显示）；3如题 1 要求建立好二叉树,按凹入表形式打印二叉树结构,如下图所示；2. 按凹入表形式打印树形结构,如下图所示；第六章答案61 分别画出具有 3 个结点的树和 3 个结点的二叉树的全部不同形状；名师归纳总结 - - - - - - -第 3 页,共 19 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用【解答】具有 3 个结点的树 具有 3 个结点的二叉树6.3 已知一棵度为 k 的树中有 n1 个度为 1 的结点, n2 个度为 2 的结点, ,nk 个度为 k 的结点,就该树中有多少个叶子结点？【解答】设树中结点总数为 n,就 n=n 0 + n1 + + nk树中分支数目为 B,就 B=n 1 + 2n 2 + 3n 3 + + knk由于除根结点外,每个结点均对应一个进入它的分支,所以有 n= B + 1即 n0 + n 1 + + n k = n1 + 2n 2 + 3n 3 + + knk + 1由上式可得叶子结点数为：n0 = n2 + 2n 3 + + k-1>n k + 16.5 已知二叉树有 50 个叶子结点,就该二叉树的总结点数至少应有多少个？【解答】 n0 表示叶子结点数, n2 表示度为 2 的结点数,就 n0 = n2+1所以 n2=n 0 1=49,当二叉树中没有度为:1 的结点时,总结点数n=n 0+n2=996.6 试分别找出满意以下条件的全部二叉树1> 前序序列与中序序列相同；2> 中序序列与后序序列相同；3> 前序序列与后序序列相同；【解答】 1> 前序与中序相同：空树或缺左子树的单支树； 2> 中序与后序相同：空树或缺右子树的单支树； 3> 前序与后序相同：空树或只有根结点的二叉树；8 个字母组成,字母在电文中显现的频率分别为：6.9 假设通讯的电文仅由 0.07 ,0.19 ,0.02 ,0.06,0.32,0.03,0.21 ,0.10 请为这 8 个字母设计哈夫曼编码；【解答】名师归纳总结 - - - - - - -第 4 页,共 19 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用构造哈夫曼树如下：哈夫曼编码为：I1：11111 I5：1100I 2：11110 I 6：10I 3：1110 I 7： 01I 4：1101 I 8： 006.11 画出如下图所示树对应的二叉树；【解答】名师归纳总结 - - - - - - -第 5 页,共 19 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用6.15 分别写出算法,实现在中序线索二叉树T 中查找给定结点 *p 在中序序列中的前驱与后继；在先序线索二叉树T 中,查找给定结点 *p 在先序序列中的后继；在后序线索二叉树T 中,查找给定结点 *p 在后序序列中的前驱；<1）找结点的中序前驱结点 BiTNode *InPre 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> ；名师归纳总结 - - - - - - -第 6 页,共 19 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用<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> ；名师归纳总结 - - - - - - -第 7 页,共 19 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用 6.21 已知二叉树根据二叉链表方式储备,利用栈的基本操作写出先序遍历非递归形式的算法；【解答】Void PreOrderBiTree root> /*先序遍历二叉树的非递归算法*/ InitStack&S> ； p=root ； whilep.=NULL | .IsEmptyS> > ifp.=NULL> Visitp->data> ；push&S,p> ；p=p->Lchild ； else Pop&S,&p> ； p=p->RChild ； 6.24 已知二叉树根据二叉链表方式储备,编写算法,将二叉树左右子树进行交换；【解答】算法 一> Void exchange BiTree root > p=root ；名师归纳总结 - - - - - - -第 8 页,共 19 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用 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； 第六章 习题解读名师归纳总结 - - - - - - -第 9 页,共 19 页精选学习资料 - - - - - - - - - 1试分别画出具有3 个结点的树和个人资料整理仅限学习使用3 个结点的二叉树的全部不同形态；2对题 1 所得各种形状的二叉树,分别写出前序、中序和后序遍历的序列；3已知一棵度为 k 的树中有 n 1 个度为 1 的结点, n2 个度为 2 的结 点, ,n k 个度为 k 的结点,就该树中有多少个叶子结点？提示 ：参考 P.116 性质 3n=n 0 + n 1 + + n kB=n 1 + 2n 2 + 3n 3 + + kn kn= B + 1 n 0 + n 1 + + nk = n 1 + 2n 2 + 3n 3 + + kn k + 1 n 0 = n 2 + 2n 3 + + k-1>n k + 14.假设一棵二叉树的先序序列为 EBADCFHGIKJ,中序序列为ABCDEFGHIJK,请画出该二叉树；提示 ：参考 P.148 6已知二叉树有50 个叶子结点,就该二叉树的总结点数至少应有多少个？提示 ：方法 1名师归纳总结 - - - - - - -第 10 页,共 19 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用<1）一个叶子结点,总结点数至多 有多少个？结论：可压缩 一度 结点；<2）满二叉树或完全二叉树具有最少的 一度 结点 <3）可能的最大满二叉树是几层？有多少叶结点？如何增补？2 5<50<2 6可能的最大满二叉树是 6 层 有 25 = 32 个叶结点假设将其中x 个变为 2 度结点后,总叶结点数目为50就： 2x + 32 x> = 50 得： x = 18此时总结点数目= 26 1> + 18 × 2方法 2 假设完全二叉树的最大非叶结点编号为 m ,就最大叶结点编号为 2m+1,2m+1>-m=50 m=49 总结点数目 =2m+1=99名师归纳总结 - - - - - - -第 11 页,共 19 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用方法 3 由性质 3：n 0=n 2+1 即： 50=n 2+1 所以： n 2=49 令 n1=0 得： n= n 0 + n 2=99 7给出满意以下条件的全部二叉树：a> 前序和中序相同 b> 中序和后序相同 c> 前序和后序相同 提示 ：去异存同；a> D L R 与 L D R 的相同点： D R ,假如无 L,就完全相同 , 假如无 LR , ；b> L D R 与 L R D 的相同点： L D ,假如无 R,就完全相同；c> D LR 与 LR D 的相同点： D,假如无 L R ,就完全相同；<假如去 D,就为空树）7 n 个结点的 K 叉树,如用具有 k 个 child 域的等长链结点储备树的 一个结点,就空的 Child 域有多少个？提示 ：参考 P.119 名师归纳总结 - - - - - - -第 12 页,共 19 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用8画出与以下已知序列对应的树：树的先根次序拜访序列为GFKDAIEBCHJ；树的后根次序拜访序列为DIAEKFCJHBG；提示 ：<1）先画出对应的二叉树<2）树的后根序列与对应二叉树的中序序列相同9假设用于通讯的电文仅由 分别为：8 个字母组成,字母在电文中显现的频率0.07 ,0.19 ,0.02 ,0.06 ,0.32 , 0.03 ,0.21 ,0.10<1）请为这 8 个字母设计哈夫曼编码,<2）求平均编码长度；10已知二叉树采纳二叉链表存放 ,要求返回二叉树 T 的后序序列中的第一个结点的指针 ,是否可不用递归且不用栈来完成 .请简述缘由 .提示 ：无右子的“ 左下端”11. 画出和以下树对应的二叉树：名师归纳总结 - - - - - - -第 13 页,共 19 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用12已知二叉树根据二叉链表方式储备,编写算法,运算二叉树中叶子结点的数目；13编写递归算法：对于二叉树中每一个元素值为 为根的子树,并释放相应的空间；提示 ：x 的结点,删去以它方法 1：<1）按先序查找；<2）超前查看子结点<3）按后序释放；voidDelSubTreeBiTree *bt, DataType x> if *bt .= NULL && *bt> ->data=x > FreeTree *bt> ；*bt =NULL ； else DelTree *bt, x>名师归纳总结 - - - - - - -第 14 页,共 19 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用void DelTree BiTreebt, DataType x> if bt > if bt->LChild && bt->LChild->data=x> FreeTree bt->LChild>； bt->LChild=NULL； if bt->RChild && bt->RChild->data=x> FreeTree bt->RChild>； bt->RChild=NULL；DelTree bt->LChild, x>；DelTree bt->RChild, x>；名师归纳总结 - - - - - - -第 15 页,共 19 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用方法 2：<1）先序查找； <2）直接查看 当前根 结点 <3）用 指针参数 ；方法 3：<1）先序查找； <2）直接查看 当前根 结点<3）通过 函数 值,返回 删除后结果 ；<参示例程序）14分别写函数完成：在先序线索二叉树 T 中,查找给定结点 *p 在先序序列中的后继；在后序线索二叉树 T 中,查找给定结点 *p 在后序序列中的前驱；提示 ：<1）先查看线索,无线索时用下面规律：<2）结点 *p 在先序序列中的后继为其左子或右子；<3）结点 *p 在后序序列中的前驱也是其左子或右子；15分别写出算法,实现在中序线索二叉树中查找给定结点 *p 在中序序列中的前驱与后继；<参例题）16编写算法,对一棵以孩子 提示 ：-兄弟链表表示的树统计其叶子的个数；<1）可将 孩子 -兄弟链表 划分为 根、首子树 、兄弟树 ,递归处理；<2）可利用 返回值 ,或 全局变量 ；名师归纳总结 - - - - - - -第 16 页,共 19 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用17对以孩子 -兄弟链表表示的树编写运算树的深度的算法；18已知二叉树根据二叉链表方式储备,利用栈的基本操作写出后序遍 历非递归的算法；<参课本）19设二叉树按二叉链表存放,写算法判别一棵二叉树是否是一棵正就 二叉树；正就二叉树是指：在二叉树中不存在子树个数为 1 的结点；提示 ：可利用任何递归、非递归遍历算法；20运算二叉树最大宽度的算法；二叉树的最大宽度是指：二叉树全部 层中结点个数的最大值；21已知二叉树根据二叉链表方式储备,利用栈的基本操作写出先序遍 历非递归形式的算法；22. 证明：给定一棵二叉树的前序序列与中序序列,可唯独确定这棵二 叉树；给定一棵二叉树的后序序列与中序序列,可唯独确定这棵二叉树；名师归纳总结 - - - - - - -第 17 页,共 19 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用 23. 二叉树根据二叉链表方式储备,编写算法将二叉树左右子树进行交 换；实习题1.建立一棵用二叉链表方式储备的二叉树,并对其进行遍历问题描述 <先序、中序和后序）,打印输出遍历结果；基本要求 从键盘接受输入先序序列,以二叉链表作为储备结构,建立二叉树 <以先序来建立）并对其进行遍历<先序、中序、后序）,然后将遍历结果打印输出；要求采纳递归和非递归两种方法实现；测试数据 ABC DE G F <其中 表示空格字符）输出结果为：先序：ABCDEGF 中序： CBEGDFA 后序： CGBFDBA 2已知二叉树根据二叉链表方式储备,编写算法,要求实现二叉树的 竖向显示 <竖向显示就是二叉树的按层显示）；提示 ：<1）参习题 6.20 ,实现逐层遍历名师归纳总结 - - - - - - -第 18 页,共 19 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用<2）队中储存每个结点的打印位置,其左、右子的距离3如题 1 要求建立好二叉树,按凹入表形式打印二叉树结构,如图6.34 所示；图6.344按凹入表形式打印树形结构,如图 6.35 所示；提示 ：参 P.129 例,用先根遍历；名师归纳总结 - - - - - - -第 19 页,共 19 页