数据结构1800例题与答案之树和二叉树(6)

结点的形式为（值，左指针，右指针），分别用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分别 …… 此处隐藏：4368字，全部文档内容请下载后查看。喜欢就下载吧 ……