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程序设计有所帮助。

赞 (0)

相关推荐

  • python字典键值对的添加和遍历方法

    添加键值对 首先定义一个空字典 >>> dic={} 直接对字典中不存在的key进行赋值来添加 >>> dic['name']='zhangsan' >>> dic {'name': 'zhangsan'} 如果key或value都是变量也可以用这种方法 >>> key='age' >>> value=30 >>> dic[key]=value >>> dic {'age': 30

  • Python实现重建二叉树的三种方法详解

    Python实现重建二叉树的三种方法详解

    本文实例讲述了Python实现重建二叉树的三种方法.分享给大家供大家参考,具体如下: 学习算法中,探寻重建二叉树的方法: 用input 前序遍历顺序输入字符重建 前序遍历顺序字符串递归解析重建 前序遍历顺序字符串堆栈解析重建 如果懒得去看后面的内容,可以直接点击此处本站下载完整实例代码. 思路 学习算法中,python 算法方面的资料相对较少,二叉树解析重建更少,只能摸着石头过河. 通过不同方式遍历二叉树,可以得出不同节点的排序.那么,在已知节点排序的前提下,通过某种遍历方式,可以将排序进行解析

  • python 使用turtule绘制递归图形（螺旋、二叉树、谢尔宾斯基三角形）

    插图工具使用Python内置的turtle模块,为什么叫这个turtle乌龟这个名字呢,可以这样理解,创建一个乌龟,乌龟能前进.后退.左转.右转,乌龟的尾巴朝下,它移动时就会画一条线.并且为了增加乌龟画图的艺术价值,可以改变尾巴宽度和尾巴浸入墨水的颜色. 1.递归绘制螺旋 先用我们让乌龟以line_len长度前进,然后向右旋转90°,然后缩短line_len长度递归调用draw_spiral函数 import turtle my_turtle = turtle.Turtle() my_win =

  • Python遍历pandas数据方法总结

    Python遍历pandas数据方法总结

    前言 Pandas是python的一个数据分析包,提供了大量的快速便捷处理数据的函数和方法.其中Pandas定义了Series 和 DataFrame两种数据类型,这使数据操作变得更简单.Series 是一种一维的数据结构,类似于将列表数据值与索引值相结合.DataFrame 是一种二维的数据结构,接近于电子表格或者mysql数据库的形式. 在数据分析中不可避免的涉及到对数据的遍历查询和处理,比如我们需要将dataframe两列数据两两相除,并将结果存储于一个新的列表中.本文通过该例程介绍对pa

  • Python 二叉树的层序建立与三种遍历实现详解

    Python 二叉树的层序建立与三种遍历实现详解

    前言 二叉树(Binary Tree)时数据结构中一个非常重要的结构,其具有....(此处省略好多字)....等的优良特点. 之前在刷LeetCode的时候把有关树的题目全部跳过了,(ORZ:我这种连数据结构都不会的人刷j8Leetcode啊!!!) 所以 !!!敲黑板了!!!今天我就在B站看了数据结构中关于树的内容后,又用我浅薄的Python大法来实现一些树的建立和遍历. 关于树的建立我觉得层序建立对于使用者来说最为直观,输入很好写.(好吧,我是看LeetCode中的树输入都是采用层序输入觉得

  • python数据结构之二叉树的建立实例

    先建立二叉树节点,有一个data数据域,left,right 两个指针域 复制代码 代码如下: # -*- coding: utf - 8 - *- class TreeNode(object): def __init__(self, left=0, right=0, data=0):        self.left = left        self.right = right        self.data = data 复制代码 代码如下: class BTree(object):

  • Python实现输入二叉树的先序和中序遍历，再输出后序遍历操作示例

    本文实例讲述了Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作.分享给大家供大家参考,具体如下: 实现一个功能: 输入:一颗二叉树的先序和中序遍历     输出:后续遍历 思想: 先序遍历中,第一个元素是树根     在中序遍历中找到树根,左边的是左子树 右边的是右子树 Python代码: # -*- coding:utf-8 -*- def fromFMtoL( mid ): global las #全局后序遍历 global fir #先序遍历 root = fir[0] #取

  • PHP根据树的前序遍历和中序遍历构造树并输出后序遍历的方法

    本文实例讲述了PHP根据树的前序遍历和中序遍历构造树并输出后序遍历的方法.分享给大家供大家参考,具体如下: 先来看看前序遍历.中序遍历与后序遍历原理图: 根据树的前序遍历和中序遍历构造树并输出后序遍历代码如下: <?php class BinaryTreeNode{ public $m_value; public $m_left; public $m_right; } function ConstructCore($preorder,$inorder){ if(count($preorder)!

  • Python实现将SQLite中的数据直接输出为CVS的方法示例

    本文实例讲述了Python实现将SQLite中的数据直接输出为CVS的方法.分享给大家供大家参考,具体如下: 对于SQLite来说,目前查看还是比较麻烦,所以就像把SQLite中的数据直接转成Excel中能查看的数据,这样也好在Excel中做进一步分数据处理或分析,如前面文章中介绍的<使用Python程序抓取新浪在国内的所有IP>.从网上找到了一个将SQLite转成CVS的方法,贴在这里,供需要的朋友使用: import sqlite3 import csv, codecs, cStringI

  • Python中list查询及所需时间计算操作示例

    本文实例讲述了Python中list查询及所需时间计算操作.分享给大家供大家参考,具体如下: # -*-coding=utf-8 -*- #! python2 #filename: list_query #date: 2018-03-25 #author: guosw import time def cost_time(fun): def cost(*args,**kwargs): stime = time.time() x = fun(*args,**kwargs) etime = time.

  • C语言数据结构二叉树先序、中序、后序及层次四种遍历

    C语言数据结构二叉树先序、中序、后序及层次四种遍历

    目录 一.图示展示 (1)先序遍历 (2)中序遍历 (3)后序遍历 (4)层次遍历 (5)口诀 二.代码展示 一.图示展示 (1)先序遍历 先序遍历可以想象为,一个小人从一棵二叉树根节点为起点,沿着二叉树外沿,逆时针走一圈回到根节点,路上遇到的元素顺序,就是先序遍历的结果 先序遍历结果为:A B D H I E J C F K G 动画演示: 记住小人沿着外围跑一圈(直到跑回根节点),多看几次动图便能理解 (2)中序遍历 中序遍历可以看成,二叉树每个节点,垂直方向投影下来(可以理解为每个节点从最

  • C语言二叉树常见操作详解【前序,中序,后序,层次遍历及非递归查找,统计个数,比较,求深度】

    C语言二叉树常见操作详解【前序,中序,后序,层次遍历及非递归查找,统计个数,比较,求深度】

    本文实例讲述了C语言二叉树常见操作.分享给大家供大家参考,具体如下: 一.基本概念 每个结点最多有两棵子树,左子树和右子树,次序不可以颠倒. 性质: 1.非空二叉树的第n层上至多有2^(n-1)个元素. 2.深度为h的二叉树至多有2^h-1个结点. 满二叉树:所有终端都在同一层次,且非终端结点的度数为2. 在满二叉树中若其深度为h,则其所包含的结点数必为2^h-1. 完全二叉树:除了最大的层次即成为一颗满二叉树且层次最大那层所有的结点均向左靠齐,即集中在左面的位置上,不能有空位置. 对于完全二叉

  • N叉树的三种遍历(层次遍历、前序遍历、后序遍历)

    N叉树的三种遍历(层次遍历、前序遍历、后序遍历)

    目录 题目链接: 1.层次遍历 2.前序遍历 3.后序遍历 题目链接: 590.N叉树的后序遍历 429.N叉树的层序遍历 598.N叉树的前序遍历 1.层次遍历 """ # Definition for a Node. class Node: def __init__(self, val=None, children=None): self.val = val self.children = children """ class Solutio

  • Python二叉树的遍历操作示例【前序遍历,中序遍历,后序遍历,层序遍历】

    本文实例讲述了Python二叉树的遍历操作.分享给大家供大家参考,具体如下: # coding:utf-8 """ @ encoding: utf-8 @ author: lixiang @ email: lixiang_cn@foxmail.com @ python_version: 2 @ time: 2018/4/11 0:09 @ more_info: 二叉树是有限个元素的集合,该集合或者为空.或者有一个称为根节点(root)的元素及两个互不相交的.分别被称为左子树和

  • Python 递归式实现二叉树前序,中序,后序遍历

    Python 递归式实现二叉树前序,中序,后序遍历

    目录 1.前序遍历 2.中序遍历 3.后序遍历 4.测试 5.结果 6.补充 6.1N叉树前序遍历 记忆点: 前序:VLR 中序:LVR 后序:LRV 举例: 一颗二叉树如下图所示: 则它的前序.中序.后序遍历流程如下图所示: 1.前序遍历 class Solution:     def preorderTraversal(self, root: TreeNode):              def preorder(root: TreeNode):             if not ro

  • Python实现二叉树前序、中序、后序及层次遍历示例代码

    前言 树是数据结构中非常重要的一种,主要的用途是用来提高查找效率,对于要重复查找的情况效果更佳,如二叉排序树.FP-树.另外可以用来提高编码效率,如哈弗曼树. 用 Python 实现树的构造和几种遍历算法.实现功能如下: 树的构造 递归实现先序遍历.中序遍历.后序遍历 堆栈实现先序遍历.中序遍历.后序遍历 队列实现层次遍历 # -*- coding=utf-8 -*- class Node(object): """节点类""" def __ini

随机推荐