Python利用前序和中序遍历结果重建二叉树的方法
本文实例讲述了Python利用前序和中序遍历结果重建二叉树的方法。分享给大家供大家参考,具体如下:
题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
这道题比较容易,前序遍历的结果中,第一个结点一定是根结点,然后在中序遍历的结果中查找这个根结点,根结点左边的就是左子树,根结点右边的就是右子树,递归构造出左、右子树即可。示意图如图所示:
利用前序和中序遍历的结果重建二叉树
Python代码:
# coding: utf-8 ''' 题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 ''' class Node: def __init__(self, data, left, right): self.data = data self.left = left self.right = right def construct_tree(pre_order, mid_order): # 忽略参数合法性判断 if len(pre_order) == 0 : return None # 前序遍历的第一个结点一定是根结点 root_data = pre_order[0] for i in range(0, len(mid_order)): if mid_order[i] == root_data: break # 递归构造左子树和右子树 left = construct_tree(pre_order[1 : 1 + i], mid_order[:i]) right = construct_tree(pre_order[1 + i:], mid_order[i+1:]) return Node(root_data, left, right) if __name__ == '__main__': pre_order = [1, 2, 4, 7, 3, 5, 6, 8] mid_order = [4, 7, 2, 1, 5, 3, 8, 6] root = construct_tree(pre_order, mid_order) print root.data print root.left.data print root.right.data print root.left.left.data print root.left.left.right.data print root.right.right.left print root.right.left.data
更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python Socket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》
希望本文所述对大家Python程序设计有所帮助。
相关推荐
-
python数据结构之二叉树的统计与转换实例
一.获取二叉树的深度 就是二叉树最后的层次,如下图: 实现代码: 复制代码 代码如下: def getheight(self): ''' 获取二叉树深度 ''' return self.__get_tree_height(self.root) def __get_tree_height(self, root): if root is 0: return 0 if root.left is 0 and root.righ
-
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中的二叉树模块内容: BinaryTree:非平衡二叉树 AVLTree:平衡的AVL树 RBTree:平衡的红黑树 以上是用python写的,相面的模块是用c写的,并且可以做为Cython的包. FastBinaryTree FastAVLTree FastRBTree 特别需要说明的是:树往往要比python内置的dict类慢一些,但是它中的所有数据都是按照某个关键词进行排序的,故在某些情况下是必须使用的. 安装和使用 安装方法 安装环境: ubuntu12.04, py
-
python数据结构之二叉树的遍历实例
遍历方案 从二叉树的递归定义可知,一棵非空的二叉树由根结点及左.右子树这三个基本部分组成.因此,在任一给定结点上,可以按某种次序执行三个操作: 1).访问结点本身(N) 2).遍历该结点的左子树(L) 3).遍历该结点的右子树(R) 有次序: NLR.LNR.LRN 遍历的命名 根据访问结点操作发生位置命名:NLR:前序遍历(PreorderTraversal亦称(先序遍历)) --访问结点的操作发生在遍历其左右子树之前.LNR:中序遍历(InorderTraversal)
-
Python算法之求n个节点不同二叉树个数
问题 创建一个二叉树 二叉树有限多个节点的集合,这个集合可能是: 空集 由一个根节点,和两棵互不相交的,分别称作左子树和右子树的二叉树组成 创建二叉树: 创建节点 再创建节点之间的关系 Python代码示例 # !/usr/bin/env python # -*-encoding: utf-8-*- # author:LiYanwei # version:0.1 class TreeNode(object): def __init__ (self, data, left = None, righ
-
Python利用前序和中序遍历结果重建二叉树的方法
本文实例讲述了Python利用前序和中序遍历结果重建二叉树的方法.分享给大家供大家参考,具体如下: 题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树.假设输入的前序遍历和中序遍历的结果中都不含重复的数字. 这道题比较容易,前序遍历的结果中,第一个结点一定是根结点,然后在中序遍历的结果中查找这个根结点,根结点左边的就是左子树,根结点右边的就是右子树,递归构造出左.右子树即可.示意图如图所示: 利用前序和中序遍历的结果重建二叉树 Python代码: # coding: utf-8 ''
-
C++基于先序、中序遍历结果重建二叉树的方法
本文实例讲述了C++基于先序.中序遍历结果重建二叉树的方法.分享给大家供大家参考,具体如下: 题目: 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树.假设输入的前序遍历和中序遍历的结果中都不含重复的数字.例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回. 实现代码: #include <iostream> #include <vector> #include <stack> using
-
通过先序遍历和中序遍历后的序列还原二叉树(实现方法)
当我们有一个 先序遍历序列:1,3,7,9,5,11 中序遍历序列:9,7,3,1,5,11 我们可以很轻松的用笔写出对应的二叉树.但是用代码又该如何实现? 下面我们来简单谈谈基本思想. 首先,先序遍历的顺序是根据 根-左孩子-右孩子 的顺序遍历的,那么我们可以率先确认的是先序遍历序列的第一个数就是根节点,然后中序遍历是根据 左孩子-根-右孩子 的顺序遍历的.我们通过先序遍历确认了根节点,那么我们只需要在中序遍历中找到根节点的位置,然后就可以很好地区分出,那些属于左子树的节点,那些是属于右子树的
-
C++实现LeetCode(105.由先序和中序遍历建立二叉树)
[LeetCode] 105. Construct Binary Tree from Preorder and Inorder Traversal 由先序和中序遍历建立二叉树 Given preorder and inorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree. For example, given preor
-
Python实现二叉树前序、中序、后序及层次遍历示例代码
前言 树是数据结构中非常重要的一种,主要的用途是用来提高查找效率,对于要重复查找的情况效果更佳,如二叉排序树.FP-树.另外可以用来提高编码效率,如哈弗曼树. 用 Python 实现树的构造和几种遍历算法.实现功能如下: 树的构造 递归实现先序遍历.中序遍历.后序遍历 堆栈实现先序遍历.中序遍历.后序遍历 队列实现层次遍历 # -*- coding=utf-8 -*- class Node(object): """节点类""" def __ini
-
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)的元素及两个互不相交的.分别被称为左子树和
-
PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解
本文实例讲述了PHP实现二叉树深度优先遍历(前序.中序.后序)和广度优先遍历(层次).分享给大家供大家参考,具体如下: 前言: 深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次.要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历.中序遍历.后序遍历.具体说明如下: 前序遍历:根节点->左子树->右子树 中序遍历:左子树->根节点->右子树 后序遍历:左子树->右子树->根节点 广度优先遍历:又叫层次遍历,从上往下对每一层依
-
Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作示例
本文实例讲述了Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作.分享给大家供大家参考,具体如下: 实现一个功能: 输入:一颗二叉树的先序和中序遍历 输出:后续遍历 思想: 先序遍历中,第一个元素是树根 在中序遍历中找到树根,左边的是左子树 右边的是右子树 Python代码: # -*- coding:utf-8 -*- def fromFMtoL( mid ): global las #全局后序遍历 global fir #先序遍历 root = fir[0] #取
-
C#使用前序遍历、中序遍历和后序遍历打印二叉树的方法
本文实例讲述了C#使用前序遍历.中序遍历和后序遍历打印二叉树的方法.分享给大家供大家参考.具体实现方法如下: public class BinaryTreeNode { public BinaryTreeNode Left { get; set; } public BinaryTreeNode Right { get; set; } public int Data { get; set; } public BinaryTreeNode(int data) { this.Data = data;
-
PHP根据树的前序遍历和中序遍历构造树并输出后序遍历的方法
本文实例讲述了PHP根据树的前序遍历和中序遍历构造树并输出后序遍历的方法.分享给大家供大家参考,具体如下: 先来看看前序遍历.中序遍历与后序遍历原理图: 根据树的前序遍历和中序遍历构造树并输出后序遍历代码如下: <?php class BinaryTreeNode{ public $m_value; public $m_left; public $m_right; } function ConstructCore($preorder,$inorder){ if(count($preorder)!
随机推荐
- Erlang中的基本元素操作小结
- oracle横向纵向求和代码实例
- 在jsp页面如何获得url参数
- Android实现从缓存中读取图片与异步加载功能类
- Linux下将数据库从MySQL迁移到MariaDB的基础操作教程
- Windows下Redis安装配置教程
- jquery.validate 自定义验证方法及validate相关参数
- 另一种希望别人无法修改js的代码
- js实现左侧网页tab滑动门效果代码
- PHP 实现多服务器共享 SESSION 数据
- Gentoo 下安装与配置Nginx+ MySQL + PHP (fastcgi) 环境步骤分享
- 在FireFox/IE下Response中文文件名乱码问题解决方案
- 2014最热门的JavaScript代码高亮插件推荐
- 关于C++类的成员初始化列表的相关问题
- dede3.1分页文字采集过滤规则详说(图文教程)
- 改变文件域的样式实现思路同时兼容ie、firefox
- 聊一聊JavaScript作用域和作用域链
- javascript里模拟sleep(两种实现方式)
- C#实现将像素转换为页面单位的方法
- Javascript中Eval函数的使用