Python利用先序和中序遍历构建二叉树并输出后序遍历
发布时间：2026-10-13| 6人浏览过
本文介绍如何使用Python根据二叉树的先序和中序遍历序列还原树结构，并输出对应的后序遍历结果。核心思路是先序遍历的首元素为根节点，在中序遍历中定位根节点以划分左右子树，通过递归处理左右子树实现后序遍历。
本文通过Python代码演示如何根据二叉树的先序遍历和中序遍历序列，推导出后序遍历序列。该示例旨在为读者提供清晰的实现思路与代码参考。
具体实现目标如下：
输入：二叉树的先序遍历序列与中序遍历序列 输出：对应的后序遍历序列
核心算法逻辑：
在先序遍历序列中，第一个元素始终代表当前子树的根节点。 在中序遍历序列中查找该根节点的位置，根节点左侧的子序列构成左子树，右侧的子序列构成右子树。
Python实现代码如下：
# -*- coding:utf-8 -*-
def fromFMtoL( mid ):
global las #全局后序遍历
global fir #先序遍历
root = fir[0] #取出当前树根
fir = fir[1:] #取出树根后 先序遍历把根拿出来 下面一个元素做树根
root_po = mid.find( root ) #在中序遍历当中树根的位置
left = mid[0:root_po] #左子树
right = mid[root_po+1:len(mid)] #右子树
'''
后序遍历： 左 右 根
先左子树 再右子树 最后跟
'''
#有左子树的时候
if len(left) > 0:
fromFMtoL( left )
#有右子树的时候
if len(right) > 0:
fromFMtoL( right )
#树根写进结果
las += root
if __name__ == "__main__" :
# fir = input("请输入先序遍历：") #前序遍历的结果
# mid = input("请输入中序遍历：") #中序遍历的结果
fir = "DBACEGF"
mid = "ABCDEFG"
# fir = "ABC"
# mid = "BAC"
las = ""
fromFMtoL( mid )
print(las)
程序运行输出结果：
ACBFGED
如需进一步了解Python相关技术，可参考本站专题：《Python数据结构与算法教程》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》。
希望上述内容能协助读者掌握Python程序设计中的树遍历相关技巧。
免责声明：本文内容仅供参考，不代表本站观点。转载或引用请注明出处。
