您好、欢迎来到现金彩票网!
当前位置:大赢家 > 复位序列 >

某二叉树中序序列为ABCDEFG后序序列为BDCAFGE则前是?

发布时间:2019-08-06 23:47 来源:未知 编辑:admin

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  第一步先根据后序遍历的最后一个结点是根结点,判断E为根,根据中序则ABCD在E的右侧,FG在E的左侧。

  第二步根据中序ABCD和后序BDCA,判断A为这四个字母的根,并且BCD都在A的右侧,进一步根据中序BCD,后序BDC,判断C为这三个字母的根,且B在C的左侧,D在C的右侧。

  第三步根据中序FG和后序BDC,判断B为三个字母的根,且CD都在左侧,进一步根据中序CD和后序DC,判断C为两个字母的根,且D在C的右侧。

  1.首先看后序,整个二叉树的根肯定在后序的最后一个,所以E应该是整个二叉树的根。然后观察中序,整个二叉树可分为3个部分(ABCD)E(FG),ABCD是E的左子树部分,FG为E的右子树部分。结构如下:

  2.左子树部分的后序序列是BDCA,那么A肯定是这四个节点的根,在观察他们的中序序列为ABCD于是判断A节点肯定没有做子树,于是进一步推出该二叉树的结构如下:

  3.再根据BCD三个节点的后序序列所知,C一定是这三个节点的根节点,而根据他们的中序序列所得,B为C的左节点,D为C的右节点,于是可以推出该二叉树的左子树,结构如下:

  4.最后,根据E的右子树中FG的后序序列所得,G为E的右节点,而根据他们的中序序列所知F应该为G的左节点,于是,E的右子树的结构也推出,至此,整个二叉树的结构就完全得到,结构如下:

http://ccsagresso.com/fuweixulie/1229.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有