数据结构（四）：树

树

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