python常用算法（5）——树，二叉树与AVL树（一）https://developer.aliyun.com/article/1542698
4.4 二叉搜索树的查询操作
从根节点开始查找，待查找的值是否与根节点的值相同，若相同则返回True；否则，判断待寻找的值是否比根节点的值小，若是则进入根节点左子树进行查找，否则进入右子树进行查找。该操作使用递归实现。
代码如下：
def query(self, node, val): if not node: return None if node.data < val: return self.query(node.rchild, val) elif node.data > val: return self.query(node.lchild, val) else: return node
4.5 二叉树的查询操作——找最大值（最小值）
查找最小值：从根节点开始，沿着左子树一直往下，直到找到最后一个左子树节点，按照定义可知，该节点一定是该二叉搜索树中的最小值节点。
程序代码如下：
def findMin(self, root): '''查找二叉搜索树中最小值点''' if root.left: return self.findMin(root.left) else: return root
查找最大值：从根节点开始，沿着右子树一直往下，知道找到最后一个右子树节点，按照定义可知，该节点一定是该二叉搜索树中的最大值节点。
程序代码如下：
def findMax(self, root): '''查找二叉搜索树中最大值点''' if root.right: return self.findMax(root.right) else: return root
4.6 二叉搜索树的删除操作
对二叉搜索树节点的删除操作分为以下三种情况
1，如果要删除的节点是叶子节点：直接删除
2，如果要删除的节点只有一个孩子：将此节点的父亲与孩子连接，然后删除该节点（注意：该待删节点可能只有左子树或者右子树）
3，如果要删除的节点有两个孩子：将其右子树的最小节点（该节点最多有一个右孩子）删除，并替换当前节点
代码如下：
# _*_coding:utf-8_*_ import random class BiTreeNode: def __init__(self, data): self.data = data self.lchild = None # 左孩子 self.rchild = None # 右孩子 self.parent = None class BST: def __init__(self, li=None): self.root = None if li: for val in li: self.insert_no_rec(val) def __remove_node_1(self, node): # 第一种情况：node是叶子节点 if not node.parent: self.root = None if node == node.parent.lchild: # node是他父亲的左孩子 node.parent.lchild = None node.parent = None # 可以不写 else: # node是他父亲的右孩子 node.parent.rchild = None def __remove_node_21(self, node): # 情况2.1:node只有一个孩子，且为左孩子 if not node.parent: # 根节点 self.root = node.lchild node.lchild.parent = None elif node == node.parent.lchild: # node是它父亲的左孩子 node.parent.lchild = node.lchild node.lchild.parent = node.parent else: # node 是它父亲的右孩子 node.parent.rchild = node.lchild node.lchild.parent = node.parent def __remove_node_22(self, node): # 情况2.2：node只有一个孩子，且为右孩子 if not node.parent: self.root = node.rchild elif node == node.parent.lchild: node.parent.lchild = node.rchild node.rchild.parent = node.parent else: node.parent.rchild = node.rchild node.rchild.parent = node.parent def delete(self, val): if self.root: # 不是空树 node = self.query_no_rec(val) if not node: # 不存在 return False if not node.lchild and not node.rchild: # 1，叶子节点 self.__remove_node_1(node) elif not node.rchild: # 2.1 只有一个左孩子 self.__remove_node_21(node) elif not node.lchild: # 2.2 只有一个右孩子 self.__remove_node_22(node) else: # 3,两个孩纸都有 min_node = node.rchild while min_node.lchild: # 有左孩子 min_node = min_node.lchild node.data = min_node.data # 删除min_node if min_node.rchild: self.__remove_node_22(min_node) else: self.__remove_node_1(min_node)
4.7 二叉搜索树的打印操作
实现二叉搜索树的前序遍历，中序遍历，后序遍历，并打印出来。其中中序遍历打印出来的数列是按照递增顺序排列。
程序的代码如下：
def printTree(self, root): # 打印二叉搜索树（中序打印，有序数列—） if root == None: return self.printTree(root.left) print(root.val, end=',') self.printTree(root.right)
4.8 二叉树的插入，查询，删除，打印完整代码
代码如下：
# _*_coding:utf-8_*_ import random class BiTreeNode: def __init__(self, data): self.data = data self.lchild = None # 左孩子 self.rchild = None # 右孩子 self.parent = None class BST: def __init__(self, li=None): self.root = None if li: for val in li: self.insert_no_rec(val) def insert(self, node, val): if not node: node = BiTreeNode(val) elif val < node.data: node.lchild = self.insert(node.lchild, val) node.lchild.parent = node elif val > node.data: node.rchild = self.insert(node.rchild, val) node.rchild.parent = node return node def insert_no_rec(self, val): p = self.root if not p: # 空树 self.root = BiTreeNode(val) return while True: if val < p.data: if p.lchild: p = p.lchild else: # 左孩子不存在 p.lchild = BiTreeNode(val) p.lchild.parent = p return elif val > p.data: if p.rchild: p = p.rchild else: p.rchild = BiTreeNode(val) p.rchild.parent = p return else: return def query(self, node, val): if not node: return None if node.data < val: return self.query(node.rchild, val) elif node.data > val: return self.query(node.lchild, val) else: return node def query_no_rec(self, val): p = self.root while p: if p.data < val: p = p.rchild elif p.data > val: p = p.lchild else: return p return None def pre_order(self, root): if root: print(root.data, end=',') self.pre_order(root.lchild) self.pre_order(root.rchild) def in_order(self, root): if root: self.in_order(root.lchild) print(root.data, end=',') self.in_order(root.rchild) def post_order(self, root): if root: self.post_order(root.lchild) self.post_order(root.rchild) print(root.data, end=',') def __remove_node_1(self, node): # 第一种情况：node是叶子节点 if not node.parent: self.root = None if node == node.parent.lchild: # node是他父亲的左孩子 node.parent.lchild = None node.parent = None # 可以不写 else: # node是他父亲的右孩子 node.parent.rchild = None def __remove_node_21(self, node): # 情况2.1:node只有一个孩子，且为左孩子 if not node.parent: # 根节点 self.root = node.lchild node.lchild.parent = None elif node == node.parent.lchild: # node是它父亲的左孩子 node.parent.lchild = node.lchild node.lchild.parent = node.parent else: # node 是它父亲的右孩子 node.parent.rchild = node.lchild node.lchild.parent = node.parent def __remove_node_22(self, node): # 情况2.2：node只有一个孩子，且为右孩子 if not node.parent: self.root = node.rchild elif node == node.parent.lchild: node.parent.lchild = node.rchild node.rchild.parent = node.parent else: node.parent.rchild = node.rchild node.rchild.parent = node.parent def delete(self, val): if self.root: # 不是空树 node = self.query_no_rec(val) if not node: # 不存在 return False if not node.lchild and not node.rchild: # 1，叶子节点 self.__remove_node_1(node) elif not node.rchild: # 2.1 只有一个左孩子 self.__remove_node_21(node) elif not node.lchild: # 2.2 只有一个右孩子 self.__remove_node_22(node) else: # 3,两个孩纸都有 min_node = node.rchild while min_node.lchild: # 有左孩子 min_node = min_node.lchild node.data = min_node.data # 删除min_node if min_node.rchild: self.__remove_node_22(min_node) else: self.__remove_node_1(min_node) def printTree(self, root): # 打印二叉搜索树（中序打印，有序数列—） if root == None: return self.printTree(root.left) print(root.val, end=',') self.printTree(root.right) # 删除 tree = BST([1, 4, 2, 5, 3, 8, 6, 9, 7]) tree.in_order(tree.root) print(" ") tree.delete(4) tree.delete(1) tree.delete(8) tree.in_order(tree.root) ''' # 插入操作 tree = BST([4,6,7,9,2,1,3,5,8]) tree.pre_order(tree.root) print(" ") tree.in_order(tree.root) print(" ") tree.post_order(tree.root) print(" ") ''' 4, 2, 1, 3, 6, 5, 7, 9, 8, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 3, 2, 5, 8, 9, 7, 6, 4, ''' # 查询操作 li = list(range(0, 500, 2)) random.shuffle(li) tree = BST(li) print(tree.query_no_rec(4).data) # 4 '''
4.9 二叉搜索树的效率
平均情况下，二叉搜索树进行搜索的时间复杂度为O(nlgn)
最坏情况下，二叉搜索树可能非常偏斜，如下图所示：
解决方案：
- 随机化传入
- AVL树
python常用算法（5）——树，二叉树与AVL树（三）https://developer.aliyun.com/article/1542700
