數據結構（四）：樹

樹

概念：樹是一些節點的集合，一棵樹由稱作根（root）的節點 r 以及0個或多個非空的（子）樹組成，這些子樹中每一棵的根都被來自根 r 的一條有向的邊（edge）連接。每一棵子樹的根叫做根 r 的兒子（child），r 是每一棵子樹的根的父親（parent）。一棵樹是N個 節點和N-1條邊的集合，其中一個節點叫做根。每條邊都將某個節點連接到它的父親，而除去根節點外每個節點都有一個父親。

特性：

• 沒有兒子的節點稱為樹葉（leaf）
• 具有相同父親的節點為兄弟（sibling）
• 在一棵樹中從根到每個節點恰好存在一條路徑，這條路徑上邊的條數稱為路徑的長
• 從根到任意節點 n 的唯一路徑的長稱為該節點 n 的深度（depth）
• 任意節點 n 到它的子樹中一片樹葉的最長路徑的長稱為節點 n 的高 
• 所有樹葉的高都是0，一棵樹的高等於它的根的高，也等於它的最深的樹葉的深度

樹的實現：實現一棵樹通常的思路是定義一個節點類，每個節點除數據外還要有指向該節點的每一個兒子的指針。但是，由於節點的兒子數變化很大並且事先不知道有多少個兒子，所以在節點類中不能直接定義指向兒子的指針。解決這個問題，可以把指向兒子的指針定義為一個鏈表，及節點類除數據外，還有一個用於存放該節點所有兒子的鏈表，即可構造一棵樹。

代碼：

 1 from collections import deque
 2 
 3 class TreeNode(object):
 4     def __init__(self, root, f_child=None):
 5         self.root = root
 6         self.depth = 0
 7         self.subtree = deque()
 8         self.f_child = f_child
 9         if self.f_child:
10             self.subtree.append(self.f_child)
11 
12     def insert(self, node):
13         node.depth = self.depth + 1
14         if self.f_child is None:
15             self.f_child = node
16         self.subtree.append(node)

樹的應用：樹的常見應用之一是UNIX等許多操作系統的目錄結構。系統的根目錄 / 即為樹的根節點，根目錄下的所有文件或子目錄都可以看作根結點的兒子，而子目錄下的文件或目錄又可以看作兒子節點的兒子，以此形成了操作系統的整棵目錄樹。

構造文件目錄並分級列印：

 1 """
 2 /
 3     usr
 4         local
 5         bin
 6     root
 7         download
 8             a.txt
 9             c.txt
10         documents
11     bin
12         config
13 """
14 # 構造上面的文件系統目錄並分級列印
15 Dir = TreeNode('/')
16 usr = TreeNode('usr')
17 root = TreeNode('root')
18 bin = TreeNode('bin')
19 download = TreeNode('download')
20 Dir.insert(usr)
21 Dir.insert(root)
22 Dir.insert(bin)
23 usr.insert(TreeNode('local'))
24 usr.insert(TreeNode('bin'))
25 root.insert(download)
26 root.insert(TreeNode('documents'))
27 bin.insert(TreeNode('config'))
28 download.insert(TreeNode('a.txt'))
29 download.insert(TreeNode('c.txt'))
30 
31 def printName(node):
32     for _ in range(node.depth):
33         print('\t', end='')
34     print(node.root)
35 
36 def ListDir(node):
37     printName(node)
38     for n in node.subtree:
39         ListDir(n)
40 
41 if __name__ == '__main__':
42     ListDir(Dir)

二叉樹

概念：每個節點最多有兩個兒子的樹，稱為二叉樹。

完滿二叉樹：如果二叉樹的所有節點中，除葉節點外都有兩個兒子，這樣的二叉樹稱為完滿二叉樹

完美二叉樹：如果完滿二叉樹的葉節點都在同一層，這樣的二叉樹稱為完美二叉樹

完全二叉樹：如果二叉樹從根節點到倒數第二層滿足完美二叉樹，最後一層的葉節點不完全填充，但靠左對齊，這樣的二叉樹稱為完全二叉樹

樹的遍歷：

• 先序遍歷：在遍歷樹節點的過程中，先處理根結點，再遞歸的處理子樹，這種遍歷方式稱為先序遍歷
• 後序遍歷：在遍歷樹節點的過程中，先遞歸的處理子子樹，再處理根結點，這種遍歷方式稱為後序遍歷
• 中序遍歷：對於二叉樹的遍歷，先遞歸的處理左子樹，再處理根結點，最後遞歸的處理右子樹，這種遍歷方式稱為中序遍歷

二叉查找樹：二叉樹的一個重要應用是其在查找中的使用。假設樹中的每個節點的值被用來存儲整數數據，且所有數據間不重覆（重覆的數據較複雜，以後討論）。為了是二叉樹具有便於查找的性質，通常規定每個節點的左子樹上的值都比它小，右子樹上的值都比它大。

實現：構造一棵二叉查找樹，通常要實現以下方法：

• make_empty：清空二叉樹
• find：查找某個節點
• find_min：查找值最小的節點
• find_max：查找值最大的節點
• insert：插入節點
• delete：刪除節點

插入節點的思路分析：二叉查找樹節點的插入是一個沿著樹的根節點遞歸向下查找插入位置的過程，即如果插入節點的值大於根結點，則從根結點的右兒子中查找；如果插入節點的值小於根結點，則從根結點的左兒子中查找。如果要插入的節點在樹中已存在，則什麼都不做，否則將節點插入到遍歷的路徑上的最後一個節點上。

刪除節點的思路分析：對於樹結構來說，刪除節點是最複雜的操作。要刪除某個樹節點，首先要對樹進行遍歷，找到目標節點。如果目標節點為葉節點（沒有孩子），則可直接刪除；如果目標節點有孩子，為了維持二叉查找樹的結構及特性不變，需要用目標節點的右子樹中的最小節點或左子樹中的最大節點來替換目標節點。

在實現這些操作的基礎上，如果想進一步維持一些節點的屬性，如節點的高度和深度，則插入和刪除操作複雜度又會增加，因為這兩個操作會改變一些樹節點高度、深度，每進行一次插入或刪除操作，就要重新計算、修正一次節點屬性，這往往使操作更加耗時。下麵分別分析：

• 插入操作：可能（因為樹節點的高度由左、右兩個兒子中高度較大的那個決定）會改變根結點到插入節點路徑上所有節點的高度；插入後要計算自身的高度和深度
• 刪除操作：可能會改變根結點到刪除節點路徑上所有節點的高度；如果刪除的節點不是葉節點，那麼從替換節點往下的整棵樹上的節點（如果有的話）的深度都減1

代碼實現：

  1 class TreeNode(object):
  2     def __init__(self, data, left=None, right=None):
  3         self.data, self.left, self.right = data, left, right
  4         self.depth = 0
  5         self.height = 0
  6 
  7 
  8 class SearchTree(object):
  9     def __init__(self, value):
 10         self.root = TreeNode(value)
 11         self.size = 1
 12         self.min = self.root
 13         self.max = self.root
 14 
 15     def _del_node(self, node):
 16         if node.right is not None:
 17             self._del_node(node.right)
 18         if node.left is not None:
 19             self._del_node(node.left)
 20         del node
 21 
 22     def make_empty(self):
 23         if self.root is not None:
 24             self._del_node(self.root)
 25         self.root = None
 26         self.size = 0
 27         self.min = None
 28         self.max = None
 29 
 30     def _height(self, node):
 31         if node is not None:
 32             return node.height
 33         else:
 34             return 0
 35 
 36     def _maxheight(self, left, right):
 37         if left is None:
 38             return self._height(right)
 39         if right is None:
 40             return self._height(left)
 41         return left.height if left.height > right.height else right.height
 42 
 43     def _add(self, node, root):
 44         if node.data > root.data:
 45             if root.right is None:
 46                 root.right = node
 47                 node.depth = root.depth + 1
 48             else:
 49                 self._add(node, root.right)
 50         if node.data < root.data:
 51             if root.left is None:
 52                 root.left = node
 53                 node.depth = root.depth + 1
 54             else:
 55                 self._add(node, root.left)
 56         root.height = self._maxheight(root.left, root.right) + 1
 57 
 58     def _search(self, value, node):
 59         if node is None:
 60             return None
 61         else:
 62             if value > node.data:
 63                 return self._search(value, node.right)
 64             if value < node.data:
 65                 return self._search(value, node.left)
 66             else:
 67                 return node
 68 
 69     def _search_parent(self, value, node):
 70         if value < node.data and node.left is not None:
 71             if value ==  node.left.data:
 72                 return node
 73             else:
 74                 return self._search_parent(value, node.left)
 75         if value > node.data and node.right is not None:
 76             if value == node.right.data:
 77                 return node
 78             else:
 79                 return self._search_parent(value, node.right)
 80         return None
 81 
 82     def insert(self, value):
 83         if self.size == 0:
 84             self.__init__(value)
 85         else:
 86             node = TreeNode(value)
 87             self._add(node, self.root)
 88             self.size += 1
 89             if value > self.max.data:
 90                 self.max = node
 91             if value < self.min.data:
 92                 self.min = node
 93 
 94     def _find_max(self, node):
 95         if node.right is None:
 96             return node
 97         else:
 98             return self._find_max(node.right)
 99 
100     def _find_min(self, node):
101         if node.left is None:
102             return node
103         else:
104             return self._find_min(node.left)
105 
106     def find(self, value):
107         return self._search(value, self.root)
108 
109     def find_max(self):
110         if self.size > 0:
111             return self._find_max(self.root)
112         return None
113 
114     def find_min(self):
115         if self.size > 0:
116             return self._find_min(self.root)
117         return None
118 
119     def _decrease_depth(self, node):
120         node.depth -= 1
121         if node.right is not None:
122             self._decrease_depth(node.right)
123         if node.left is not None:
124             self._decrease_depth(node.left)
125 
126     def _update_path_height(self, start_node, end_node):
127         if end_node.data > start_node.data:
128             self._update_path_height(start_node.right, end_node)
129             start_node.height = self._maxheight(start_node.left, start_node.right) + 1
130         if end_node.data < start_node.data:
131             self._update_path_height(start_node.left, end_node)
132             start_node.height = self._maxheight(start_node.left, start_node.right) + 1
133 
134     def delete(self, value):
135         # 情況一：節點不存在
136         # 情況二：節點存在且有孩子
137         # 情況三：節點存在，沒孩子
138         # 刪除節點的同時，保證樹上每個節點的高度和深度正確：
139         # 兩步走：1.頂替節點的所有子節點深度減1；
140         # 2.如果頂替節點的父節點的高度發生變化，則更新從根到父節點路徑上所有節點的高度
141         del_node = self._search(value, self.root)
142         if del_node is not None:
143             max_value = self.max.data
144             min_value = self.min.data
145             del_value = del_node.data
146             if del_node.right is not None:
147                 replace_node = self._find_min(del_node.right)
148                 replace_parent = self._search_parent(replace_node.data, del_node)
149                 del_node.data = replace_node.data  # 用替換節點覆蓋被刪除節點的值，相當於刪掉了目標節點
150                 if replace_node.right is not None: # 如果替換節點有孩子，更新所有孩子節點的深度
151                     self._decrease_depth(replace_node.right)
152                     # 將替換節點的孩子嫁接到父節點的樹上，此時替換節點已從原樹中摘除
153                     if replace_parent == del_node:
154                         replace_parent.right = replace_node.right # 替換節點是其父節點的右兒子
155                     else:
156                         replace_parent.left = replace_node.right  # 替換節點是其父節點的左兒子
157                 if replace_parent.height != self._maxheight(replace_parent.left, replace_parent.right) + 1:  # 如果替換節點的父節點高度發生了變化，更新從根到父節點路徑上所有節點的高度
158                     replace_parent.height = self._maxheight(replace_parent.left, replace_parent.right) + 1
159                     self._update_path_height(self.root, replace_parent)
160                 del replace_node
161             elif del_node.left is not None:
162                 replace_node = self._find_max(del_node.left)
163                 replace_parent = self._search_parent(replace_node.data, del_node)
164                 del_node.data = replace_node.data
165                 if replace_node.left is not None:
166                     self._decrease_depth(replace_node.left)
167                     if replace_parent == del_node:
168                         replace_parent.left = replace_node.left
169                     else:
170                         replace_parent.right = replace_node.left
171                 if replace_parent.height != self._maxheight(replace_parent.left, replace_parent.right) + 1:
172                     replace_parent.height = self._maxheight(replace_parent.left, replace_parent.right) + 1
173                     self._update_path_height(self.root, replace_parent)
174                 del replace_node
175             else:
176                 del_node.height = -1  # 目標節點沒有孩子，其父節點的高度必然-1，為了避免再次搜索其父，直接更新其自身路徑上所有節點的高度
177                 self._update_path_height(self.root, del_node)
178                 del del_node
179             self.size -= 1
180             if del_value == max_value:
181                 self.max = self.find_max()
182             if del_value == min_value:
183                 self.min = self.find_min()