Python利用前序和中序遍歷結(jié)果重建二叉樹的方法

更新時間：2016年04月27日 10:00:02 作者：阿涵-_-

這篇文章主要介紹了Python利用前序和中序遍歷結(jié)果重建二叉樹的方法,實例分析了Python二叉樹的定義與遍歷操作技巧,需要的朋友可以參考下

本文實例講述了Python利用前序和中序遍歷結(jié)果重建二叉樹的方法。分享給大家供大家參考，具體如下：

題目：輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。

這道題比較容易，前序遍歷的結(jié)果中，第一個結(jié)點一定是根結(jié)點，然后在中序遍歷的結(jié)果中查找這個根結(jié)點，根結(jié)點左邊的就是左子樹，根結(jié)點右邊的就是右子樹，遞歸構(gòu)造出左、右子樹即可。示意圖如圖所示：

利用前序和中序遍歷的結(jié)果重建二叉樹

Python代碼：

# coding: utf-8
'''
題目：輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建出該二叉樹。
假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。
'''
class Node:
  def __init__(self, data, left, right):
    self.data = data
    self.left = left
    self.right = right
def construct_tree(pre_order, mid_order):
  # 忽略參數(shù)合法性判斷
  if len(pre_order) == 0 :
    return None
  # 前序遍歷的第一個結(jié)點一定是根結(jié)點
  root_data = pre_order[0]
  for i in range(0, len(mid_order)):
    if mid_order[i] == root_data:
      break
  # 遞歸構(gòu)造左子樹和右子樹
  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

更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python Socket編程技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》、《Python入門與進(jìn)階經(jīng)典教程》及《Python文件與目錄操作技巧匯總》

希望本文所述對大家Python程序設(shè)計有所幫助。

您可能感興趣的文章: