Chinaunix首页 | 论坛 | 博客
  • 博客访问: 181887
  • 博文数量: 20
  • 博客积分: 1510
  • 博客等级: 上尉
  • 技术积分: 214
  • 用 户 组: 普通用户
  • 注册时间: 2006-10-11 23:54
个人简介

一个异想天开的coder

文章分类

全部博文(20)

文章存档

2014年(5)

2013年(4)

2012年(2)

2011年(1)

2008年(1)

2007年(6)

2006年(1)

分类: Python/Ruby

2014-07-14 01:10:18

这种题一般有二种形式,共同点是都已知中序序列。如果没有中序序列,是无法唯一确定一棵树的,证明略。
一、已知二叉树的前序序列和中序序列,求解树。
步骤:
1.定位树根节点:从前序列表可以知道第一个元素为树根
2.求树的左右子树:从中序列表以步骤1中的树根为中心,左边为左子树,右边为右子树
3.递归求解:分别以左右子树,重复步骤1,2,3,直到所有节点都定位完成。

二、已知二叉树的后序序列和中序序列,求解树。

步骤:
1.定位树根节点:从后序列表可以知道最后一个元素为树根
2.求树的左右子树:从中序列表以步骤1中的树根为中心,左边为左子树,右边为右子树
3.递归求解:分别以左右子树,重复步骤1,2,3,直到所以节点都定位完成。

以下为python的示例代码

  1. # -*- coding: utf-8 -*-

  2. class TreeNode:
  3.     def __init__(self, val, left=None, right=None):
  4.         self.value = val
  5.         self.left = left
  6.         self.right = right
  7.     
  8.     def prev_visit(self, result):
  9.         """鍓嶅簭閬嶅巻"""
  10.         result.append(self.value)
  11.         if self.left:
  12.             self.left.prev_visit(result)
  13.         if self.right:
  14.             self.right.prev_visit(result)

  15.     def midd_visit(self, result):
  16.         if self.left:
  17.             self.left.midd_visit(result)
  18.         result.append(self.value)
  19.         if self.right:
  20.             self.right.midd_visit(result)

  21.     def post_visit(self, result):
  22.         if self.left:
  23.             self.left.post_visit(result)
  24.         if self.right:
  25.             self.right.post_visit(result)
  26.         result.append(self.value)

  27.     def level(self):
  28.         left_level = 0
  29.         right_level = 0
  30.         if self.left:
  31.             left_level = self.left.level()
  32.         if self.right:
  33.             right_level = self.right.level()

  34.         return 1 + (left_level if left_level > right_level else right_level)

  35. def from_before_and_middle(before, middle):
  36.     if len(before) == 1:
  37.         return TreeNode(before[0])
  38.     val = before[0]
  39.     idx = middle.index(val)
  40.     left = None
  41.     right = None
  42.     left_middle = None
  43.     right_middle = None
  44.     if idx > 0:
  45.         left_middle = middle[0:idx]
  46.         left = from_before_and_middle([i for i in before if i in left_middle], left_middle)

  47.     if idx < (len(middle)-1):
  48.         right_middle = middle[idx+1:]
  49.         right = from_before_and_middle([i for i in before if i in right_middle], right_middle)

  50.     #print "before:", before
  51.     #print "middle:", middle
  52.     #print "root:", val, "left:", left_middle, "right:", right_middle
  53.     return TreeNode(val, left, right)

  54. def from_post_and_middle(post, middle):
  55.     if len(post) == 1:
  56.         return TreeNode(post[0])
  57.     val = post[-1]
  58.     idx = middle.index(val)
  59.     left = None
  60.     right = None
  61.     left_middle = None
  62.     right_middle = None
  63.     if idx > 0:
  64.         left_middle = middle[0:idx]
  65.         left = from_post_and_middle([i for i in post if i in left_middle], left_middle)

  66.     if idx < (len(middle)-1):
  67.         right_middle = middle[idx+1:]
  68.         right = from_post_and_middle([i for i in post if i in right_middle], right_middle)

  69.     #print "post:", post
  70.     #print "middle:", middle
  71.     #print "root:", val, "left:", left_middle, "right:", right_middle
  72.     return TreeNode(val, left, right)

  73. if __name__ == '__main__':
  74.     before = [1, 2, 4, 5, 7, 9, 10, 3, 6, 8]
  75.     middle = [4, 2, 9, 7, 10, 5, 1, 3, 8, 6]
  76.     tree = from_before_and_middle(before, middle)
  77.     post = []
  78.     tree.post_visit(post)
  79.     print post
  80.     print "level:", tree.level()
  81.     tree = from_post_and_middle(post, middle)
  82.     before_2 = []
  83.     tree.prev_visit(before_2)
  84.     if before_2 == before:
  85.         print "success"


阅读(1667) | 评论(0) | 转发(0) |
0

上一篇:centos6 安装配置icecast2

下一篇:没有了

给主人留下些什么吧!~~