已知先序和中序遍历序列,怎么还原二叉树

作者:SeekFlaw 求瑕 内容组 · 发布于 2026-11-19 · 更新于 2026-11-19

回答

前提:各结点的值互不相同。先序序列的首个元素是根;在中序序列里找到这个根,它左边的是左子树的中序序列,右边的是右子树的中序序列。左子树的结点数 k 也就知道了,于是先序序列去掉根之后,前 k 个是左子树的先序,剩下的是右子树的先序。对左右两段分别递归即可。

步骤:1. 取先序首元素为根;2. 在中序里定位根,划分左右子树;3. 用左子树的结点数在先序里切分;4. 左右子树各自重复 1 到 3,直到序列为空。

后序加中序同理,只是取后序的末尾元素为根。先序加后序一般无法确定一棵固定的二叉树(只有单个子树时无法判断它是左还是右)。

例(自编):先序 A B D E C F,中序 D B E A F C。根 A;中序中 A 左边 D B E(3 个)是左子树,右边 F C 是右子树。先序里前 3 个 B D E 属左子树,C F 属右子树。左子树:先序 BDE、中序 DBE,根 B,左孩子 D,右孩子 E。右子树:先序 CF、中序 FC,根 C,F 在 C 左边,是 C 的左孩子。

该树后序遍历为 D E B F C A(用 Python 递归还原后核对得同样结果)。

依据:数据结构课程通行的二叉树遍历序列与二叉树还原的结论。

用这个问题生成复习导图 打开官方导图,复制到我的空间

相关官方导图:考研 408 · 数据结构算法题与复杂度

标签:计算机408数据结构二叉树先序遍历中序遍历