二叉树已知后序序列和中序序列,或已知前序序列和中序序列,画出二叉树(简单易懂)

中序后序画树模板:

step1:找到根并输出

step2:将中序,后序各分为左右两棵子树;

step3:递归,重复step1,2;

(前序中序画树也是差不多按以上模板格式来)

下面是具体例子分析:

题目1:某二叉树前序序列为ABDGHCEFI,中序序列为GDHBAECIF,请画出二叉树。

题目2:某二叉树中序序列为ABCDEFG,后序序列为BDCAFGE,则前序序列是___EACBDGF _____。

温馨提示:建议边看步骤边动笔跟着画~

题目1:某二叉树前序序列为ABDGHCEFI,中序序列为GDHBAECIF,请画出二叉树。

First,前序序列第一个字母即为二叉树顶点,依题意得顶点为A。

《二叉树已知后序序列和中序序列,或已知前序序列和中序序列,画出二叉树(简单易懂)》

Second,在中序序列找到A的位置,排在A左边的所有字母(GDHB)组成左子树,排在A右边的所有字母(ECIF)组成右子树。

《二叉树已知后序序列和中序序列,或已知前序序列和中序序列,画出二叉树(简单易懂)》

注意!接下来是关键两步,这两步搞懂,后面依样画葫芦即可。

Third,看一下中序序列左子树部分(GDHB)在前序序列中的顺序,前序序列包含左子树部分的序列是(BDGH),由B排在第一个可知,B就是左子树的根结点;同理,看一下中序序列右子树部分(ECIF)在前序序列中的顺序,前序序列包含右子树部分的序列是(CEFI),由C排在第一个可知,C就是右子树的根结点。

《二叉树已知后序序列和中序序列,或已知前序序列和中序序列,画出二叉树(简单易懂)》

Fourth,求出左右子树的根结点后,我们只看中序序列,中序序列左子树部分(GDHB),因为GDH在根结点B左边,所以GDH是B的左子树;同理中序序列右子树部分(ECIF),因为E在根结点C左边,所以E组成C的左子树;因为IF在根结点C的右边,所以IF组成C的右子树。

《二叉树已知后序序列和中序序列,或已知前序序列和中序序列,画出二叉树(简单易懂)》

Fifth,重复第三步,看一下剩下的中序序列左子树部分(GDH)在前序序列中的顺序,前序序列包含左子树部分的序列此时是(DGH),可知D在第一个,所以D就是B的左子树的根结点;同理,看一下剩下的中序序列C的右子树部分(IF)在前序序列中的顺序,前序序列包含该左子树部分的序列此时是(FI),可知F在第一个,所以F就是C的右子树的根结点。

《二叉树已知后序序列和中序序列,或已知前序序列和中序序列,画出二叉树(简单易懂)》

Sixth,重复第四步,我们只看中序序列,此时中序序列左子树剩下部分(GDH),因为G在D左边,那G就是D的左子树;H在D右边,那H就是D的右子树。此时中序序列右子树剩下部分(IF),因为I在F左边,那I就是F的左子树。

《二叉树已知后序序列和中序序列,或已知前序序列和中序序列,画出二叉树(简单易懂)》

Seventh,如果还有结点没画完的话,重复三、四步即可。

按照上述方法一步步来,整棵二叉树就画好啦!ヽ(*^ー^)人(^ー^*)ノ

已知后序序列和中序序列,画二叉树,步骤跟上面差不多。

题目2:某二叉树中序序列为ABCDEFG,后序序列为BDCAFGE,则前序序列是___EACBDGF _____。

First,后序序列最后一个字母即为二叉树顶点,依题意得顶点为E。

《二叉树已知后序序列和中序序列,或已知前序序列和中序序列,画出二叉树(简单易懂)》

Second,在中序序列找到E的位置,排在E左边的所有字母(ABCD)组成左子树,排在E右边的所有字母(FG)组成右子树。

《二叉树已知后序序列和中序序列,或已知前序序列和中序序列,画出二叉树(简单易懂)》

接下来是关键步骤:

Third,看一下中序序列左子树部分(ABCD)在后序序列中的顺序,后序序列包含左子树部分的序列是(BDCA),由A排在最后一个可知,A就是左子树的根结点;同理,看一下中序序列右子树部分(FG),后序序列包含右子树部分的序列是(FG),由G排在最后一个可知,G就是右子树的根结点。

《二叉树已知后序序列和中序序列,或已知前序序列和中序序列,画出二叉树(简单易懂)》

Fourth,求出左右子树的根结点后,我们只看中序序列,中序序列左子树部分(ABCD),因为BCD在根结点A右边,所以BCD是A的右子树;同理中序序列右子树部分(FG),因为F在根结点G左边,所以F组成G的左子树。

《二叉树已知后序序列和中序序列,或已知前序序列和中序序列,画出二叉树(简单易懂)》

Fifth,重复第三步,看一下剩下的中序序列左子树部分(BCD)在后序序列中的顺序,后序序列包含左子树部分的序列此时是(BDC),可知C在最后一个,所以C就是A的右子树的根结点;这里右子树已经排完了,就不用再看了。

《二叉树已知后序序列和中序序列,或已知前序序列和中序序列,画出二叉树(简单易懂)》

Sixth,重复第四步,我们只看中序序列,此时中序序列左子树剩下部分(BCD),因为B在C左边,那B就是C左子树;D在C右边,那D就是C右子树。

《二叉树已知后序序列和中序序列,或已知前序序列和中序序列,画出二叉树(简单易懂)》

如有错误,还请指出。

码字不易,给个赞让更多人看到吧 (*^▽^*)~

    原文作者:Curz酥
    原文地址: https://blog.csdn.net/m0_56494923/article/details/122294917
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞