问答题 一棵二叉树的先序、中序和后序序列如下,其中有部分未标出,试构造出该二叉树。先序序列为:一一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是根。到中序序列中找到A,A将序列分成左右两部分:左边5个元素形成二叉树的左子树,右边5个元素形成二叉树的右子树。这样,先序序列从第2个元素开始的5个元素是二叉树左子树的先序序列,后面的5个元素形成二叉树右子树的先序序列。同理,后序序列也可以确定左右子树各有5个元素。先画左子树还是右子树都一样,按习惯,我们先画出左子树。从后序序列知,B是左子树的根,到左子树的中序序列中找到B,B的左面有一个元素C,这是B的左子女。B的右面有3个元素,即B的右子树有3个结点。从左子树的先序(或后序)序列中都能发现D是B的右子树的根。但是这时中序序列并未给出D,而是空格。这时B的右子树先序序列是“DE___”,中序序列是“___F”,后序序列是“EFD”,可以判定E是D的左子女,F是D的右子女。至此,整棵二叉树的左子树分析完毕。同样,也可以画出右子树。
【答案解析】