Python利用前序和中序遍历结果重建二叉树的方法
作者：阿涵-_- 发布时间：2023-03-01 14:56:35
标签：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程序设计有所帮助。
0
投稿猜你喜欢
关于“登录”和“注册”的问题已经被很多设计师和交互设计上写过无数遍了，今天我在登录纳米盘网站时受到打击了所以写下此文。事情是这样的：当初租用- SQLSTATESQL SERVER 驱动程序错误描述 HY000所有绑定列都是只读的。必须是可升级的列，以使用 SQLSetPos 或 S
- 通过Python中的matplotlib绘制百分比堆叠柱状图，并为每一个类别设置不同的填充图案。主要原因是有些论文打印出是黑白色的，不同类别
- 在ASP中，也能让XML发挥其优点。例如像.NET那样写一个XML配置文件，在程序中读取，或者将一些数据量不大又经常访问的数据写入到XML中
- 数据库的选择原则是什么？我只知道小网站用Access，大网站用SQL，请问它的具体选择原则是什么？在实际应用中，数据库的选择原则一般是：如果
- Debian Etch Linux上成功安装了MySQL 5.0.27 icc版本，并使用JDBC测试中文成功!中文问题的关键是全部使用UT
- 这篇文章主要介绍了python isinstance函数用法详解,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值
- 一.基本的查询语句，特殊符号||。制定列的别名AS，唯一标示distinct1.字符连接符“||”与“+”符oracle：select &n
- Request.ServerVariables("Url") 返回服务器地址Request.ServerVariable
- 本文实例分析了javascript定义变量时带var与不带var的区别。分享给大家供大家参考。具体分析如下：直接看实例里说明：<scr
- 本文实例讲述了php实现的一段简单概率相关代码。分享给大家供大家参考，具体如下：<?phpfor($i=1;$i<100000;
- 代码如下： 代码如下:///<summary> /// 将两个列不同的DataTable合并成一个新的DataTab
- ASP使用xmlhttp获取远程网页内容，解决乱码问题方法一：<％function getHTTPPage(url)on error
- 本文实例为大家分享了JavaScript实现年历效果的具体代码，供大家参考，具体内容如下<!DOCTYPE html><h
- 很多年以前，面对上古时代遗留的 HTML 发出的腐臭，我捂住鼻子唉声叹气。刚练熟 web 标准的我，恨不得寝其尸食其肉，把一切推翻重来。但经
- 本文实例为大家分享了JavaScript实现淘宝网图片的局部放大的具体代码，供大家参考，具体内容如下要实现的效果如下：<!DOCTYP
- 程序一：负责从字典中随机提取数据，写入一个新文件。（1.php） <?php /* 从字典文件中提取随机值 */
- 一直希望自己对Web设计的色彩把握的更好些，所以手头上就备了一份图片版的配色表，对色彩的搭配有了很多的提高，今天发现了这套非常完整的Web版
- 新建图像文件后选Channels面板，新建Alpha1通道：输入文字； &nbs
- 本文实例讲述了PHP global全局变量的使用与注意事项。分享给大家供大家参考，具体如下：使用global在方法里面声明外部变量为全局变量
