结点的形式为（值，左指针，右指针），分别用tree[i].v，tree[i].l，tree[i].r来表示第i个结点的值，左指针，右指针，其中左，右指针的值为所指结点在数组中的下标，若指针的值为0，表示它指向空树，图中指针root用以指向二叉树的根结点。问题： （1）填充流程图中的①、②、③，使其按中序遍历二叉树。
（2）把流程图中的（A）框移至哪个位置（图中Ⅰ～Ⅸ）使流程图的算法从中序遍历变成后序遍历。
【上海海运学院 1997年 四、（13分）】
46．设一棵二叉树的先序、中序遍历序列分别为
先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C （1）画出这棵二叉树。
（2）画出这棵二叉树的后序线索树。 （3）将这棵二叉树转换成对应的树（或森林）。【南京航空航天大学 1997 二、 (10分)】 47．已知一棵二叉树的对称序和后序序列如下： 对称序：GLDHBEIACJFK 后序： LGHDIEBJKFCA (1) （2分)给出这棵二叉树： (2) （2分)转换为对应的森林：
(3) （4分)画出该森林的带右链的先根次序表示法：
Itag=
(4) (4分) 画出该森林带度数的后根次序表示法：
(5) (4分)在带度数的后根次序表示法中，不包含指针，但仍能完全反映树的结构。写出以结点x为根的子树在后根次序序列中的前驱的求法。（用语言叙述，不用写算法）【山东大学 1998 八、（16分）】
48．设某二叉树的前序遍历序列为:ABCDEFGGI，中序遍历序列为:BCAEDGHFI：
（1）试画出该二叉树；
（2）写出由给定的二叉树的前序遍历序列和中序遍历序列构造出该二叉树的算法。 （3）设具有四个结点的二叉树的前序遍历序列为ａｂｃｄ；Ｓ为长度等于四的由ａ，ｂ，ｃ，ｄ排列构成的字符序列，若任取Ｓ作为上述算法的中序遍历序列，试问是否一定能构造出相应的二叉树，为什么？试列出具有四个结点二叉树的全部形态及相应的中序遍历序列。
【浙江大学 1997 六、 (15分)】
类似本题的另外叙述有： （1）已知二叉树的先序序列: CBHEGAF, 中序序列: HBGEACF, 试构造该二叉树
【北京理工大学 2001 八、2 （4分）】
（2）已知二叉树按中序排列为BFDAEGC，按前序排列为ABDFCEG，要求画出该二叉树。
【山东师范大学 1996 五、1 (2分)】
（3）已知一棵二叉树的前序序列 A,B,D,C,E,F，中序序列B,D,A,E,F,C. 画出这棵二叉树。
【燕山大学 1999 四、 (5分)】
（4）已知一棵二叉树的前序遍历结果是：ABCDEFGHIJ,中序遍历的结果是：BCEDAGHJIF,试画出这棵二叉树。【厦门大学 1998 六、1 （7分)】
（5）已知二叉树BT各结点的先序、中序遍历序列分别为ABCDEGF和CBAEDF，试画出该二叉树。
【北京工业大学 1998 二、 (6分)】
49. 假设一棵二叉树的前序序列为ABCD,它的中序序列可能是DABC吗?【石油大学1998一、1(5分)】
类似本题的另外叙述有： （1）一棵前序序列为1，2，3，4，的二叉树，其中序序列可能是4，1，2，3吗？设一棵二叉树的前序序列为1，2，3，4，5，6，7，8，9，其中序序列为2，3，1，5，4，7，8，6，9，试画出该二叉树。
【东南大学 1996一、2 （7分) 1998 一、3】
50．一棵非空的二叉树其先序序列和后序序列正好相反，画出这棵二叉树的形状。 【西安电子科技大学2000软件 一、8 （5分）】
51．已知一棵二叉树的后序遍历序列为EICBGAHDF，同时知道该二叉树的中序遍历序列为CEIFGBADH，试画出该二叉树。【重庆大学 2000 二、2】
类似本题的另外叙述有： （1）已知二叉树ＢＴ各结点的中序和后序序列分别为ＤＦＢＡＣＥＧ和ＦＤＢＧＥＣＡ，试构造出该二叉树ＢＴ，并作简要说明。【北方交通大学 1997 二、 (8分)】
（2）已知二叉树的中序遍历序列为G F B E A N H M，后序遍历的结点序列为G E B F H N M A ，画出此二叉树的形态。【青岛海洋大学 1999 一、5（5分)】
（3）已知二叉树的后序序列为ABCDEFG 和中序序列为ACBGEDF，构造出该二叉树。
【福州大学 1998 三、1 (6分)】
（4）已知某二叉树的后序遍历和中序遍历如下，构造出该二叉树。
后序遍历序列： G D B E I H F C A 中序遍历序列：D G B A E C H I F 【厦门大学 2000 七、1 （20%/3分)】
（5）已知一个二分树的中序序列和后序序列如下：
中序：A B C D E F G H I J 后序：A C D B H J I G F E 试画出此二分树的结构。 【首都经贸大学 1998 二、1 （10分）】
52．假设一棵二叉树的层次序列为ABCDEFGHIJ，中序序列DBGEHJACIF。请画出这棵二叉树。
【武汉大学 2000 三、1】【东南大学 2000 一、1 （6分）】
类似本题的另外叙述有： （1）假设一棵二叉树的层次次序（按层次递增顺序排列，同一层次自左向右）为
ABECFGDHI,中序序列为BCDAFEHIG。请画出该二叉树，并将其转换为对应的森林。【山东大学 2001 四、 (6分)】
53. 已知一个森林的先序序列和后序序列如下，请构造出该森林。 先序序列：ABCDEFGHIJKLMNO
后序序列：CDEBFHIJGAMLONK 【合肥工业大学 2000 四、1 （5分）】 54． 画出同时满足下列两条件的两棵不同的二叉树。 (1)按先根序遍历二叉树顺序为ABCDE。 (2)高度为5其对应的树（森林）的高度最大为4。【东北大学 1997 一、3 （5分）】 55．用一维数组存放的一棵完全二叉树；ABCDEFGHIJKL。请写出后序遍历该二叉树的访问结点序列。
【西安电子科技大学1999计应用 一、6 （5分）】
56．一棵二叉树的先序、中序、后序序列如下，其中一部分未标出，请构造出该二叉树。 先序序列 ：_ _ C D E _ G H I _ K 中序序列 ：C B _ _ F A _ J K I G
后序序列 ：_ E F D B _ J I H _ A 【厦门大学 2002 七、1 （6分)】
类似本题的另外叙述有： （1）一棵二叉树的先序、中序和后序序列分别如下，其中有一部分为显示出来。试求出空格处的内容，并画出该二叉树。
先序序列: _ B F I C E H G 中序序列：D K F I A E J C
后序序列： K F B H J G A 【西安电子科技大学2000计应用 五、2 （5分)】
（2）已知一棵二叉树的先序 中序和后序序列如下，其中空缺了部分，请画出该二叉树。 先序：_ B C _ E F G _ I J K _ 中序：C B E D _ G A J _ H _ L
后序：_ E _ F D _ J _ L _ H A 【合肥工业大学 2001 四、1 （5分)】
（3）已知含有8个结点的一棵二叉树，按先序、中序、后序进行遍历后，有些结点序号不清楚如下图示。要求构造出一棵符合条件的二叉树。 先根序遍历 _ 2 3 _ 5 _ 7 8 中根序遍历 3 _ 4 1 _ 7 8 6
后根序遍历 _ 4 2 _ _ 6 5 1 【东北大学 1996 一、3 （5分）】
57．M 叉树的前序和后序遍历分别与由它转换成的二叉树的哪种遍历相对应？
【中国人民大学 2000 一、2 （4分）】
58．证明：在二叉树的三种遍历序列中，所有叶子结点间的先后关系都是相同的。要求每步论断都指出根据。【北京工业大学 2001 二、3 （5分）】
59. 下表中M﹑N分别是一棵二叉树中的两个结点，表中行号i=1，2，3，4分别表示四种M﹑N的相对关系，列号j=1，2，3分别表示在前序、中序、后序遍历中M,N之间的先后次序关系。要求在i，j所表示的关系能够发生的方格内打上对号。例如：如果你认为n是m的祖先，并且在中序遍历中n能比m先被访问，则在（3，2）格内打上对号
先根遍历时n先被访问 中根遍历时n先被访问 后根遍历时n先被访问 N在M的左边 N在M的右边 N是M的祖先 N是M的子孙 【南京理工大学 2001 四、 (10分)】
60．用一维数组存放的一棵完全二叉树如下图所示：
A B C D E F G H I J K L 写出后序遍历该二叉树时访问结点的顺序。
【北京工业大学 1996 一、4 （6分）】
61．设树形T在后根次序下的结点排列和各结点相应的次数如下：
后根次序：ＢＤＥＦＣＧＪＫＩＬＨＡ 次 数：００００３０００２０２４
请画出Ｔ的树形结构图。 【吉林大学 2001 一、2 （4分）】 62．已知二叉树采用二叉链表方式存放，要求返回二叉树T的后序序列中的第一个结点的指针，是否可不用递归且不用栈来完成？请简述原因。【西北大学 2001 三 6】
63．对于二叉树T的两个结点n1和n2，我们应该选择树T结点的前序、中序和后序中哪两个序列来判断结点n1必定是结点n2的祖先,并给出判断的方法。不需证明判断方法的正确性。
【复旦大学 1999 五 (10分)】
64．设二叉树的存储结构如下(每题5分,共15分)
LINK 0 0 2 3 7 5 8 0 10 1 INFO J H F D B A C E G I RLINK 0 0 0 9 4 0 0 0 0 0 其中,T为树根结点的指针,LLINK、RLINK分别指向结点的左右子女,INFO为其数据域,请完成下列各题:
（1）画出二叉树T的逻辑结构. （2）写出按前序、中序和后序周游二叉树T得到的结点序列. （3）画出二叉树T的后序线索树。 【山东工业大学 1995 六、（15分）】 65．在二叉树的前序遍历和中序遍历的递归算法中，最后一个递归调用语句在调用时所保留的参数有什么作用？如何清除最后这个递归语句？【北京邮电大学 1994 三、 (8分)】 66．在二叉树的Ｌlink-Rlink存储表示中，引入“线索”的好处是什么？
【山东大学 1999 六、１(２分）】
67．按下面要求解下图中二叉树的有关问题：
(1)对此二叉树进行后序后继线索化 ；(2)将此二叉树变换为森林； (3)用后根序遍历该森林，；写出遍历后的结点序列。【北京邮电大学 1996 五、 (10分)】
类似本题的另外叙述有： （1）已知一棵二叉树的先序遍历序列为：AEFBGCDHIKJ，中序遍历序列为：EFAGBCHKIJD。试写出此二叉树的后序遍历序列，并用图画出它的后序线索二叉树。【同济大学 2000 一、 (10分)】
68．对下图所示二叉树分别按前序﹑中序﹑后序遍历，
A 给出相应的结点序列，同时给二叉树加上中序线索。
E 【青岛海洋大学 1999年一、1 （5分）】 B C K F D I G L J M H O N P
第67题图
69. 假设一个二叉树的两种遍历如下：
前序：ABFGCHDEIJLK 中序：FGBHCDILJKEA （1）画出这棵二叉树以及它的中序线索树；
（2）写出在中序线索树的情况下，找到结点N的前驱结点的算法INORDER-PRIOR(N,X) 【上海海运学院 1996 四、 (10分)】
70．已知一棵二叉树的中序（或中根）遍历结点排列为DGBAECHIF，后序（或后根）遍历结点排列为GDBEIHFCA， （1）试画出该二叉树；
（2）试画出该二叉树的中序穿线（或线索）树； （3）试画出该二叉树（自然）对应的森林；【吉林大学 2000 一、1 （5分）】 71．设二叉树BT的存储结构如下:
1 2 3 4 5 6 7 8 9 10
Lchild Data Rchild 0 0 J H 0 0 2 F 0 3 D 7 B 5 A 8 C 0 10 1 I 0 0 E G 9 4 0 0 0 其中BT为树根结点的指针，其值为6,Lchild,Rchild分别为结点的左、右孩子指针域,data为结点的数据域。试完成下列各题:
（l）画出二叉树BT的逻辑结构;
（2）写出按前序、中序、后序遍历该二叉树所得到的结点序列; （3）画出二叉树的后序线索树。【中国矿业大学 2000 二、 (15分)】
72．请说明是否存在这样的二叉树，即它可以实现后序线索树进行后序遍历时不使用栈；而对前序线索树进行前序遍历时，又有什么样的二叉树可不使用栈。【西安电子科技大学 1996 二、1 (5分）】
73．一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为多少？
【西安电子科技大学 2000计应用 一、2 （5分）】 74．在前序线索树上，要找出结点p的直接后继结点，请写出相关浯句。结点结构为(ltag,lc,data,rtag,rc)。【西北大学 2000 二、6 （5分）】
75．对于后序线索二叉树，怎样查找任意结点的直接后继；对于中序线索二叉树，怎样查找任意结点的直接前驱？【西北工业大学 1998 一、4 （4分）】
76．将下列树的孩子—兄弟链表改为后根遍历全线索链表。【清华大学 1994 二、 (10分)】 Data A Ltag 0 Fch 2 Rtag 0 B 0 0 0 C 0 5 0 D 0 7 0 E 0 8 0 F 0 0 0 G 0 11 0 H 0 0 0 I 0 0 0 J 0 0 0 K 0 0 0