1.二叉树是一种遵守以下规则的树:
每个结点的子结点数量可为0，1，2
如果有两个子结点，则其中一个子结点的值必须小于父结点，另一个子结点的值必须大于父结点
2. 二叉树查找算法先从根结点开始
（1）检视该结点的值
（2）如果正是所要找的值，返回根结点
（3）如果要找的值小于当前结点的值，则再该结点的左子树查找
（4）如果要找的值大于当前结点的值，则在该结点的右子树查找
3.二叉树插入也是先从根结点开始
找到要插入的值应该被链接到哪个叶结点
要插入的值大于该叶结点的值，将该值插到该叶结点的右边
要插入的值小于该叶结点的值，将该值插到该叶结点的左边
4.二叉树的删除算法规则
（1）如果要删除的结点没有子结点，那就直接删除它就好了
（2）如果要删除的结点有一个子结点，那就删除它之后，还要将子结点填到被删除结点的位置上
（3）如果要删除的结点有两个子结点，则将该结点替换成其后继结点。一个结点的后继结点，就是所有比被删除结点大的子结点中，最小的一个
• 如果后继结点带有右子结点，则在后继结点填补被删除结点以后，用此有子结点替代后继结点的父结点的左子结点
1 # 树结点 2 class TreeNode: 3 def __init__(self, value, left=None, right=None): 4 self.value = value 5 self.leftChild = left 6 self.rightChild = right 7 8 # 查找(二叉树的查找算法先从根结点开始) 9 def tree_search(self, value, node): 10 # 基准情形: 如果node不存在或者node的值符合 11 if node is None or node.value == value: 12 return node 13 14 # 如果node存在但value小于当前结点的值,那就从左子结点出继续往下查找 15 elif value < node.value: 16 return self.tree_search(value, node.leftChild) 17 18 # 如果node存在但value大于当前结点的值,那就从右子结点出继续往下查找 19 elif value > node.value: 20 return self.tree_search(value, node.rightChild) 21 22 # 插入 23 def tree_insert(self, value, node): 24 # 如果node存在但value小于当前结点的值,那就从左子结点出继续往下查找 25 if value < node.value: 26 # 如果左子结点不存在,则将新值作为左子结点 27 if node.leftChild is None: 28 node.leftChild = TreeNode(value) 29 else: 30 self.tree_search(value, node.leftChild) 31 # 如果node存在但value大于当前结点的值,那就从右子结点出继续往下查找 32 elif value> node.value: 33 # 如果右子结点不存在,则将新值作为右子结点 34 if node.rightChild is None: 35 node.rightChild = TreeNode(value) 36 else: 37 self.tree_search(value, node.rightChild) 38 39 # 删除 40 def tree_delete(self, delete_value, node): 41 # 基准情形: 当前位置的上一层无子结点,说明已经到达书的底层 42 if node is None: 43 return None 44 45 # 如果要删除的值小于当前结点,则以左子树为参数,递归调用方法,然后将当前接待你的左链指向返回的结点 46 elif delete_value < node.value: 47 node.leftChild = self.tree_delete(delete_value, node.leftChild) 48 # 将当前结点(及其子树,如果存在的话)返回。将作为其父结点的新左子结点(或新右子结点) 49 return node 50 51 # 如果要删除的值大于当前结点,则以右子树为参数,递归调用方法,然后将当前接待你的右链指向返回的结点 52 elif delete_value > node.value: 53 node.rightChild = self.tree_delete(delete_value, node.rightChild) 54 # 将当前结点(及其子树,如果存在的话)返回。将作为其父结点的新右子结点(或新左子结点) 55 return node 56 57 # 如果要删除的值正是当前结点 58 elif delete_value == node.value: 59 # 如果当前结点没有左子结点,有右子结点,则以右子结点(及其子树,如果存在的话)替换当前删除结点成为当前删除结点之父结点的新子结点 60 # 如果当前结点没有左子结点,也没有右子结点,那就返回None 61 # 如果当前结点没有右子结点,有左子结点,则以左子结点(及其子树,如果存在的话)替换当前删除结点成为当前删除结点之父结点的新子结点 62 if node.leftChild is None: 63 return node.rightChild 64 elif node.rightChild is None: 65 return node.leftChild 66 67 # 剩下的情况只有 当前结点有左子结点和右子结点 68 # 如果当前结点有两个子结点,调用lift函数来作删除(它会使当前结点的值变为其后继结点的值) 69 else: 70 node.rightChild = self.tree_lift(node.rightChild, node) 71 72 return node 73 74 def tree_lift(self, node, delete_node): 75 # 如果此函数的当前结点有左子结点,则递归调用本函数,从左子树找出后继结点 76 if node.leftChild: 77 node.leftChild = self.tree_lift(node.leftChild, delete_node) 78 return node 79 # 如果此函数的当前结无左子结点,则代表当前结点是后继结点,于是将其值设置为被删除结点的新值 80 else: 81 delete_node.value = node.value 82 # 用后继结点的右子结点替代后继结点的父结点的左子结点 83 return node.rightChild 84 85 # 中序遍历 86 def in_order(self, node): 87 if not node: 88 return 89 self.in_order(node.leftChild) 90 print(node.value, end=',') 91 self.in_order(node.rightChild) 92 93 if __name__ == '__main__': 94 node4 = TreeNode(4) 95 node11 = TreeNode(11) 96 node30 = TreeNode(30) 97 node40 = TreeNode(40) 98 node52 = TreeNode(52) 99 node61 = TreeNode(61) 100 node82 = TreeNode(82) 101 node95 = TreeNode(95) 102 node10 = TreeNode(10, node4, node11) 103 node33 = TreeNode(33, node30, node40) 104 node56 = TreeNode(56, node52, node61) 105 node89 = TreeNode(89, node82, node95) 106 node25 = TreeNode(25, node10, node33) 107 node75 = TreeNode(75, node56, node89) 108 node50 = TreeNode(50, node25, node75) 109 110 # res_search = node50.tree_search(56, node50) 111 112 # print(res_search.value, res_search.leftChild, res_search.rightChild) 113 114 # node50.tree_insert(92, node50) 115 116 # node50.tree_delete(33, node50) 117 118 # 中序遍历 119 node50.in_order(node50) 120 121 """ 122 # 删除树结点过程 123 50 124 25 75 125 10 33 56 89 126 4 11 30 40 52 61 82 95 127 1.删除30 128 <1>tree_delete(30, node50): 129 elif 30 < node50: 130 node50.leftChild=<2>tree_delete(30, node25) 131 elif 30 > node25: 132 node25.rightChild=<3>tree_delete(30, node33) 133 elif 30 < node33.value: 134 node33.leftChild = <4>tree_delete(30, node30) 135 elif 30 = node30: 136 if node30.leftChild is None: 137 <4>return None 138 <3>return node33 139 <2>return node25 140 <1>return node50 141 142 50 143 25 75 144 10 33 56 89 145 4 11 40 52 61 82 95 146 2. 删除56 147 tree_delete(56, node50) 148 elif 56 > node50: 149 node50.rightChild = tree_delete(56, node75) 150 elif 56 < node75: 151 node75.leftChild = tree_delete(56, node56) 152 elif 56 = node56: 153 # node56 有两个子结点 154 else: 155 node56.rightChild=tree_lift(node61, node56) 156 return node56 157 return node75 158 return node50 159 160 tree_lift(node61, node56) 161 else: # node61无左子结点 162 node56.value = node61.value 163 return node61.rightChild # return None 164 50 165 25 75 166 10 33 61 89 167 4 11 40 52 82 95 168 169 3. 删除25 170 tree_delete(25, node50) 171 elif 25 < node50: 172 node50.leftChild = tree_delete(25, node25) 173 elif 25 = node25: 174 # node25 有两个子结点 175 else: 176 node25.rightChild = tree_lift(node33, node25） 177 return node25 178 return node50 179 180 tree_lift(node33, node25） 181 else: 182 node25.value = node33.value 183 return node40 184 50 185 25 75 186 10 33 61 89 187 4 11 40 52 82 95 188 189 4.删除50 190 tree_delete(50, node50) 191 elif 50 = node50: 192 # node50有两个子结点 193 else: 194 node50.rightChild = tree_lift(node75, node50) 195 return node50 196 197 tree_lift(node75, node50) 198 if node75.leftChild: 199 node75.leftChild = tree_delete(node61, node50) 200 if node61.leftChild: 201 node61.leftChild = tree_delete(node52, node50) 202 # 如果此函数的当前结无左子结点,则代表当前结点是后继结点,于是将其值设置为被删除结点的新值 203 else: 204 node50.value = node52.value 205 return node52.rightChild # None 206 return node61 207 return node75 208 209 """ 210 211 """ 212 # 中序遍历过程 213 in_order(node50) 214 in_order(node25) 215 in_order(node10) 216 in_order(node4) 217 print(node4.value) 1 218 return 219 print(node10.value) 2 220 in_order(node11) 221 print(node11.value) 3 222 return 223 print(node25.value) 4 224 in_order(node33) 225 in_order(node30) 226 print(node30.value) 5 227 return 228 print(node33.value) 6 229 in_order(node40) 230 print(node40.value) 7 231 return 232 print(node50.value) 8 233 in_order(node75) 234 in_order(node56) 235 in_order(node52) 236 print(node52.value) 9 237 return 238 print(node56.value) 10 239 in_order(node61) 240 print(node61.value) 11 241 return 242 print(node75.value) 12 243 in_order(node89) 244 in_order(node82) 245 print(node82.value) 13 246 return 247 print(node33.value) 14 248 in_order(node95) 249 print(node95.value) 15 250 return 251 """