1、计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 1 及答案与解析一、单项选择题1 树是一种逻辑关系，表示数据元素之间存在的关系为_。【北京交通大学2007 年】（A）集合关系（B）一对一关系（C）一对多关系（D）多对多关系2 在一棵三元树中度为 3 的结点数为 2 个，度为 2 的结点数为 1 个，度为 1 的结点数为 2 个，则度为 0 的结点数为_个。【哈尔滨：业大学 2001 年】（A）4（B） 5（C） 6（D）73 设有一表示算术表达式的二叉树(见图 3-1)，它所表示的算术表达式是_。【南京理工大学 1999 年】（A）A+B+C(D*E)+(FG)（B） (A*B+C)
2、(D*E)+(FG)（C） (A+B+C)(D*E+(F G)（D）A*B+CD*E+FG4 在下述结论中，正确的是_。【南京理工大学 1999 年】只有一个结点的二叉树的度为 0：二叉树的度为 2；二叉树的左右子树可任意交换：深度为 K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。（A）（B） （C） （D）5 若一棵二叉树具有 10 个度为 2 的结点，5 个度为 1 的结点，则度为 0 的结点个数是_。【北京工商大学 2001 年】（A）9（B） 11（C） 15（D）不确定6 具有 10 个叶结点的二叉树中有_个度为 2 的结点。【北京航空航天大学 2000年】（A）8（B）
3、9（C） 10（D）117 一棵完全二叉树上有 1001 个结点，其中叶_了结点的个数是_。【西安交通大学 1996 年】（A）250（B） 500（C） 254（D）505（E）以上答案都不对8 若一棵深度为 6 的完全二叉树的第 6 层有 3 个叶子结点，则该二叉树共有个叶了结点。【北京航空航天大学 2003 年】（A）17（B） 18（C） 19（D）209 有关二叉树下列说法正确的是_。【南京理工大学 2000 年】（A）二叉树的度为 2（B）一棵二叉树的度可以小于 2（C）二叉树中至少有一个结点的度为 2（D）二又树中任何一个结点的度都为 210 二叉树的第 i 层上最多含有结点数为
4、_。【北京理工大学 2001 年】（A）2 i（B） 2i-1 一 1（C） 2i-1（D）2 i 一 111 当结点数目一定时，具有最小深度的二又树是_。【北京航空航天大学 2005年】（A）满二叉树（B）完全二叉树（C）线索二叉树（D）二叉排序树12 一棵具有 n 个结点的完全二又树的树高度(深度)是_。【南京理工大学 1996年】（A）log 2n+1（B） log2n+1（C） log2n（D）log 2n 一 113 一棵深度为 4 的完全二叉树，最少有_个结点。【华南理工大学 2005 年】（A）4（B） 8（C） 15（D）614 一棵树高为 k 的完全二叉树至少有_个结点。【南
5、京理工大学 1998 年】（A）2 k1（B） 2k-1 一 1（C） 2k-1（D）2 k15 有 n 个结点的二叉树的深度最小值是_。【华中科技大学 2006 年】（A）log 2(n)（B） log2(n+1)（C） log2(n+1)（D）log 2(n)16 在一棵高度为 k 的满二叉树中，结点总数为_。【北京工商大学 2001 年】（A）2 k-1（B） 2k（C） 2k 一 1（D）log2 k+117 一棵深度为 7 的满二叉树共有_个非终端结点。【北京邮电大学 2007 年】（A）31（B） 63（C） 127（D）25518 有 n 个结点，并且高度为 n 的二叉树的数目为
6、_。【华中科技大学 2007 年】（A）log 2n（B） n2（C） n（D）2 n-119 下列判断中_是正确的。【华南理工大学 2006 年】（A）深度为 k 的二叉树最多有 2k-1 个结点(k1)，最少有 k 个结点（B）二叉树中不存在度大于 2 的结点（C）对二叉树遍历是指先序、中序或后序遍历中的一种（D）构造线索二叉树是为能方便找到每个结点的双亲20 以下说法中_是正确的。【华南理工大学 2006 年】（A）完全二叉树中，叶结点的双亲的左兄弟(如果存在)一定不是叶结点（B）任何一棵二叉树，终端结点数为度为 2 的结点数减 1（C）二叉树不适合用顺序结构存储（D）结点按层序编号的二
7、叉树，第 i 个结点的左孩子(如果存在)的编号为 2i21 利用二叉链表存储树，则根结点的右指针是_。【青岛大学 2001 年】（A）指向最左孩子（B）指向最右孩子（C）空（D）非空22 当一棵有 n 个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组 AL,n中时，数组中第 i 个结点的左孩子为 _。【南京理工大学 1999 年】（A）A2i(2in)（B） A2i+1(2i+1n)（C） Ai2（D）无法确定23 一棵有 n 个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组 ALn中，则二又树中第 i(i 从 1 开始用上述方法编号 )个结点的右孩予在数组 A
8、 中的位置是_。【南京理工大学 2000 年】（A）A2i(2in)（B） A2i+1(2i+1n)（C） Ai-2（D）条件不充分，无法确定24 若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用_遍历方法最合适。【北京航空航天大学 1999 年】（A）前序（B）中序（C）后序（D）按层次25 树的后根遍历序列等同于该树对应的二叉树的_。【湖南大学 2008 年】（A）先序序列（B）中序序列（C）后序序列（D）层次遍历26 已知某完全二叉树采用顺序存储结构，结点数据信息的存放顺序依次为ABCDEFGH，该完全二叉树的后序遍历序列为_。【北京航空航天大学 2002 年】（
9、A）HDEBFGCA（B） HEDBFGCA（C） HDEBAFGC（D）HDEFGBCA二、综合题27 假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树 BT 中，写出计算该算术表达式值的算法。【东北大学 2000 年】28 假定用两个一维数组 LN和 RN作为有 N 个结点 1，2，N 的二叉树的存储结构。Li和 Rj分别指示结点 i 的左儿子和右儿子，Li=0(Ri=0)表示 i 的左(右)儿子为空。试写一个算法，由 L 和 R 建立一个一维数组 Tn，使 Ti存放结点i 的父亲；然后再写一个判别结点 U 是否为结点 V 的后代的算法。【哈尔滨工业大学 1999 年】29 已知
10、一棵二叉树按顺序方式存储在数组 A1，n中。设计算法，求出下标分别为 i 和 j 的两个结点的最近的公共祖先结点的值。【武汉大学 2000 年】30 有 n 个结点的完全二叉树存放在一维数组 A1,n中，试据此建立一棵用二叉链表表示的二叉树，根由 tree 指向。【南京理工大学 1998 年】31 已知深度为 h 的二叉树采用顺序存储结构_已存放于数组 BT12 h 一 1中，请写一非递归算法，产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(1ehild，data，rehild)，根结点所在链结点的指针由 T 给出。【北京航空航天大学2007 年】32 编写递归算法，依据树的双亲表示法
11、及其根结点创建树的孩子一兄弟链表存储结构。【清华大学 1995 年】33 编程，判断一棵二叉链表表示的二又树是否是完全二叉树。【南京航空航天大学 2001 年】34 二叉树采用二叉链表存储。1)编写计算整个二叉树高度的算法(二叉树的高度也称为二叉树的深度)。2) 编写计算二叉树最大宽度的算法(二叉树的最大宽度是指二叉树所有层中结点个数的最大值)。【西北大学 2001 年】35 在二叉树中查找值为 x 的结点，试编写算法(用 c 语言)打印值为 x 的结点的所有祖先，假设值为 x 的结点不多于一个。【上海交通大学 1998 年】36 设一棵完全二叉树使用顺序存储结构存放在数组 btL,n中，请写
12、出进行非递归的前序遍历算法。【西安电子科技大学 1998 年】37 设计算法返回二叉树 T 的先序序列的最后一个结点的指针，要求采用非递归形式，且不允许用栈。【合肥工业大学】999 年】38 对于二叉树的链接实现，完成非递归的中序遍历过程。【中山大学 1999 年】39 试给出二叉树的自下而上、自右而左的层次遍历算法。【吉林大学 2001 年】40 已知一二叉树中结点的左、右孩子为 left 和 right，p 指向二叉树的某一结点。请用 C 语言编写一个非递归函数 postfirst(p)，求 p 所对应子树的第一个后序遍历结点。【浙江大学 1998 年】41 请设计一个算法，要求该算法把二
13、叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为 head。二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。分析你的算法的时、空复杂度。【华南师范大学 1999年】42 设两棵二叉树的根结点地址分别为 p 和 q，采用二叉链表的形式存储这两棵树上所有的结点。请编写程序，判断它们是否相似。【上海交通大学 2000 年】【北京航空航天大学 2005 年】计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 1 答案与解析一、单项选择题1 【正确答案】 C【试题解析】 考查树的概念。树是一种特殊的数据结构，表示元素之间的一对多的关系，例如：一个父结点可能有多个儿子结
14、点，而一个儿子结点一定只有一个父结点。【知识模块】 树和二叉树2 【正确答案】 C【试题解析】 考查树结点数与度的相关计算。树中结点数等于所有结点度数和加1。所以，2 十 1+2+X=2.3+12 十 2.1+x0+1，解得 X=6。【知识模块】 树和二叉树3 【正确答案】 C【试题解析】 考查二又树表示算术表达式的方法。叶子结点表示运算值，非叶子结点表示运算符，运算符的子结点或子树即该运算符的运算值。【知识模块】 树和二叉树4 【正确答案】 D【试题解析】 考查二叉树的相关概念。二叉树的度最多为 2，可以比 2 小。二叉树的左有了树是有顺序的，不可随意交换。完全二叉树从最底层右边起比层数相同
15、的满二叉树连续缺失若干个叶结点。【知识模块】 树和二叉树5 【正确答案】 B【试题解析】 考查二叉树结点数和度的关系。二叉树结点度数最多为 2。设度为0 的结点个数为 x，根据“树中结点数等于所有结点度数和加 1”，可得10+5+X=10*2+5+1+X*0+1，解得 x=11。【知识模块】 树和二叉树6 【正确答案】 B【试题解析】 考查二叉树结点数和度的关系。根据“非空二叉树卜叶子结点数等于度为 2 的结点数加 1”，所以选 B。【知识模块】 树和二叉树7 【正确答案】 E【试题解析】 考查完全二叉树叶子结点数的计算。对完全二叉树按从上到下、从左到右的顺序进行编号 1，2，N，第 1001
16、 个结点的父结点编号为 10012=500，此后的所有结点都没有孩子结点，即为叶子结点。叶子结点数为 1001-500=501。【知识模块】 树和二叉树8 【正确答案】 A【试题解析】 考查完全二叉树叶子结点数的计算。第 5 层共有结点 24 个，即 16个叶子结点。第 6 层最左边有 3 个叶子结点，对应第 5 层最左边两个结点，所以第5 层右边有 162=14 个叶子结点，加上第 6 层 3 个，共 17 个叶予结点。【知识模块】 树和二叉树9 【正确答案】 B【试题解析】 考查二叉树的相关概念。二叉树的度至多为 2，可以小于 2。当二叉树只有一个结点时，度为 0。【知识模块】 树和二叉树
17、10 【正确答案】 C【试题解析】 考查二叉树一层结点最大数。第 i 层最多含有结点数为 2i-1【知识模块】 树和二叉树11 【正确答案】 B【试题解析】 考查最小深度的二又树。当结点组成完全二叉树的时候，树的深度最小。满二叉树是完全二叉树的特殊情况。【知识模块】 树和二叉树12 【正确答案】 A【试题解析】 考查完全二叉树高度的计算。具有 n 个结点的完全二叉树的高度为10g2(n+1)或log 2n+1。【知识模块】 树和二叉树13 【正确答案】 B【试题解析】 考查完全二叉树的结点数。深度为 4 的完全二叉树，前 3 层结点总数为 23 一 1=7。第 4 层只有一个结点时，完全二叉树
18、结点数最少。即 8 个。【知识模块】 树和二叉树14 【正确答案】 C【试题解析】 考查完全二叉树的结点数。【知识模块】 树和二叉树15 【正确答案】 C【试题解析】 考查二叉树深度最小值。当结点组成完全二叉树的时候，树的深度最小。【知识模块】 树和二叉树16 【正确答案】 C【试题解析】 考查满二叉树的结点数。考生只要记住公式即可。【知识模块】 树和二叉树17 【正确答案】 B【试题解析】 考查满二叉树非终端结点的计算。深度为 n 的满二叉树结点个数为2n-1，叶予结点个数为 2n-1，非终端结点个数为 2n-1-1。【知识模块】 树和二叉树18 【正确答案】 D【试题解析】 考查二叉树的树
19、形。由题可得，每层有一个结点，从根结点往下，每个结点都有作左孩子、右孩子两种情况，由概率知识可得，二叉树共有 2n-1 种树形。【知识模块】 树和二叉树19 【正确答案】 B【试题解析】 考查二叉树的各种性质。二叉树的遍历有各种不同的方法，比如层次遍历。引入线索二叉树是为了方便找到结点在某个遍历序列中的前驱和后继结点。【知识模块】 树和二叉树20 【正确答案】 A【试题解析】 考查二叉树的各种性质。非空二叉树卜叶子结点数等于度为 2 的结点数加 1，二叉树可以使用顺序结构存储。D 中性质只针对完全二叉树。【知识模块】 树和二叉树21 【正确答案】 C【试题解析】 考查二又链表存储树。根结点的右
20、指针为空。【知识模块】 树和二叉树22 【正确答案】 D【试题解析】 考查二叉树的顺序存储。完全二叉树时，第 i 个结点的左孩了编号为 2i，普通二叉树并无此规律。【知识模块】 树和二叉树23 【正确答案】 D【试题解析】 考查二叉树的顺序存储。完全二叉树时，第 i 个结点的右孩子编号为 2i+1，普通二叉树并无此规律。【知识模块】 树和二叉树24 【正确答案】 C【试题解析】 考查二叉树各种遍历顺序。要交换分支结点的左右子树，应该最后才访问分支结点。应采用后序遍历。【知识模块】 树和二叉树25 【正确答案】 B【试题解析】 考查树的遍历与二叉树遍历的对应。树和森林的遍历，可采用对应二叉树的遍
21、历算法来实现，见表 3-1。【知识模块】 树和二叉树26 【正确答案】 A【试题解析】 考查完全二叉树的存储和后序遍历序列。按照顺序结构建立二叉树，然后按照后序遍历顺序遍历该二叉树。【知识模块】 树和二叉树二、综合题27 【正确答案】 算法的基本设计思想：以二叉树表示算术表达式，根结点用于存储运算符。先分别求出左子树和右子树表示的子表达式的值，最后根据根结点的运算符的要求，计算出表达式的最后结果。算法的代码：typedef struct node(float val；char optr； 只取+ ， 一， *， struct node *lchild， *rchildBiNode，*BiTre
22、e;float PostEval(BiTree bt) 以后序遍历算法求以二叉树表示的算术表达式的值float lv，rv；if(bt 一lchild=NULL bt 一rchild=NULL)return bt 一val； e1Selv=PostEval(bt-ichiid); 求左子树表示的子表达式的值rv=PostEval(bt-rchiid)； 求右了树表示的子表达式的值switch(bt 一optr)Case+：valUe=lv+rv ：break;Case一 ：valUe=1Vrv：break;case*：valme=1v*rv：break;Case ：valUe=1vrv：ret
23、urn valUe； PoStEval【知识模块】 树和二叉树28 【正确答案】 算法的基本设计思想：由指示结点 i 左儿子和右儿子的两个一维数组 Li和 Ri，建立指示结点 i 的双亲的一维数组 Ti。若结点 i 的左了女是 L，则结点 L 的双亲是结点 i，若 i 的右子女是 r，则 r 的双亲是 i。根据 T 数组，判断结点 u 足否是结点 V 后代的算法，转为判断结点 V 是否是结点 u 的祖先的问题。算法的代码：int Generation(int u，int v ，int N，int L ，int R，int T)L和 R是含有 N 个元素且指示二叉树结点 i 左儿子和右儿子的一维
24、数组本算法据此建立结点 i 的双亲数组 T，并判断结点 U 是否是结点 v 的后代for(i=1 ; ij)i=i2 ; 下标为 i 的结点的双亲结点的下标e1SeJ=j2； 下标为 j 的结点的双亲结点的下标printf(“所查结点的最近公共祖先的下标为d，值为d“，i ，Ai)，设元素类型为整型 AnCeStor【知识模块】 树和二叉树30 【正确答案】 算法的基本设计思想：利用递归算法，先建立根的链结点表示，然后分别以根结点的孩子(左右子树的根)为根建立左右子树。算法的代码：BiTree Creat(E1emType A，int i)n 个结点的完全二叉树存于一维数组 A 中本算法据此建
25、立以二叉链表表示的完全二叉树BiTree tree ;if(idata=Ai;if(2*in)tree 一1child=NULL;e1Setree 一-child=Creat(A，2*i)；if(2*i+1n)tree 一rchild=NULL：e1Setree 一rchild=Creat(A ，2*i+1);return tree；/Creat初始调用时，i=1。【知识模块】 树和二叉树31 【正确答案】 二叉树采用顺序存储结构(一维数组)是按完全二叉树的形状存储的，不是完全二叉树的二叉树顺序存储时，要加“虚结点” 。数组中的第一个元素是根结点。算法的基本设计思想：采用队列结构，先建立根结点
26、入队。当队列不空时循环执行以下步骤：队头结点出队，如果有左孩子，则建立左孩子结点并入队；如果有右孩子，则建立右孩子结点并入队。算法的代码： typedef struct BiTree bt： 二叉树结点指针 int num； num 是结点在一维数组中的编号 tnode tnode Qmaxsize； 循环队列，容量足够大 void creat(BiTree T ，E1emType BT，int h) 深度为 h 的二叉树存于一维数组 BT12 h 一 1中 本算法生成该二叉树的二叉链表存储结构 tnode tq； tq 是队列元素 int len=pow(2，h)一 1; 数组长度 T=(B
27、iTree)malloc(Si zeof(BiNode); 申请结点 T 一data=BT1； 根结点数据 tqbt=T; tq num=1; Q1=tq； 根入队列 front=0； 循环队列头、尾指针 rear=1; while(front!=rear) 当队列不空时循环 front=(front+1)maxsi ze; tq：Qfront； 出队，取出结点及编号 p=tqbt； i=tqnum； if(BT2+i=#2*ilen) 左子树为空，#，表示虚结点 P 一ichild=NULL; else 建立左子女结点并入队列 p 一lchiid=(BiTree)melloc(Sizeof(
28、BiNode); p-ichild-data=BT2*i； 左子女数据 tqbt=P 一1child; tqnum=2*i ； rear=(rear+1)maxsize; 计算队尾位置 Qrear=tq； 左子女结点及其编号入队 if(BT2*i+1=#2*i+1len) p-rchild=NULL; 右子树为空 e1Se 建立右子女结点并入队列 P 一rchild=(BiTree)mallOC(Si Zeof(BiNode); P 一rchild一data=BT2*i+1; tqbt=P 一rchild： tqnum=2*i+1; rear=(rear+1)maxsi ze； 计算队尾位置，
29、右子女及其编号入队 Qrear=tq； while Creat 本题中的虚结点用#表示，应根据二叉树的结点数据的类型而定。【知识模块】 树和二叉树32 【正确答案】 算法的基本设计思想：首先给出根结点在双亲表示法中的下标，找根结点的子女要遍历双亲表示法的整个静态链表，根结点的第一个子女是孩子兄弟表示法中的孩子，其他子女结点作兄弟。对双亲表示法中的任一结点，均递归建立其孩子兄弟链表子树。算法的代码：CSTree PtreeToCStree(PTree pt，int root)本算法将双亲表示法的树 pt 转为孩子兄弟链表表示的树root 是根结点在双亲表示法中的下标CSTree child，Si
30、bling ；int firstchild；CSTree cst=(CSTree)mall0(2(SiZeof(CSNode);cst 一data=ptnodesroot data;根结点Cst 一firstchilct=NULL;cst 一nextsibling=NULL；firstchild=1 ;for(i=1; ifirstchild=child；firStchild=0 ;sibling=cst 一firstch1d；e1Se child 不是 root 的第一个孩子，作兄弟处理Sibling 一nextsibling=chiid；Sibling=sibling 一nextsibli
31、ng;) if end forreturn cst; PtreetoCStree【知识模块】 树和二叉树33 【正确答案】 算法的基本设计思想：判定是否是完全二叉树，可以使用队列进行从上至下、从左至右的层次遍历，当首次出现叶子结点或无右孩子结点后，后面全部都应该是叶子结点。同时在遍历中利用完全二叉树“若某结点无左子女就不应有右子女”的原则进行判断。算法的代码：int JudgeComplete(BiTree bt) 判断二叉树是否是完全二叉树，如是，返回 1，否则，返回 0int tag=0；BiTree p=bt，Q ； Q 是队列，元素是二叉树结点指针，容量足够大if(p=NULL)ret
32、urn 1;QueueInit(Q)；QueueIn(Q，p)； 初始化队列，根结点指针入队while(!QueueEmpty(Q)p=QueueOut(Q); 出队if(p 一1chiid!tag)QueueIn(Q，p 一ichild); 左子女入队e1Seif(p 一ichiid) 前边已有结点为空，本结点不空return 0；else 首次出现结点为空tag=1；if(p 一rchiId!tag)QueueIn(Q，p 一rchild)； 右子女入队e1Seif(p 一rchiid)return 0；e1Setag=1; whilereturn 1； JudgeCOmplete完全二叉
33、树证明还有其他方法。判断时易犯的错误是证明其左子树和右子树都是完全二叉树，由此推出整棵二叉树必是完全二叉树的错误结论。【知识模块】 树和二叉树34 【正确答案】 算法的基本设计思想：利用递归算法求二叉树高度：计算出某结点左右子树的高度，取大值加 1 即是以该结点为根的子树的高度。求最大宽度可采用层次遍历的方法，记下各层结点数，每层遍历完毕，若结点数大于原先最大宽度，则修改最大宽度。算法的代码：int Height(BiTree bt)求二叉树 bt 的深度int h1，hr;if(bt=NULL)return O;e1Sehl=Height(bt 一lch) ；hr=Height(bt 一rc
34、h);if(h1hr)return h1+1；e1sereturn hr+1：int Width(BiTree bt)求二叉树 bt 的最大宽度if(bt=NULL) 空二叉树宽度为 0return 0；e1seBiTree Q; Q 是队列，元素为二叉树结点指针，容量足够大front=1 ; 队头指针rear=1； 队尾指针last=1; 同层最右结点在队列中的位置temp=0; 记局部宽度maxw=0； 记最大宽度Qrear=bt； 根结点入队列while(frontlchiid!=NULL)Q+rear=p-ichild；左子女入队if(P 一rchild!=NULL)Q+rear=p
35、一rchild ；右子女入队if(front1ast)一层结束，last=rear；if(tempmaxw)maxw=temp； last 指向下层最右元素，更新当前最大宽度temp=0，、/if while elsereturn maxw； width【知识模块】 树和二叉树35 【正确答案】 算法的基本设计思想：采用后序遍历，最后访问根结点，当访问到值为 X 的结点时，栈中所有元素均为该结点的祖先。算法的代码：typedef struct BiTree bt;int tag;lstack； tag=0 表示左子女被访问，tag=1 表示右子女被访问void Search(BiTree bt
36、，ElemType x)在二叉树 bt 中，查找值为 X 的结点，并打印其所有祖先stack s; 栈容量足够大top=0；while(bt!=NULLtop0)while(bt!=NULLbt 一data!=x) 结点入栈S+topt=bt;stoptag=0 ；bt=bt 一ichild； 沿左分支向下if(bt 一data=x)printf(“所查结点的所有祖先结点的值为：n”);找到 Xfor(i：1；idata)； 输出祖先值后结束exit(1);while(top!=Ostoptag=1)top 一一； 退栈(空遍历)if(top!=0)stoptag=1 ；bt=stopt 一r
37、child；沿右分支向下遍历 while(bt!=NULL top0)/ search因为查找的过程就是后序遍历的过程，使用的栈的深度不超过树的深度，算法复杂度为 0(10gn)。【知识模块】 树和二叉树36 【正确答案】 二叉树的顺序存储是按完全二叉树的顺序存储格式，双亲与子女结点下标间有确定关系。对顺序存储结构的二叉树进行遍历，与二叉链表类似。在顺序存储结构下，判二叉树为空时，用结点下标大于 n(完全二叉树)或 0(对一般二叉树的“虚结点 ”)。本题是完全二叉树。算法的基本设计思想：从根结点开始，每访问一个结点，将其右孩子入栈，沿着左分支向下继续访问，当结点下标大于 n 时，判二叉树为空。
38、然后依次退栈，继续循环访问。算法的代码：void PreOrder(ElemType bt，int n) 对以顺序结构存储的完全二叉树 bt 进行前序遍历in 七 top=O，s； top 是栈 s 的栈顶指针，栈容量足够大while(i0)while(i0)i=stop 一一 ； 取出栈顶元素 PreOrder【知识模块】 树和二叉树37 【正确答案】 算法的基本设计思想：要找二叉树先序序列的最后一个结点，若二叉树有右子树，则是右子树中最右下的叶子结点；若无右子树，仅有左子树，则是左子树最右下的叶子结点：若二叉树无左、右子树，则返回根结点。算法的代码：BiTree LastNode(BiTr
39、ee bt) 返回二叉树 bt 先序序列的最后一个结点的指针BiTree p=bt；if(bt=NULL)return NUIL；elsewhile(p)i f(p 一rchild)p=p 一rchild； 若右子树不空，沿右子树向下e1Se if(P 一 lchiid)p=P 一ichild； 右子树空，左子树不空，沿左子树向下e1Sereturn p; p 即为所求 lastnode【知识模块】 树和二叉树38 【正确答案】 算法的基本设计思想：先中序遍历左子树，然后弹栈，访问根结点，遍历右子树。算法的代码：VOid InOrder(BiTree bt)BiTree s，p：bt； s 是
40、元素为二叉树结点指针的栈，容量足够大int top=O;while(Ptop0)while(p) 中序遍历左子树S+top=P；p=p 一1chiid；if(top0)p=stop 一一 ， 退栈，访问，转右子树printf(“d”，P 一data)；p=p 一rchild； InOrder【知识模块】 树和二叉树39 【正确答案】 算法的基本设计思想：借助队列和栈，先使用队列实现自上而下、自左而右的遍历。最后弹出栈中元素实现对二叉树按自下而上、自右而左的层次遍历。算法的代码：VOid InvertLevel(BiTree bt) 对二叉树按自下而上、自右而左的进行层次遍历if(bt!=NUL
41、L)StackInit(s)； 栈初始化，栈中存放二叉树结点的指针QueueInit(Q)； 队列初始化，队列中存放二叉树结点的指针QueueIn(Q，bt)；while(!QueueEmpty(Q) 自上而下层次遍历p=QueueOut(Q)； 出队push(S，p)， 入栈if(p-ichild) 若左子女不空，则入队列QueueIn(Q，P 一1chiid)；if(p-rchild) 若右子女不空，则入队列QueueIn(Q，P 一rchiid)；while(!StackEmpty(S) 自下而上、自右而左的层次遍历P=pop(S)；printf(“d”，P 一data)； if(bt!
42、=NULL) InvertLevel【知识模块】 树和二叉树40 【正确答案】 算法的基本设计思想：若 P 有左子树，则 q 是 P 的左子树上最左下的叶子结点；若 P 无左子树，仅有右子树，则 q 是 P 的右子树上最左下的叶子结点。算法的代码：BiTree PoStFirst(BiTree P)BiTree q=p；if(!q)return NULL；e1sewhile(q 一ichildq 一rchiid) 当 q 不是叶子结点if(q 一lchild)q=q-ichiid； 优先沿左分支向下去查 “最左下”的叶子结点elseq=q-rchiid； 沿右分支去查“最左下”的叶子结点ret
43、urn q；题目“求 P 所对应子树的第一个后序遍历结点”，蕴涵 P 是子树的根。若 P 是叶子结点，求其后继要通过双亲。【知识模块】 树和二叉树41 【正确答案】 算法的基本设计思想：叶子结点只有在遍历中才能知道。使用中序递归遍历，设置前驱结点指针 pre，初始为空。第一个叶子结点由指针 head 指向，遍历到叶子结点时，就将它前驱的 rehild 指针指向它，最后叶子结点的 rchild 为空。算法的代码：LinkList head，pre=NULL ； 全局变量LinkList InOrder(BiTree bt)中序遍历二叉树 bt，将叶子结点从左到右链成一个单链表，表头指针为 hea
44、dif(bt)InOrder(bt 一lchiid)； 中序遍历左子树if(bt 一lchild=NULL bt 一rchild=NULL) 叶子结点if(pre=NULL) 处理第一个叶子结点head=bt；pre=bt；e1Sef 将叶子结点链入链表pre 一rchiid=bt;pre=bt;InOrder(bt 一rchiid)； 中序遍历右子树pre 一rchild=NULL； 设置链表尾return head； InOrder时间复杂度为 0(n)，辅助变量使用 head 和 pre，栈空间复杂度为 0(n)。【知识模块】 树和二叉树42 【正确答案】 算法的基本设计思想：两棵空二叉树或仅有根结点的二叉树相似；对非空二叉树，可判左、右子树是否相似，采用递归的思想。算法的代码：int Similar(BiTree P，BiTree q)判断二叉树 P 和 q 是否相似if(p=NULLq=NULL)return 1；else if(!Pq I I p!q)return 0;elsereturn Similar(P 一lchiid，q 一1chiid)Similar(P 一rchiid，q 一rchild)； Similar【知识模块】 树和二叉树
