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


猜你喜欢
- CSS 中的 position 属性可以很容易的将指定的元素定位到理想的位置。但在使用这一属性时需要注意,尤其是在表格元素中。为了说明此问题
- 这篇文章主要介绍了Python socket模块ftp传输文件过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学
- 如下所示:import cv2import mathimport numpy as npdef move(img): height, wid
- 在python中,命令行解析的很好用,首先导入命令行解析模块import argparseimport sys然后创建对象parse=arg
- 1. 插入数据前判断数据是否存在SET ANSI_NULLS ON GO SET QUOTED_IDENTIFIER ON GO -- ==
- 背景最近在测试一款软件的关闭第三方窗口的功能,感觉实现应该挺简单的。所以就尝试了。由于说它的实现是靠c++实现的,本人对c++实在不在行,但
- 本文实例讲述了Python实现快速排序的方法。分享给大家供大家参考,具体如下:说起快排的Python实现,首先谈一下,快速排序的思路:1、取
- 本文研究的主要是python处理csv数据动态显示曲线,分享了实现代码,具体如下。代码:# -*- coding: utf-8 -*- &q
- 显示图像是 Opencv最基本的操作之一, imshow()函数可以实现该操作。如果使用过其他GUI框架背景,就会很自然地调用 imshow
- Golang 开发者遇到的许多问题之一是尝试将一个函数的参数设置为可选. 这是一个非常常见的用例, 有些对象应该使用一些基本的默认设置来开箱
- 关于端口扫描器端口扫描工具(Port Scanner)指用于探测服务器或主机开放端口情况的工具。常被计算机管理员用于确认安全策略,同时被攻击
- js中变量的特征js的变量是松散类型的。变量可以用于保存任何类型的数据。所以js也被称为弱类型语言。变量的定义与访问简单说下作用域什么是作用
- 由于连续的字符(字母、符号、数字)在默认情况下是不换行的,可能会破坏整个界面布局。那如何解决这个问题呢?在 IE 和 Safari 1.3+
- 删除一条留言信息会级联删除回复信息,这时我们需要用到事务,如下SQL 代码如下:ALTER PROCEDURE [dbo].[proc_tb
- 本文实例讲述了PHP实现对数组分页处理方法。分享给大家供大家参考,具体如下:最近用到了用数组数据分页,这里整理了一下,具体代码如下:<
- vue router路由嵌套不显示问题的解决方法,具体内容如下路由嵌套,vue2.0 router中嵌套路由不成功,如何解决?我先说下我的需
- 本文实例讲述了PHP实现按之字形顺序打印二叉树的方法。分享给大家供大家参考,具体如下:问题请实现一个函数按照之字形打印二叉树,即第一行按照从
- Tuple概述在Python中使用元组(Tuple)存储一组信息,其特征如下:1、使用()定义元组2、元组中使用逗号 , 分割各元素;各元素
- #-*- coding: utf-8 -*-import datetime#给定日期向后N天的日期def dateadd_day(days)
- 在开发django应用的过程中,使用开发者模式启动服务是特别方便的一件事,只需要 python manage.py runserver 就可