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程序设计有所帮助。
相关推荐
baike 2020-05-09
sunjunior 2020-04-08
mieleizhi0 2019-12-31
郭岚 2019-11-04
hanyujianke 2019-11-01
Sophiego 2019-05-18
Cypress 2019-07-01
jaminliu0 2019-06-29
YUAN 2019-06-28
Lenskit 2019-06-26
WindChaser 2019-06-21
xingweiyong 2015-04-07
算法魔功 2018-07-24
王少雷的黑马 2017-02-17
Wcplus 2018-05-07
zhglinux 2018-07-27
举 2017-10-12
wangxiaohua 2015-08-11
明立 2017-06-30
大数据分析BDA 2015-01-12
pythonpycharm 2016-05-24
大数据分析BDA 2014-08-02
tansuo 2014-07-30
Pythonandme 2019-03-06
pythoncream 2018-12-24
guyuanxiang 2014-04-29
PHP100 2019-03-28
PHP100 2019-03-28