# 中序遍历 def in_order_tree_walk(node): if node is not None: in_order_tree_walk(node.leftChild) print(node.value, end=" ") in_order_tree_walk(node.rightChild) def pre_order_tree_walk(node): if node: print(node.value, node.color) pre_order_tree_walk(node.leftChild) pre_order_tree_walk(node.rightChild) # 最小关键字元素 def tree_minimum(node): while node.leftChild: node = node.leftChild return node def tree_maximum(node): temp_node = node while temp_node.rightChild: temp_node = temp_node.rightChild return temp_node # 后继 def tree_successor(node): if node.rightChild: return tree_minimum(node.rightChild) # 如果指定结点的右子树为空 up_node = node.parent while up_node and node == up_node.rightChild: node = up_node up_node = up_node.parent return up_node # 前驱 def tree_predecessor(node): if node.leftChild: return tree_maximum(node.leftChild) up_node = node.parent while up_node and node == up_node.leftChild: node = up_node up_node = up_node.parent return up_node def transplant(tree, node_u, node_v): if not node_u.parent: tree.root = node_v elif node_u == node_u.parent.leftChild: node_u.parent.leftChild = node_v elif node_u == node_u.parent.rightChild: node_u.parent.rightChild = node_v if node_v: node_v.parent = node_u.parent class TreeNode: def __init__(self, value, left=None, right=None, parent=None): self.value = value self.parent = parent self.leftChild = left self.rightChild = right class Tree: def __init__(self, root=None): self.root = root # 二叉树查找 def tree_search(self, search_value, node): if node.value is None or search_value == node.value: return node if search_value < node.value: return self.tree_search(search_value, node.leftChild) else: return self.tree_search(search_value, node.rightChild) def tree_search_02(self, search_value, node): while node and search_value != node.value: if search_value < node.value: node = node.leftChild else: node = node.rightChild return node # 插入 def tree_insert(self, insert_node): parent_node = None r = self.root while r is not None: parent_node = r if insert_node.value < r.value: r = r.leftChild else: r = r.rightChild insert_node.parent = parent_node if parent_node is None: self.root = insert_node elif insert_node.value < parent_node.value: parent_node.leftChild = insert_node else: parent_node.rightChild = insert_node # 删除 def tree_delete(self, delete_node): if delete_node.leftChild is None: transplant(self, delete_node, delete_node.rightChild) elif delete_node.rightChild is None: transplant(self, delete_node, delete_node.leftChild) else: y = tree_minimum(delete_node.rightChild) if y.parent != delete_node: transplant(self, y, y.rightChild) y.rightChild = delete_node.rightChild y.rightChild.parent = y transplant(self, delete_node, y) y.leftChild = delete_node.leftChild y.leftChild.parent = y if __name__ == '__main__': # 构建二叉树++++++++++++++++上界+++++++++++++++++ node_4 = TreeNode(4) node_11 = TreeNode(11) node_30 = TreeNode(30) node_40 = TreeNode(40) node_52 = TreeNode(52) node_61 = TreeNode(61) node_82 = TreeNode(82) node_95 = TreeNode(95) node_10 = TreeNode(10, node_4, node_11) node_33 = TreeNode(33, node_30, node_40) node_56 = TreeNode(56, node_52, node_61) node_89 = TreeNode(89, node_82, node_95) node_25 = TreeNode(25, node_10, node_33) node_75 = TreeNode(75, node_56, node_89) node_50 = TreeNode(50, node_25, node_75) node_4.parent = node_10 node_11.parent = node_10 node_30.parent = node_33 node_40.parent = node_33 node_52.parent = node_56 node_61.parent = node_56 node_82.parent = node_89 node_95.parent = node_89 node_10.parent = node_25 node_33.parent = node_25 node_56.parent = node_75 node_89.parent = node_75 node_25.parent = node_50 node_75.parent = node_50 # 构建二叉树+++++++++++++++++下界+++++++++++++++++ T = Tree(node_50) in_order_tree_walk(node_50) print() search_res01 = T.tree_search(33, T.root) print(search_res01, search_res01.value) search_res02 = T.tree_search_02(33, T.root) print(search_res02, search_res02.value) mini = tree_minimum(node_50) print(mini, mini.value) maxi = tree_maximum(node_50) print(maxi, maxi.value) # successor = tree_successor(node_30) # print(successor, successor.value) # predecessor = tree_predecessor(node_30) # print(predecessor, predecessor.value) node_77 = TreeNode(77) T.tree_insert(node_77) in_order_tree_walk(node_50) print() T.tree_delete(node_56) T.tree_delete(node_77) in_order_tree_walk(node_50)