文章内容
一、根据前序遍历和中序遍历确定二叉树
前序(根节点-左节点-右节点):A B D E H C F G
中序(左节点-根节点-右节点):D B E H A F C G
1、第一步:根据前序确定祖宗节点
根据前序就可以判断遍历的第一个就是祖宗节点,为A ,然后我们就可以把中序遍历以A节点分开。
![如何根据给定的两个二叉树遍历序列(前序中序、中序后序)确定二叉树插图 如何根据给定的两个二叉树遍历序列(前序中序、中序后序)确定二叉树插图](https://static.ntan520.com/blog-media/2022/07/8368e60879828a70ddf9c461fb15add5.png?x-oss-process=style/watermark)
2、第二步:确定左子树的根节点
再看前序A的后一个节点,为B,根据前序的性质为左子树的根节点,所以我们把中序遍历的B再次像之前那样截取出来。
![如何根据给定的两个二叉树遍历序列(前序中序、中序后序)确定二叉树插图2 如何根据给定的两个二叉树遍历序列(前序中序、中序后序)确定二叉树插图2](https://static.ntan520.com/blog-media/2022/07/15f519939217ee0dc18407f02da0543e.png?x-oss-process=style/watermark)
3、第三步:确定左子树的右边节点
由以上图可知,可以知道D就是左边的节点了
4、第四步:确定左子树的右边节点
ABD根据前序全部遍历完毕。再次依据上述方法构造左子树。在前序遍历和中序遍历H都在E的右边,为E的右节点。
![如何根据给定的两个二叉树遍历序列(前序中序、中序后序)确定二叉树插图4 如何根据给定的两个二叉树遍历序列(前序中序、中序后序)确定二叉树插图4](https://static.ntan520.com/blog-media/2022/07/9a91173f1df96f48c3fb0de6e2cdd6e0.png?x-oss-process=style/watermark)
5、第五步:确定右子树
根据前序下一个字母为C,那么右子树的根节点就为C,然后再根据中序排序找出字母割分左右。
![如何根据给定的两个二叉树遍历序列(前序中序、中序后序)确定二叉树插图6 如何根据给定的两个二叉树遍历序列(前序中序、中序后序)确定二叉树插图6](https://static.ntan520.com/blog-media/2022/07/86c240bfd46d29bc01eb40538317da9b.png?x-oss-process=style/watermark)
全部步骤都已完成
二、根据后序遍历和中序遍历确定二叉树
中序(左节点-根节点-右节点):D B E H A F C G
后序(左节点-右节点-根节点):D H E B F G C A
1、第一步:根据后序确定祖宗节点
根据后序的性质,最后一个为祖宗节点,为A。然后我们割分中序的左右子树。
![如何根据给定的两个二叉树遍历序列(前序中序、中序后序)确定二叉树插图8 如何根据给定的两个二叉树遍历序列(前序中序、中序后序)确定二叉树插图8](https://static.ntan520.com/blog-media/2022/07/bee22f2ba1d63347622b2ede334443b1.png?x-oss-process=style/watermark)
2、第二步:同时割分左右子树
根据上面的区分我们同时割分后序,把左右子树的节点区分出来。
![如何根据给定的两个二叉树遍历序列(前序中序、中序后序)确定二叉树插图10 如何根据给定的两个二叉树遍历序列(前序中序、中序后序)确定二叉树插图10](https://static.ntan520.com/blog-media/2022/07/7de004c4311c7a138c3bb29f62850ef1.png?x-oss-process=style/watermark)
3、第三步:确定左右子树根节点
由第二步可知,C和B为右子树和左子树的根节点,区分FG和DHE。画出中序的B和C节点,可以判断这两个节点左右节点各为多少。
![如何根据给定的两个二叉树遍历序列(前序中序、中序后序)确定二叉树插图12 如何根据给定的两个二叉树遍历序列(前序中序、中序后序)确定二叉树插图12](https://static.ntan520.com/blog-media/2022/07/086b9612f2fa5991f8461c6eb37b4fba.png?x-oss-process=style/watermark)
4、第四步:确定左右子树所有子节点
只有EH的判断了,根据中序排序(左节点-根节点-右节点)的规律,为以防万一,再加上后序排序(左节点-右节点-根节点)的规律。先以后序来看,E是根节点,那么H因为排在E的前面就不太清楚是E的左还是右节点,再来看中序,中序的H排在E的后面,就可以判定H是E的右节点,这是因为中序是左节点-根节点-右节点,如果H是E的左节点那必然排在E的前面,中序先遍历左节点。
![如何根据给定的两个二叉树遍历序列(前序中序、中序后序)确定二叉树插图14 如何根据给定的两个二叉树遍历序列(前序中序、中序后序)确定二叉树插图14](https://static.ntan520.com/blog-media/2022/07/3ac6c7079b3dcb2ec6f641a10ca79993.png?x-oss-process=style/watermark)