树
概念：树是一些节点的集合，一棵树由称作根（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()
