如何根据给定的两个二叉树遍历序列(前序中序、中序后序)确定二叉树

一、根据前序遍历和中序遍历确定二叉树

前序(根节点-左节点-右节点):A B D E H C F G

中序(左节点-根节点-右节点):D B E H A F C G

1、第一步:根据前序确定祖宗节点

根据前序就可以判断遍历的第一个就是祖宗节点,为A ,然后我们就可以把中序遍历以A节点分开。
如何根据给定的两个二叉树遍历序列(前序中序、中序后序)确定二叉树插图

2、第二步:确定左子树的根节点

再看前序A的后一个节点,为B,根据前序的性质为左子树的根节点,所以我们把中序遍历的B再次像之前那样截取出来。
如何根据给定的两个二叉树遍历序列(前序中序、中序后序)确定二叉树插图2

3、第三步:确定左子树的右边节点

由以上图可知,可以知道D就是左边的节点了

4、第四步:确定左子树的右边节点

ABD根据前序全部遍历完毕。再次依据上述方法构造左子树。在前序遍历和中序遍历H都在E的右边,为E的右节点。
如何根据给定的两个二叉树遍历序列(前序中序、中序后序)确定二叉树插图4

5、第五步:确定右子树

根据前序下一个字母为C,那么右子树的根节点就为C,然后再根据中序排序找出字母割分左右。
如何根据给定的两个二叉树遍历序列(前序中序、中序后序)确定二叉树插图6

全部步骤都已完成

二、根据后序遍历和中序遍历确定二叉树

中序(左节点-根节点-右节点):D B E H A F C G

后序(左节点-右节点-根节点):D H E B F G C A

1、第一步:根据后序确定祖宗节点

根据后序的性质,最后一个为祖宗节点,为A。然后我们割分中序的左右子树。
如何根据给定的两个二叉树遍历序列(前序中序、中序后序)确定二叉树插图8

2、第二步:同时割分左右子树

根据上面的区分我们同时割分后序,把左右子树的节点区分出来。
如何根据给定的两个二叉树遍历序列(前序中序、中序后序)确定二叉树插图10

3、第三步:确定左右子树根节点

由第二步可知,C和B为右子树和左子树的根节点,区分FG和DHE。画出中序的B和C节点,可以判断这两个节点左右节点各为多少。
如何根据给定的两个二叉树遍历序列(前序中序、中序后序)确定二叉树插图12

4、第四步:确定左右子树所有子节点

只有EH的判断了,根据中序排序(左节点-根节点-右节点)的规律,为以防万一,再加上后序排序(左节点-右节点-根节点)的规律。先以后序来看,E是根节点,那么H因为排在E的前面就不太清楚是E的左还是右节点,再来看中序,中序的H排在E的后面,就可以判定H是E的右节点,这是因为中序是左节点-根节点-右节点,如果H是E的左节点那必然排在E的前面,中序先遍历左节点。
如何根据给定的两个二叉树遍历序列(前序中序、中序后序)确定二叉树插图14

发表评论