admin 管理员组

文章数量: 1086019


2024年4月22日发(作者：在线时钟)

有一二叉树， 前序遍历顺序为

a b c d e f g 中序遍历顺序为

b a d c f g e

二叉树：

前序遍历A-B-D-F-G-H-I-E-C

中序遍历F-D-H-G-I-B-E-A-C

后序遍历F-H-I-G-D-E-B-C-A

前序(根左右)，中序(左根右)，后序(左右根)

例题1:

已知某二叉树的前序遍历为A-B-D-F-G-H-I-E-C,中序遍历为

F-D-H-G-I-B-E-A-C,请还原这颗二叉树。

解题思路：

从前序遍历中，我们确定了根结点为A，在从中序遍历中得出

F-D-H-G-I-B-E在根结点的左边，C在根结点的右边，那么我

们就可以构建我们的二叉树的雏形。

那么剩下的前序遍历为B-D-F-G-H-I-E，中序遍历为F-D-H-G-

I-B-E， B就是我们新的“根结点”，从中序遍历中得出F-D-

H-G-I在B的左边，E在B的右边，继续构建

那么剩下的前序遍历为D-F-G-H-I，中序遍历为F-D-H-G-I，D

就是我们新的“根结点”，从中序遍历中得出F在D的左边，

H-G-I在D的右边，继续构建

那么剩下的前序遍历为G-H-I，中序遍历为H-G-I，G就是我

们新的“根结点”，从中序遍历中得出H在G的左边，I在G

的右边，继续构建

例题2：

已知某二叉树的中序遍历为F-D-H-G-I-B-E-A-C,后序遍历为

F-H-I-G-D-E-B-C-A,请还原这颗二叉树。

解题思路：

从后序遍历中，我们确定了根结点为A，在从中序遍历中得出

F-D-H-G-I-B-E 在根结点的左边，C在根结点的右边，那么我

们就可以构建我们的二叉树的雏形。之后就是新根节点B，

FDHGI在根左，E在根右。在之后就是新根D，F根左，HGI根

右，然后就差不多了。

就像恢复前中顺序的二叉树一样，我们也可以恢复中后顺序的

二叉树。

你不能用光学前序遍历和后序遍历来恢复二叉树。


本文标签： 遍历 二叉树 前序 中序 后序

版权声明：本文标题：有一二叉树, 前序遍历顺序为 a b c d e f g 中序遍历顺序为 b a d c 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1713730646a648899.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。