Python输入二叉树的先序和中序遍历,再输出后序遍历 Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作示例
稀里糊涂林老冷 人气:0本文实例讲述了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程序设计有所帮助。
加载全部内容