1、计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 2 及答案与解析一、单项选择题1 一棵二又树的前序遍历序列为 1234567，它的中序遍历序列可能是_。【北京工业大学 2001 年】（A）3124567（B） 1234567（C） 4135627（D）14365722 已知一棵二叉树的前序遍历结果为 123456，中序遍历结果为 321546，则后序遍历的结果为_。【哈尔滨工程大学 2001 年】（A）325641（B） 654321（C） 325461（D）不定3 己知某二叉树的后序遍历序列是 dabec，中序遍历序列是 debac，它的前序遍历序列是_。【山东大学 2001 年】
2、（A）acbed（B） decab（C） deabc（D）cedba4 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是_。【北京交通大学 2005 年】（A）空或只有一个结点（B）高度等于其结点数（C）任一结点无左孩予（D）任一结点无右孩子5 某二叉树结点的中序序列为 BDAECF，后序序列为 DBEFCA，则该二叉树对应的森林包括_棵树。【中南大学 2003 年】（A）1（B） 2（C） 3（D）46 若唯一的确定一棵二叉树，只需要知道该二叉树的_。【北京交通大学 2004年】（A）先序序列（B）中序序列（C）中序和后序序列（D）先序和后序序列7 在二叉树结点的先序序列、中序序列和后
3、序序列中，所有叶子结点的先后顺序_。【北京交通大学 2001 年】（A）都不相同（B）完全相同（C）先序和中序相同，而与后序不同（D）中序和后序相同，而与先序不同8 引入二叉线索树的目的是_。【南京理工大学 1998 年】（A）加快查找结点的前驱或后继的速度（B）为了能在二叉树中方便地进行插入与删除（C）为了能方便地找到双亲（D）使二叉树的遍历结果唯一9 二叉树在线索化后，仍不能有效求解的问题是_。【北京交通大学 2003 年】（A）先序线索二叉树中求先序后继（B）中序线索二叉树中求中序后继（C）中序线索二叉树中求中序前驱（D）后序线索二叉树中求后序后继10 若 x 是二叉中序线索树中一个有左
4、孩子的结点，且 X 不为根，则 x 的前驱为_。【南京理工大学 1996 年】（A）X 的双亲（B） X 的右子树中最左结点（C） X 的左子树中最右结点（D）X 的左了树中最右叶结点11 n 个结点的线索二叉树上含有的线索数为_。【中山大学 1998 年】（A）2n（B） n-1（C） n+1（D）n12 _的遍历仍需要栈的支持。【中南大学 2001 年】（A）前序线索树（B）中序线索树（C）后序线索树（D）所有线索树13 在二叉排序树中进行查找的效率与_有关。【北京航空航天大学 2004 年】（A）二叉排序树的深度（B）二叉排序树的结点的个数（C）被查找结点的度（D）二叉排序树的存储结构1
5、4 对一棵二叉排序树进行_遍历得到的结点序列是个有序序列。【湖南大学2001 年】（A）前序（B）中序（C）后序（D）层次15 对于二叉排序树，下面的说法_是正确的。【华南理工大学 2006 年】（A）二叉排序树是动态树表，查找不成功时插入新结点时，会引起树的重新分裂和组合（B）对二叉排序树进行层次遍历可得到有序序列（C）用逐点插入法构造二叉排序树时，若先后插入的关键字有序，二叉排序树的深度最大（D）在二叉排序树中进行查找，关键字的比较次数不超过结点数的 1216 分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是_。【合肥工业大学 2000 年】（A）(100 ，80，90，
6、60，120，110，130)（B） (100，120，110，130，80，60，90)（C） (100，60，80，90，120，110，130)（D）(100 ，80，60，90，120，130，110)17 设二叉排序树中关键字由 11000 的整数构成，现要查找关键字为 363 的结点，下述关键字序列中，不可能是在二叉排序树上查找的序列是_。【北京交通大学2005 年】（A）2，252，401，398，330，344，397，363（B） 924，220，911，244，898，258，362，363（C） 925，202，911，240，912，245，363（D）2，399，38
7、7，219，266，382，381，278， 36318 构造一棵具有 n 个结点的二叉排序树，最理想情况下的深度为_。【华中科技大学 2007 年】（A）n2（B） n（C） log2(n+1)（D）log 2(n+1)19 从空树开始，依次插入元素 52、26、14、32、71、60、93、58、24 和 41 后构成了一棵二叉排序树。在该树查找 60 要进行比较次数为_。【广东工业大学2003 年】（A）3（B） 4（C） 5（D）620 含有 20 个结点的平衡二叉树的最大深度为_。【北京交通大学 2004 年】（A）4（B） 5（C） 6（D）721 在平衡二叉树中插入一个结点后造成
8、了不平衡，设最低的不平衡结点为 A，并已知 A 的左孩子的平衡因子为 0、右孩子的平衡因子为 1，则应作_型调整以使其平衡。【北京交通大学 2005 年】（A）LL（B） LR（C） RL（D）RR22 已知一棵深度为 k 的平衡二叉树，其每个非叶子结点的平衡因子均为 0，则该树共有结点总数为_。【北京交通大学 2006 年】（A）2 k-1 一 1（B） 2k-1+1（C） 2k1（D）2 k 十 123 在下列存储形式中，哪一个不是树的存储形式?_。【北京交通大学 2001 年】（A）双亲表示法（B）孩子链表表示法（C）孩子兄弟表示法（D）顺序存储表示法24 设森林 F 对应的二叉树为 B
9、，它有 m 个结点，B 的根为 p，p 的右子树结点个数为 n，森林 F 中第一棵树的结点个数是 _。【南京理工大学 2000 年】（A）mn（B） mn 一 1（C） n+1（D）条件不足，无法确定25 森林 T=(T1，T2 ，Tm)转化为二叉树 BT 的过程为：若 m=0，则 BT 为空；若 m0，则_。【太原科技大学 2006 年】（A）将中间子树 Tmid(mid=(1 十 m)2)的根作为 BT 的根；将(T1，T2，Tmid1)转换为 BT 的左子树：将(Tmid 十，Tm)转换为 BT 的右子树（B）将子树 T1 的根作为 BT 的根；将 T1 的子树森林转换成 BT 的左子树
10、；将(T2，T3，Tm) 转换成 BT 的右子树（C）将子树 T1 的根作为 BT 的根；将 T1 的左子树森林转换成 BT 的左子树：将T1 的右子树森林转换为 BT 的右子树；其他依次类推（D）将森林 T 的根作为 BT 的根；将(T1，T2 ，Tm)转化为该根下的结点，得到一棵树，然后将这棵树再转化为二叉树 BT26 在有 n 个叶予结点的赫夫曼树中，非叶子结点的总数为_。【中南大学 2003年】（A）n-1（B） n（C） 2n 一 1（D）2n27 有 n 个叶子的赫夫曼树的结点总数为_。【青岛大学 2002 年】（A）不确定（B） 2n（C） 2n+1（D）2n128 一棵赫大曼树
11、共有 215 个结点，对其进行赫夫曼编码，共能得到_个不同的码字。【北京邮电大学 2005 年】（A）107（B） 108（C） 214（D）21529 下列编码中_不是前缀码。【湖南大学 2003 年】（A）00 ，01 ，10，11（B） 0，1，00，11（C） 0，10，110，111（D）10 ，110 ，1110，111130 给定整数集合3，5， 6，9，12 ，与之对应的赫夫曼树是 _。【华南理工大学 2007 年】（A）（B）（C）（D）二、综合题31 一棵二叉树以二叉链表来表示，求其指定的某一层 k(k1)上的叶予结点的个数。【上海大学 1999 年】32 设一棵二叉树中各
12、结点的值互不相同，其前序序列和中序序列分别存于两个一维数组 preLn 和 midL,n中，试遍写算法建立该二叉树的二叉链表。【南京航空航天大学 1999】33 已知一具有 n 个结点的二叉树的中序遍历序列与后序遍历序列分别存放于数组INL,n和 POSTLn中(设该二叉树各结点的数据值均不相同)。请写一建立该二叉树的二叉链表结构的非递归算法。该二叉链表的链结点结构为(lchild， data，rchild)，其中 data 为数据域，lchild 与 rchild 分别为指向该结点左、右孩子的指针域(当孩子结点不存在时，相应指针域为空，用 NULL 表示)。【北京航空航天大学 2003 年】
13、34 写出中序线索二叉树的线索化过程(已知二叉树 T)。【山东大学 2000 年】35 已知一中序线索二叉树，写一算法完成对它的中序扫描。【山东大学 2001 年】36 编写程序段，利用中序全线索树求其中任意结点 p 的前序后继结点，结果仍用p 指出。设线索树不带头结点，其中序序列第一个结点的左标志和最后一个结点的右标志皆为 0(非线索) ，对应指针皆为空。【北京工业大学 2000 年】37 写出在中序线索二叉树里查找指定结点在后序下的前驱结点的算法。【河海大学 1998 年】38 已知中序线索二叉树 T 的右予树不空。设计算法，将 s 所指的结点作为 T 的右子树中的一个叶子结点插入进去，并
14、使之成为 T 的右子树 (中序序列)的第一个结点(同时要修改相应的线索关系)。【合肥工业大学 2001 年】39 二叉树排序方法如下：1)将第一个数据放在树根。2)将随后读入的数据与树根中的数据相比较，若比树根大，则置于右子树，反之则置于左子树，建成一棵二叉树。3) 利用中序遍历打印排序结果。4)试用 PASCAL 或 C 语言编写二叉树的排序程序。【浙江大学 1995 年】40 编程求以孩予一兄弟表示法存储的森林的叶了结点数。要求描述结构。【北京工业大学 2000 年】【北京交通大学 2007】41 以孩予一兄弟链表为存储结构，请设计递归和非递归算法求树的深度。【北方交通大学 1999 年】
15、42 将由图 3-2 所示的三棵树组成的森林转换为二叉树。(只要求给出转换结果)【南京航空航天大学 1998 年】43 已知一个森林的先序序列和后序序列如下，请构造出该森林。1)先序序列：ABCDEFGHIJKLMNO。2)后序序列：CDEBFHIJGAMLONK。【合肥工业大学 2000 年】44 假定用于通信的电文仅有 8 个字母 C1，C2，C8 组成，各个字母在电文中出现的频率分别为 5，25，3，6，10，11，36，4，试为这 8 个字母设计赫夫曼编码。【上海海事大学 1998 年】45 给定集合15，3，14， 2，6，9，16，17 。1)用口表示外部结点，用。表示内部结点，构
16、造相应的 Huffman 树。2)计算它的带权路径长度。3)写出它的 Huffman 编码。【山东大学 1998 年】计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 2 答案与解析一、单项选择题1 【正确答案】 B【试题解析】 考杏二叉树的遍历序列。由题可得 1 为根结点，并且 2 为 1 的孩子结点。对于 A 选项，3 应为 1 的左孩子，前序遍历序列应为 13，不符。对于 B选项，当 2 为 1 的右孩子，3 为 2 的右孩子时满足题目要求。对于 C 选项，类似 A 选项，前序遍历序列应该为 14。对于 D 选项，若 1 为中序第一个字母，则所有结点在 1 的右子树中，右子树根结
17、点为 2，而 34 在 2 的左子树中，567 在 2 的右子树中才可满足前序序列，与中序遍历序列不符。【知识模块】 树和二叉树2 【正确答案】 A【试题解析】 考查由二叉树前序遍历序列和中序遍历序列建造二叉树的方法。因为前序序列中 1 开头，所以根结点为 1。由中序序列可知 1 的左子树中含有 23，右子树中含有 456。再根据前序序列可知，2 为 3 的父结点，4 为 56 的父结点。又由中序序列可知 3 为 2 的左孩子，5 为 4 的左孩子，6 为 4 的右孩子。画出二叉树如图 33 所示，可知后序遍历的结果。【知识模块】 树和二叉树3 【正确答案】 D【试题解析】 考查由后序遍历序列
18、和中序遍历序列建立二叉树的方法。类似上题的方法，后序序列最后一个为根结点。所以 C 为根结点，根据中序序列得知 deba都在 c 的左子树内。然后由后序序列可知 e 为 c 左子树的根结点，由中序序列可知d 为 e 的左孩予，ba 为 e 的右子树。再次分析可知 a 为 b 的右孩子。过程如图 3-4所示。【知识模块】 树和二叉树4 【正确答案】 B【试题解析】 考查根据二叉树的遍历序列推导树形。由题可得，非空树的先序和后序相反，即“根左右”与“左右根”顺序相反，因此树只有根结点，或者根结点只有左子树或右子树，依此类推，其子树有同样的性质，任意结点只能有一个孩子，才能满足先序序列和后序序列正好
19、相反。树形应该为一个长链，所以选 B。【知识模块】 树和二叉树5 【正确答案】 C【试题解析】 考查根据遍历序列推导树形以及森林的二叉树表示。根据中序以及后序序列推导树形如图 35 所示。该二叉树表示一个有三棵树的森林，其根结点分别为 A、C、F。【知识模块】 树和二叉树6 【正确答案】 C【试题解析】 考查确定二叉树所需的序列。前序序列和中序序列或后序序列和中序序列可唯一确定一棵二叉树。由前序序列和后序序列不能唯一确定一棵二叉树。【知识模块】 树和二叉树7 【正确答案】 B【试题解析】 考查二叉树遍历中叶子结点的先后顺序。由于左子树的访问始终在右子树之前，所以不管采用何种遍历方式，所有叶子结
20、点被访问的前后顺序是不变的。【知识模块】 树和二叉树8 【正确答案】 A【试题解析】 考查引入二又线索树的目的。为充分利用二叉树的空链域，且加快查找结点的前驱或后继速度，故引入了二叉线索树。【知识模块】 树和二叉树9 【正确答案】 D【试题解析】 考查线索化不能解决的问题。后序线索二叉树中不能有效解决求后序后继的问题。【知识模块】 树和二叉树10 【正确答案】 C【试题解析】 考杳二叉树的中序线索化过程。二叉中序线索树中，某结点若有左孩子，则按照中序“左根右”的顺序，该结点的前驱结点为左子树中最右的一个结点。【知识模块】 树和二叉树11 【正确答案】 C【试题解析】 考查线索二叉树的线索数。n
21、 个结点共有链域指针 2n 个，其中，除根结点外，每一个结点都被一个指针指向。剩余的链域建立线索，共 2n(n1)=n+1 个线索。【知识模块】 树和二叉树12 【正确答案】 C【试题解析】 考查各种顺序遍历是否需要栈。不需要栈的支持仍可遍历则有：结点的左子树不为空时，它的前驱是其父结点或者左子树的结点；结点的右子树不为空时，它的后继是其父结点或者右子树的结点。显然，前序和中序线索树都满足这个条件，而后序线索树不满足。【知识模块】 树和二叉树13 【正确答案】 A【试题解析】 考查二叉排序树查找效率的决定因素。二叉排序树查找算法的平均查找长度，主要取决于树的高度。【知识模块】 树和二叉树14
22、【正确答案】 B【试题解析】 考查二叉排序树的性质。对二叉排序树进行中序遍历是可以得到一个有序序列的。【知识模块】 树和二叉树15 【正确答案】 C【试题解析】 考查二又排序树的相关性质。二叉排序树插入新结点时不会引起树的分裂组合。对二叉排序树进行中序遍历可得到有序序列。当插入的关键字有序时，二叉排序树会形成一个长链，此时深度最大。在此种情况下进行查找，有可能需要比较每个结点的关键字，超过结点数的 12。【知识模块】 树和二叉树16 【正确答案】 C【试题解析】 考查二叉排序树的构造过程。按照二又排序树的构造方法，不难得到 A、B、D 序列的构造结果相同。【知识模块】 树和二叉树17 【正确答
23、案】 C【试题解析】 考查二叉排序树的查找。在二叉排序树上查找时，先与根结点值进行比较，若相同，则查找结束，否则根据比较结果，沿着左子树或右子树向下继续查找。根据二叉排序树的定义，有左子树结点值根结点值右子树结点值。C 序列中，比较 911 关键字后，应转向其左子树比较 240，左子树中不应出现比 911 更大的数值，但是 240 竟有一个右孩子结点值为 912，所以不可能是正确的序列。【知识模块】 树和二叉树18 【正确答案】 D【试题解析】 考查二叉排序树的最小深度。当二叉排序树的叶子结点全部都在相邻的两层内时，深度最小。理想情况是从第一层到倒数第二层为满二叉树。类比完全二叉树，可得深度为
24、log 2(n+1)。【知识模块】 树和二叉树19 【正确答案】 A【试题解析】 考查二叉排序树的建立和查找。以第一个元素为根结点，依次将元素插入到排序树当中。进行查找时，先与根结点比较，然后根据比较结果，继续在左子树或者右子树上进行查找。【知识模块】 树和二叉树20 【正确答案】 C【试题解析】 考查给定结点数的平衡二叉树的最大深度。平衡二叉树结点数的递推公式为：N 0=0，N 1=1，N 2=2，N h=1+Nh-1+Nh-2(h 为平衡二叉树高度，N h 为构造此高度的平衡二叉树所需最少结点数)。通过递推公式可得，构造 5 层平衡二叉树至少需要 12 个结点，构造 6 层至少需要 20
25、个结点。【知识模块】 树和二叉树21 【正确答案】 C【试题解析】 考查平衡二叉树的插入。左孩子的平衡因子为 0，右孩子的平衡因子为 1，说明不平衡是因为在右子树的左子树上插入结点引起的，应作 RL 调整。【知识模块】 树和二叉树22 【正确答案】 C【试题解析】 考查特殊的平衡二叉树结点数的计算。每个非叶子结点的平衡因予为 0，说明该平衡二叉树为满二叉树，所以结点总数为 2k 一 1。【知识模块】 树和二叉树23 【正确答案】 D【试题解析】 考查树的存储形式。A、B、C 为树常用的存储形式。顺序存储表示法可以用来存储二叉树，但是不可用来存储树。【知识模块】 树和二叉树24 【正确答案】 A
26、【试题解析】 考查森林对应的二叉树。森林转换成二叉树时采用孩子一兄弟表示法，根结点及其左子树为森林中的第一棵树，右子树为其他树。所以第一棵树的结点个数为 m-n。【知识模块】 树和二叉树25 【正确答案】 B【试题解析】 考查森林转化成二叉树的过程。将森林中每棵树的根结点看成是兄弟结点的关系，再按照“左孩子右兄弟”的规则来进行转化。【知识模块】 树和二叉树26 【正确答案】 A【试题解析】 考查赫夫曼树非叶子结点的计算。赫夫曼树是二叉树。非空二叉树上叶子结点数等十度为 2 的结点数加 1。赫大曼树中度为 1 的结点个数为 0。所以叶子结点数一 1 即为非叶子结点数。【知识模块】 树和二叉树27
27、 【正确答案】 D【试题解析】 考查赫夫曼树结点总数的计算。根据“非空二叉树上叶子结点数等于度为 2 的结点数加 1”，度为 2 的结点数为 n 一 1，结点总数为 2n1。【知识模块】 树和二叉树28 【正确答案】 B【试题解析】 考查赫夫曼树叶子结点数的计算。根据上题结论，叶子结点数为(215+1)2=108，所以共有 108 个不同的码字。【知识模块】 树和二叉树29 【正确答案】 B【试题解析】 考查前缀码的定义。如果没有一个编码是另一个编码的前缀，称这样的编码为前缀编码。B 选项中，0 是 00 的前缀，1 是 11 的前缀。【知识模块】 树和二叉树30 【正确答案】 C【试题解析】
28、 考查赫夫曼树的构造方法。先是 3 和 5 构造为一棵子树，其根权值为 8；接着该子树与 6 构成一棵新子树，根权值为 14；然后 9 与 12 构造为一棵子树;最后两棵子树共同构造为一棵赫夫曼树。【知识模块】 树和二叉树二、综合题31 【正确答案】 算法的基本设计思想：采用队列结构按层次遍历，遍历 K 层时记录叶子结点个数。算法的代码：int LeafKlevel(BiTree bt， int k)求二叉树 bt 的第 k(k1)层上叶子结点个数if(bt=NULL 1 I kichild !p-rchild)1ear+； 叶子结点if(p 一1chiid)Q+rear：p 一lchiid，
29、 左子女入队if(p 一rchiid)Q+rear=p 一rchiid ； 右子女入队if(front=last)level+； 二叉树同层最右结点已处理，层数增 1last=rear； last 移到指向下层最右一元素if(1evelk) 层数大于 k 后退出运行return leaf； while LeafKLevel【知识模块】 树和二叉树32 【正确答案】 算法的基本设计思想：采用递归算法，取前序序列第一个结点为根，递归建立左、右子树。算法的代码：void PreInCreat(BiTree root，ElemType pre，ElemType mid，int 1l，int hl，in
30、t12，int h2)根据二叉树前序序列 pre 和中序序列 mid 建立二叉树11、h1、12、h2 是序列第一和最后元素的下标root=(BiTree)malloc(SiZeof(BiNode);申请结点root 一data=pre11； pre11是根结点for(i=12；ilchild=NULL; 无左子树else 递归建立左子树PreInCreat(root 一lchiid，pre，mid，11+l ，11+(i 一 12)，12，i 一 1)，if(i=h2)root 一rchild=NULL； 无右子树else 递归建立右子树PreInCreat(root 一rchild，pre
31、 ，mid，11+(i 一 12)+1，h1，i+1，h2)； PreInCreat【知识模块】 树和二叉树33 【正确答案】 算法的基本设计思想：开始时考查整个中序序列和后序序列，将中序序列和后序序列的起始信息封装到结构体中，入栈。当栈不为空时，循环执行操作：取出栈顶元素，按照结构体所指示出的两段序列，将元素的结点赋值为后序序列的最后一个结点；若此结点有左子树，挂接左孩子并将左子树的中序和后序信息封装入栈；若有右子树，挂接右孩子并将右子树中序和后序信息入栈。直到栈空为止。算法的代码：typedef Structint 11 l h1 t 12，h2；BiTree t;node；void In
32、PostCreat(ElemType IN，ElemType POST ，int 1，int hl，int 12，int h2)由二叉树的中序序列 IN和后序序列 POST建立二叉树，11、h1 和 12、h2分别是中序序列和后序序列第一和最后元素的下标，初始调用时，11=12=1、hl=h2=nnode S， P； s 是栈，容量足够大BiTree bt=(BiTree)mellOC(SiZeof(BiNode)；int top=0， i；P11=11; 初始化Ph1=h1；P12=12;Ph2=h2；Pt=bt；S+top=P;while(top0)p=stop 一一 ； 取出栈顶数据bt
33、=Pt；11=p11；h1=Ph1；12=p12;h2=ph2;for(i=11;idata ：POSTh2; 根结点的值if(i=11)bt 一1child=NULL; bt 无左子树e1Sebt 一1child=(BiTree)malloc(Sizeof(BiNode)；Pt=bt 一1chiid；P11=11;Ph1=i 一 1；P12=12；Ph2=12+i11 一 1；S+top=p； 将建立左予树的数据入栈if(i=h1)bt 一rchild=NULL; bt 无右子树e1Sebt 一rchild=(BiTree)mallOC(SiZeof(BiNode);Pt=bt 一rchii
34、d：P11=i+1：Ph1=h1;P12=12+i 一 11：Ph2=h21;S+top一 p； 右子树数据入栈 while(top0) InPostCreat【知识模块】 树和二叉树34 【正确答案】 算法的基本设计思想：递归地将左子树中序线索化，接着判断若没有左孩子，则左指针指向前驱结点，若前驱不空则给前驱加上后继线索。然后递归地将右子树中序线索化。算法的代码：VOid CreateInThread(ThreadTree T) 建立中序二叉树的主过程ThreadTree pre=NULL；if(T!=NULL)InThread(T，Pre);pre 一rchild：NuLL; 处理遍历的最
35、后一个结点pre 一rtag=1 ;VOid InThread(ThreadTree P，ThreadTree pre) 中序遍历对二叉树线索化的递归算法if(p!=NULL)InThread(p-ichiid，pre)； 线索化左子树if(P 一lchiid=NULL) 左子树为空，建立前驱线索P 一lchiid pre：P 一1tag=1 ;if(pre!=NULLpre 一rchild=NULL) 建立前驱结点的后继线索pre 一rchi id=P;pre 一rtag=1；pre=p； 标记当前结点成为刚刚访问过的结点InThread(p 一rchiid ，pre); 线索化右子树 In
36、Thread【知识模块】 树和二叉树35 【正确答案】 算法的基本设计思想：循环执行以下步骤：沿左分支向下，访问最左端第一个没有左子树的结点(中序遍历第一个结点)，然后当有右线索时访问后继结点，有右孩子时转到右子树。算法的代码：VOid InOrderThreat(BiThrTree thrt)thrt 是指向中序全线索化头结点的指针，本算法中序遍历该二叉树p=thrt 一lchild； p 指向二叉树的根结点，当二叉树为空时，P 指向 thrtwhile(P!=thrt)while(P 一ltag=O)p=p-ichiid； 沿左子女向下visit(*p)， 访问左子树为空的结点while(
37、p 一rtag=1 p-rchiid!=thrt)P=P 一rchiid;viSit(*p)； 沿右线索访问后继结点p=p 一rchild； 转向右子树 InOrderThread【知识模块】 树和二叉树36 【正确答案】 算法的基本设计思想：若 p 有左子女，则左子女就是其前序后继；若 p 无左子女而有右子女，则 p 的右子女就是 p 的前序后继；若 P 无左、右子女，这时沿 p 的右线索往上，直到 P 的右标志为 0(非线索 )，这时若 p 的右子女为空，则表示这是中序遍历最后一个结点，故指定结点无前序后继，否则，该结点就是指定结点的前序后继。算法的代码：BiThrTree InSuec(
38、BiThrTree T，BiThrTree P)利用中序全线索树求其中任意结点 P 的前序后继结点if(p 一1tag=0P 一ichiid!=NULL)return p-ichiid； p 的左子女是 P 的前序后继e1Se if(p 一rtag=0P 一rchiid!=NULL)return P 一 rchiid； p 的右子女是其前序后继e1Se p 无左、右子女，应沿右线索向上(找其前序后继 )，直到某结点右标志为0while(P 一rtag=1)p=p 一rchiid；if(p 一rchiid)retUrn P 一 rchild；e 上 sereturn NULL； 指定结点的前序后
39、继 InSucc注意题目“中序序列第一个结点的左标志和最后结点的右标志皆为 0(非线索)，对应指针皆为空” 的说明。若无这一说明，只要结点的左标志为 0，其左子女就是其前序后继。最后，当 P 无子女，沿右线索向上找其前序后继时，若最后结点的右标志为 0，但对应指针为空，p 也无前序后继。【知识模块】 树和二叉树37 【正确答案】 算法的基本设计思想：在后序序列中，若结点 p 有右子女，则右子女是其前驱；若无右子女而有左子女，则左子女是其前驱。若结点 p 左、右子女均无，设其中序左线索指向某祖先结点 f(p 是 f 右子树中按中序遍历的第一个结点)，若 f 有左子女，则其左子女是结点 p 在后序
40、下的前驱；若 f 无左子女，则顺其前驱找双亲的双亲，一直继续到双亲有左子女(这时左子女是 p 的前驱)。还有一种情况，若 p 是中序遍历的第一个结点，结点 p 在中序和后序下均无前驱。算法的代码：BiThrTree InPostPre(BiThrTree t，BiThrTree p)F 中序线索二叉树 t 中，求指定结点 P 在后序下的前驱结点 qBiThrTree q；if(p 一rtag=0) 若 P 有右子女，则右子女是其后序前驱q=p 一rchiid，else if(p 一 ltag=0) 若 P 无右子女而有左子女，左子女是其后序前驱q=p 一lchiid;else if(p 一 l
41、child=NULL)q=NULL； p 是中序序列第一个结点，无后序前驱else 顺左线索向上找 P 的祖先，若存在，再找祖先的左子女while(p 一itag=1if(p 一ltag=0)q=p 一lchild， p 结点的祖先的左子女是其后序前驱elseq=NULL， 仅右单支树 (P 是叶子结点)，已上到根结点，P 无后序前驱return q; InPostPre【知识模块】 树和二叉树38 【正确答案】 算法的基本设计思想：若使新插入的叶子结点 s 成为 T 右子树中序序列的第一个结点，则应在 T 的右子树中最左面的结点 (设为 p)处插入，使 S 成为结点 p 的左子女，则 S 的
42、前驱是 T，后继是 p。算法的代码：void ThrTreeInsert(BiThrTree T，BiThrTree S)(在中序线索二叉树 T 的右子树上插入结点 S，使 s 成为 T 右子树中序遍历第一个结点p=T-rchiid； 用 P 去指向 T 的右子树中最左面的结点while(p 一1taq=0)p=p 一1child；s 一itag：1； s 是叶子结点，其左、右标志均为 1S 一rtag=1 ；S-lchild：T; S 的前驱是根结点 T，后继是结点 PS 一rchild=P；D 一ichild：S; 将 P 的左子女指向 S，并修改左标志为 0P 一1tag=0；IThrT
43、reeInsert【知识模块】 树和二叉树39 【正确答案】 直接按照题目中思想编写程序即可。算法的代码：BiTree Creat()生成并中序输出二叉排序树scanf(“c“，ch) ch 是二叉排序树结点值的类型变量，假定是字符变量BiTree bSt=NULL，f=NULL;while(ch!=#) 、，是输入结束标记s=(BiTree)malloc(sizeof(BiNode)； 申请结点S 一data=ch；S 一1child=S 一rchild=NULL ；if(bSt=NULL)bst： S; 根结点e1Se 查找插入结点P=bst;while(P)if(chp 一data)f=
44、P；p=p 一rchild；沿右分支查，f 是双亲e1Sef=p；p=p 一ichild；沿左分支查if(f 一datarchild=S；e1Sef 一1child=S;scanf(“c”，ch)； 读入下一数据 while(ch!=#)retllrn bSt：void InOrder(BiTree bst)bst 是二叉排序树，中序遍历输出二叉排序树if(bSt)InOrder(bSt 一lchild) ；printf(”d”，bst-data);InOrder(bst 一rchild) ； InOrder【知识模块】 树和二叉树40 【正确答案】 算法的基本设计思想：当森林(树)以孩子一兄
45、弟表示法存储时，若结点没有孩子(fch-NULL) ，则它必是叶子结点，总的叶子结点个数是孩子子树(fch)上的叶子结点个数和兄弟(nsib)子树上的叶子结点个数之和。算法的代码：typedef Struct nodeElemType data， 数据域Struct node*fch，*nsib;孩子与兄弟域*Tree;int Leaves(Tree t)计算以孩子一兄弟表示法存储的森林的叶子结点数if(t)if(t-fch NULL) 若结点无孩子，则该结点必是叶子结点return 1+LeaveS(t-nSib);返回叶子结点和其兄弟子树中的叶子结点数return LeaveS(t 一fc
46、h)+Leaves(t 一nsib) ；孩子子树和兄弟子树中叶子结点数之和 LeaveS【知识模块】 树和二叉树41 【正确答案】 由孩子一兄弟链表表示的树，求深度的算法的基本设计思想：采用递归算法，若树为空，深度为 0；若第一子女为空，深度为 1 和兄弟子树深度的大者，否则，深度为第一子女树深度加 1 和兄弟子树深度的大者。其非递归算法使用队列，逐层遍历树，取得树的深度。算法的代码；int Height(CSTree bt)递归求以孩子一兄弟链表表示的树的深度int hc，hs；if(bt=NULL)return 0;else if(!bt 一fimstchild)return 1+heig
47、ht(bt 一nextSibling); 子女空，查兄弟的深度 结点既有第一子女又有兄弟，深度取子女深度加 1 和兄弟子树深度的大者hc=height(bt 一firstchild);第一子女树深hs=height(bt 一nextsibling)； 兄弟树深if(hc+1hS)return hc+1；e1Sereturn hs;Iheightint height(CSTree t)非递归遍历求以孩子一兄弟链表表示的树的深度if(t=NULL)return 0；e1Seint frOnt=1，rear=1; front、rear 是队头、队尾元素的指针int 1ast=1，h=0;last 指向树中同层结点中最后一个结点，h 是树的深度Qrear=t， Q 是以树中结点为元素的队列while(frontfirstchild)Q+rear=t-firstchild； 第一子女入队t=t 一nextsibling ； 同层兄弟指针后移if(front1ast)f 本层结束，深度加 1(初始深度为 0)h+；last=rear； Ilast 再移到指向当前层最右一个结点jwhile(front=last else Height【知识模块】 树和二叉树42 【正确答案】 森林转换为二叉树的三步：1)连线(将兄弟结点相连，各树的根看作兄弟)。2) 切线 (保留最左
