3.〖01年计算机研题〗【严题集627⑧】给定二叉树的两种遍历序列,分别是: 前序遍历序列:D,A,C,E,B,H,F,G,I:中序遍历序列:D,C,B,E,H,A,G,I,F, 试画出二叉树B,并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法 解:方法是:由前序先确定root由中序可确定root的左、右子树。然后由其左子树的元素集合和右子树 的集合对应前序遍历序列中的元素集合,可继续确定ro的左右孩子。将他们分别作为新的root,不断递 归,则所有元素都将被唯一确定,问题得解 H 4.【计算机研2000给定如图所示二叉树T,请画出与其对应的中序线索二叉树 解:要遵循中序遍历的轨迹来画出每个前驱和后继。 中序遍历序列:5540256028083354 40 五、阅读分析题(每题5分,共20分) 1.(P604-26)试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列 答:DLR: ABDFJGKCEHIL M LDR: BFJDGKACHELIM LRD:JFKGDBHLMIECA 2.(P604-27)把如图所示的树转化成二叉树 答:注意全部兄弟之间都要连线(包括度为2的兄 弟),并注意原有连线结点一律归入左子树,新添 连线结点一律归入右子树。4 3. 〖01 年计算机研题〗【严题集 6.27③】给定二叉树的两种遍历序列，分别是： 前序遍历序列：D，A，C，E，B，H，F，G，I； 中序遍历序列：D，C，B，E，H，A，G，I，F， 试画出二叉树 B，并简述由任意二叉树 B 的前序遍历序列和中序遍历序列求二叉树 B 的思想方法。 解：方法是：由前序先确定 root，由中序可确定 root 的左、右子树。然后由其左子树的元素集合和右子树 的集合对应前序遍历序列中的元素集合，可继续确定 root 的左右孩子。将他们分别作为新的 root，不断递 归，则所有元素都将被唯一确定，问题得解。 D A C F E G B H I 4.【计算机研 2000】给定如图所示二叉树 T，请画出与其对应的中序线索二叉树。 解：要遵循中序遍历的轨迹来画出每个前驱和后继。 中序遍历序列：55 40 25 60 28 08 33 54 28 25 33 40 60 08 54 55 五、阅读分析题（每题 5 分，共 20 分） 1. （P60 4-26）试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。 答：DLR：A B D F J G K C E H I L M LDR: B F J D G K A C H E L I M LRD：J F K G D B H L M I E C A 2. （P60 4-27）把如图所示的树转化成二叉树。 答：注意全部兄弟之间都要连线（包括度为 2 的兄 弟）,并注意原有连线结点一律归入左子树，新添 连线结点一律归入右子树。 A B E C K F H D L G I M J 28 25 33 40 60 08 54 2 55 8 2 5 4 0 5 55 5 6 0 3 3 0 8 54 N I L N I L