一棵二叉树的先序 中序和后序序列如下 其中有部分未标出 试构造出该二叉树。 先序序列为：一一CDE
序列,部分,正确答案
已帮助 人
一棵二叉树的先序、中序和后序序列如下，其中有部分未标出，试构造出该二叉树。 先序序列为：一一CDE—GHI一K 中序序列为：C B一一F A—J K I G 后序序列为：一E F D B—J I H—A 【电子科技大学2001三、1(5分)】【厦门大学2002七、l(6分)】
请帮忙给出正确答案和分析，谢谢！
-
正确答案：本题解答原理及方法如下：首先掌握先序遍历是“根一左一右”中序遍历是“左一根一右”后序遍历是“左一右一根”。从给定条件的后序序列中最后元素A是根。到中序序列中找到AA将序列分成左右两部分：左边5个元素形成二叉树的左子树右边5个元素形成二叉树的右子树。这样先序序列从第2个元素开始的5个元素是二叉树左子树的先序序列后面的5个元素形成二叉树右子树的先序序列。同理后序序列也可以确定左右子树各有5个元素。先画左子树还是右子树都一样按习惯我们先画出左子树。从后序序列知B是左子树的根到左子树的中序序
本题解答原理及方法如下：首先掌握先序遍历是“根一左一右”中序遍历是“左一根一右”,后序遍历是“左一右一根”。从给定条件的后序序列中,最后元素A是根。到中序序列中找到A,A将序列分成左右两部分：左边5个元素形成二叉树的左子树,右边5个元素形成二叉树的右子树。这样,先序序列从第2个元素开始的5个元素是二叉树左子树的先序序列,后面的5个元素形成二叉树右子树的先序序列。同理,后序序列也可以确定左右子树各有5个元素。先画左子树还是右子树都一样,按习惯,我们先画出左子树。从后序序列知,B是左子树的根,到左子树的中序序