Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作示例
本文实例讲述了Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作。分享给大家供大家参考,具体如下:
实现一个功能:
输入:一颗二叉树的先序和中序遍历
输出:后续遍历
思想:
先序遍历中,第一个元素是树根
在中序遍历中找到树根,左边的是左子树右边的是右子树
Python代码:
#-*-coding:utf-8-*- deffromFMtoL(mid): globallas#全局后序遍历 globalfir#先序遍历 root=fir[0]#取出当前树根 fir=fir[1:]#取出树根后先序遍历把根拿出来下面一个元素做树根 root_po=mid.find(root)#在中序遍历当中树根的位置 left=mid[0:root_po]#左子树 right=mid[root_po+1:len(mid)]#右子树 ''' 后序遍历:左右根 先左子树再右子树最后跟 ''' #有左子树的时候 iflen(left)>0: fromFMtoL(left) #有右子树的时候 iflen(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程序设计有所帮助。