<big>編譯環(huán)境：python v3.5.0, mac osx 10.11.4</big>
<big>前述內容：</big>

• 線性表
• 隊列
• 堆棧
• 線性結構相關算法

什么是樹（Tree）

客觀事物中許多事物存在層次關系馒疹，而這種分組層次管理機制有利于高效的查找稿械。如：

• 人類社會關系
• 圖書信息管理
• 社會組織結構

樹的定義

n（n>=0）個節(jié)點構成的有限集合

• 當n＝0時，稱為空樹客冈。
• 對于非空樹：
  • 樹根（root），一個特殊的節(jié)點，用 r表示
  • 其余節(jié)點可分為m（m>0)個互不相交的有限集T1,T2....,Tm,其中每個集合本身又是一棵樹壁榕，稱為原樹的子樹(SubTree)。
    

根據(jù)樹的定義如下事例就不是樹赎瞎，因為：

• 子樹是互不相交的牌里；
• 除了跟結點外，每個結點都有且只有一個父結點务甥；
• 一棵含有n個結點的樹二庵，具有n-1條邊

樹的基本術語

• 結點的度（Degree）：結點的子樹個數(shù)（如：A的度數(shù)為3）
• 樹的度：樹中所有結點最大的度數(shù)（如：上述樹的度為3）
• 葉（Leaf）結點：度為0的結點（如：上述樹的葉結點為：F,L,H,M,J,K）
• 路徑和路徑長度：從結點n到結點b的路徑為一個結點序列，其路徑長度為所包含邊的個數(shù)（如：A到F的路徑為A,B,F缓呛，路徑長度為2）
• 結點的層次（Level）：規(guī)定根結點在第一層催享，其他結點層次為其父結點層次加一。（如：A的層次為1哟绊，B的層次為2）
• 樹的深度（Depth）：樹中所有結點的最大層次因妙。（如：上述樹的深度為4）
• 森林（Forest）：是m（m>=0）互不相交樹的集合。對于每個結點而言票髓，其子樹的集合即為森林攀涵。由此倒谷，也可以森林和樹相互遞歸的定義來定義描述樹蔓罚。Tree＝（root怜校，F(xiàn)）走诞，其中root為根結點，F(xiàn)是m（m>=0）棵樹的森林窗宇。

樹的表示

對于一顆指定的樹（如下）疗绣，我們要怎樣在計算機中表示它的信息呢烙懦？

• 樹的結構體中包含：一個存放結點元素的單元拦盹，一個指向第一個兒子的指針和一個指向第一個兄弟的指針。

  
  
• 這樣一來薪鹦，我們表示一顆樹掌敬，則只需要2n個存儲單元來存儲樹的邊，僅僅浪費n+1個存儲單元池磁。
• 當我們把上述樹進行旋轉45度時奔害，發(fā)現(xiàn)這就是一顆二叉樹了，因此大部分的樹都可以轉化為二叉樹的形式進行表示地熄。綜上所述华临，樹的算法大多圍繞二叉樹進行。
  

二叉樹的表示

<big>二叉樹是一個有窮的結點集合端考，基本結構單元由一個包含結點元素雅潭、左孩子和右孩子指針的結構體組成。</big>

• 二叉樹有五種基本形態(tài)

  
  
• 二叉樹有左右順序之分却特，因此下述兩棵樹不為同一棵樹扶供。
  
• 特殊二叉樹：

• 斜二叉樹（skewed binary tree）：完全向一邊偏，形如單向鏈表裂明。

  
  
• 完美二叉樹（perfect binary tree）或滿二叉樹 （full binary tree）：沒有度為一的結點椿浓。（可用順式存儲方式進行存儲）
  
• 完全二叉樹（complete binary tree）：若對結點為n的完全二叉樹從上到下、從左到右進行編號i（1<=i<=n）闽晦，其編號與滿二叉樹中編號為i的結點在二叉樹中的位置相同扳碍。（可用順式存儲方式進行存儲）
  

二叉樹的重要性質

• 一顆二叉樹的第i層的最大結點數(shù)為2^(i-1)，i>=1仙蛉，不適合空樹笋敞。
• 深度為k的二叉樹擁有的最大結點樹為2^k-1，k>=1荠瘪，不適合空樹夯巷。
• 對于任何非空二叉樹T，若n0表示葉結點的個數(shù)哀墓，n2表示度為2結點的個數(shù)鞭莽，那么它們滿足關系n0=n2＋1。

1. 樹的邊數(shù)等于結點個數(shù)減一
2. 二叉樹只有度為零麸祷、一和二的結點澎怒，可以分別用n0，n1阶牍，n2表示喷面。
3. n0+n1＋n2則為樹結點個數(shù)，n11+n22**則為樹的邊樹
4. n0+n1＋n2－1=n11+n22走孽，即：n0=n2+1

二叉樹的抽象數(shù)據(jù)數(shù)據(jù)類型

• 先序遍歷

1. 先訪問其根結點（即輸出元素值）
2. 再遍歷其左子樹
3. 最遍歷其右子樹

• 中序遍歷

  
  

1. 先遍歷其左子樹
2. 再訪問其根結點（即輸出元素值）
3. 最后遍歷其右子樹

• 后序遍歷

  
  

1. 先遍歷其左子樹
2. 再遍歷其右子樹
3. 最后訪問其根結點（即輸出元素值）

• 層序遍歷

  
  

  按二叉樹的在滿二叉樹上對應編號的先后順序輸出惧辈。上述樹的層序遍歷輸出結果為：ABOCSMQWK

二叉樹的順序存儲結構（ tree.py）

• 根據(jù)完全二叉樹和滿二叉樹的性質，從上到下磕瓷、從左到右對結點進行編號盒齿，我們可以利用數(shù)組來存儲這兩種含有n個結點的特殊二叉樹念逞。
• 若我們對一般二叉樹也采取上述存儲方式，則會造成空間浪費边翁。
  
• 生成樹：
  tree =['A','B','O','C','S','M','Q','W','K']
• 是否為空樹
  def isEmptyTree(tree):
  return len(tree) == 0
• 遞歸算法的遍歷：
  • 先序遍歷
    def preOrderTraversal(tree,root): ＃ 遞歸算法
    if root <= len(tree):
    if tree[root-1]:
    print(tree[root-1]) # 輸出元素,訪問結點
    preOrderTraversal(tree,root=2root) # 遍歷左子樹
    preOrderTraversal(tree,root=2root+1) # 遍歷右子樹
  • 中序遍歷
    def inOrderTraversal(tree, root): # 中序遍歷
    if root <= len(tree):
    inOrderTraversal(tree, root=2 * root) # 遍歷左子樹
    if tree[root - 1]:
    print(tree[root - 1]) # 輸出元素,訪問結點
    inOrderTraversal(tree, root=2 * root + 1) # 遍歷右子樹
  • 后序遍歷
    def postOrderTraversal(tree, root): # 后序遍歷
    if root <= len(tree):
    postOrderTraversal(tree, root=2 * root) # 遍歷左子樹
    postOrderTraversal(tree, root=2 * root + 1) # 遍歷右子樹
    if tree[root - 1]:
    print(tree[root - 1]) # 輸出元素,訪問結點

• 非遞歸算法遍歷（利用堆棧）

  
  
• 先序遍歷（入棧的時候輸出）
  import stack_chain
  def preOrderTraversal(tree):
  store = stack_chain.stackChain() # 建立空棧
  node = 1 # 指向樹根
  while node <= len(tree) or not (stack_chain.isEmpty(store)): # 如果樹沒有到葉結點,或堆棧不為空
  while node <= len(tree): # 遍歷左子樹
  if tree[node-1]:
  print(tree[node-1]) # 訪問結點,并輸出結點
  stack_chain.push(store, [tree[node - 1], node]) # 將左子樹的元素壓入堆棧中
  node = 2
  if not (stack_chain.isEmpty(store)):
  element = stack_chain.pop(store)
  node = 2element[1] + 1 # 左子樹遍歷完后遍歷右子樹
• 中序遍歷（出棧的時候輸出）
  import stack_chain
  def preOrderTraversal(tree):
  store = stack_chain.stackChain() # 建立空棧
  node = 1 # 指向樹根
  while node <= len(tree) or not (stack_chain.isEmpty(store)): # 如果樹沒有到葉結點,或堆棧不為空
  while node <= len(tree): # 遍歷左子樹
  stack_chain.push(store, [tree[node - 1], node]) # 將左子樹的元素壓入堆棧中
  node = 2
  if not (stack_chain.isEmpty(store)): # 訪問結點,并輸出
  element = stack_chain.pop(store)
  if element[0]:
  print(element[0])
  node = 2element[1] + 1 # 左子樹遍歷完后遍歷右子樹
• 后序遍歷（第二次出棧的時候輸出）
  import stack_chain
  def preOrderTraversal(tree):
  store = stack_chain.stackChain() # 建立空棧
  node = 1 # 指向樹根
  while node <= len(tree) or not (stack_chain.isEmpty(store)): # 如果樹沒有到葉結點,或堆棧不為空
  while node <= len(tree): # 遍歷左子樹
  stack_chain.push(store, [tree[node - 1], node翎承，0]) # 將左子樹的元素壓入堆棧中，增加一個tag表示元素第幾次被彈出
  node = 2
  if not (stack_chain.isEmpty(store)): # 訪問結點,并輸出
  element = stack_chain.pop(store)
  if element[0] and element[2]>0: # 元素第二次被彈出時輸入符匾。
  print(element[0])
  if element[2] ＝＝0:
  element[2]=1 # 被彈出一次后改變tag
  stack_chain.push(store,element)
  node = 2element[1] + 1 # 左子樹遍歷完后遍歷右子樹
• 層序遍歷
  def levelOrderTraversal(tree):
  node = 0
  while node < len(tree):
  if tree[node]:
  print(tree[node])
  node += 1

二叉樹的鏈式存儲結構（tree_chain.py）

由包含結點元素叨咖、指向左孩子的指針和指向右孩子指針的結構體連接形成的鏈表結構。

• 創(chuàng)建二叉樹（可以根據(jù)先序和中序啊胶，或中序和后序甸各，根據(jù)先序和中序創(chuàng)建二叉樹示意圖如下）

  
  

• 先序的第一個為根結點

• 我們根據(jù)先序的根結點可以在中序遍歷中找到，從而得到根結點的兩個兒子結點的左右順序焰坪。

• 因此當我們確定一顆二叉樹時趣倾，中序遍歷的順序是必須的，因為只有它才能告訴我們兒子結點的左右順序某饰，而前和后序遍歷提供的都是根結點的信息誊酌。
  class BinaryTree(): # the basical structure of binary tree
  def init(self, element=None, left=None, right=None):
  self.element = element
  self.left = left
  self.right = right
  def createTree(preOrder, inOrder):
  if preOrder:
  p = BinaryTree() # create a tree node
  site = inOrder.index(preOrder[0]) # find root in inOrder sequence and then we can know that
  # which set is on the left and which set is on the right
  # attach left and right set to root, according to root site in inOder sequence
  p.element = preOrder[0]
  del preOrder[0]
  # recursive
  p.left = createTree(preOrder=preOrder[0:site],inOrder=inOrder[0:site])
  p.right = createTree(preOrder=preOrder[site:],inOrder=inOrder[site+1:])
  return p

• 判斷是否為空樹
  def isEmptyTree(root): ＃ hasn't either left child or right child
  return root.left is None and root.right is None

• 遞歸算法的遍歷：

  • 先序遍歷
    def preOrderTraversal(root): ＃ 遞歸算法
    if root:
    print(root.element) # 輸出元素,訪問結點
    preOrderTraversal(root.left) # 遍歷左子樹
    preOrderTraversal(root.right) # 遍歷右子樹
  • 中序遍歷
    def inOrderTraversal(tree, root): # 中序遍歷
    if root:
    inOrderTraversal(root.left) # 遍歷左子樹
    print(root.element) # 輸出元素,訪問結點
    inOrderTraversal(root.element) # 遍歷右子樹
  • 后序遍歷
    def postOrderTraversal(tree, root): # 后序遍歷
    if root:
    postOrderTraversal(root.left) # 遍歷左子樹
    postOrderTraversal(root.right) # 遍歷右子樹
    print(root.element) # 輸出元素,訪問結點

• 非遞歸算法遍歷（利用堆棧）
• 先序遍歷（入棧的時候輸出）
  import stack_chain
  def preOrderTraversal(tree):
  store = stack_chain.stackChain() # 建立空棧
  p = tree # 指向樹根
  while p or not (stack_chain.isEmpty(store)): # 如果樹沒有到葉結點,或堆棧不為空
  while p: # 遍歷左子樹
  print(p.element) # 訪問結點,并輸出結點
  stack_chain.push(store, p) # 將左子樹的元素壓入堆棧中
  p = p.left
  if not (stack_chain.isEmpty(store)):
  node = stack_chain.pop(store)
  p = node.right # 左子樹遍歷完后遍歷右子樹
• 中序遍歷（出棧的時候輸出）
  import stack_chain
  def preOrderTraversal(tree):
  store = stack_chain.stackChain() # 建立空棧
  p = tree # 指向樹根
  while p or not (stack_chain.isEmpty(store)): # 如果樹沒有到葉結點,或堆棧不為空
  while p: # 遍歷左子樹
  stack_chain.push(store, p) # 將左子樹的元素壓入堆棧中
  p = p.left
  if not (stack_chain.isEmpty(store)): # 訪問結點,并輸出
  node = stack_chain.pop(store
  print(node.element)
  p = node.right # 左子樹遍歷完后遍歷右子樹
• 后序遍歷（第二次出棧的時候輸出）
  import stack_chain
  def preOrderTraversal(tree):
  store = stack_chain.stackChain() # 建立空棧
  p = tree # 指向樹根
  count = stack_chain.stackChain() # 記錄結點彈出的次數(shù)
  while p or not (stack_chain.isEmpty(store)): # 如果樹沒有到葉結點,或堆棧不為空
  while p: # 遍歷左子樹
  stack_chain.push(store, p) # 將左子樹的元素壓入堆棧中
  stack_chain.push(count,1) # 增加一個tag表示元素第幾次被彈出
  p = p.left
  if not (stack_chain.isEmpty(store)): # 訪問結點,并輸出
  node = stack_chain.pop(store)
  tag = stack_chain.pop(count)
  if tag > 1: # 元素第二次被彈出時輸入。
  print(node.element)
  else:
  stack_chain.push(count,2) # 被彈出一次后改變tag
  stack_chain.push(store,node)
  p = node.right # 左子樹遍歷完后遍歷右子樹
• 層序遍歷
  def levelTraversal(tree):
  store = queue_chain.queueChain() # 用隊列來暫存數(shù)據(jù)
  queue_chain.inQue(store, tree) # 將根結點插入隊列中
  while not(queue_chain.isEmpty(store)): # 逐個彈出訪問
  node = queue_chain.outQue(store)
  print(node.element)
  if node.left:
  queue_chain.inQue(store, node.left)
  if node.right:
  queue_chain.inQue(store,node.right)

二叉樹的應用

• 利用后序遍歷求二叉樹的高度

  
  
  
  

  def getTreeHight(tree):
  if tree: # 逐個遍歷左邊的樹和右邊的樹,取高的最大值
  hl = getTreeHight(tree.left)
  hr = getTreeHight(tree.right)
  hight = max(hl,hr)
  return hight+1
  else:
  return 0

• 二元運算表達式樹及其遍歷

  
  

源代碼: JacobKam-GitHub

后續(xù)內容：

• 平衡二叉樹與二叉搜索樹
• 堆露乏、哈夫曼樹和集合
• 樹相關算法