算法--二叉搜索树的python实现
二叉查找树(Binary Search Tree),也称为二叉搜索树、有序二叉树或排序二叉树,是指一棵空树或者具有下列性质的二叉树:
- 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
- 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
- 任意节点的左、右子树也分别为二叉查找树;
- 没有键值相等的节点。
通常采取二叉链表作为二叉查找树的存储结构(使用队列存储)。
# encoding=utf-8 import queue class TreeNode(object): def __init__(self,val): self.value = val self.left = None self.right = None self.father = None # 定义二叉搜索树的各种功能方法 class BST(object): def __init__(self,nodeList): self.root = None for node in nodeList: self.bfs_insert(node) #self.bfs_insert(node)中的bfs_insert方法在后面实现。放在构造函数中的目的是将一个列表生成一个二叉搜索树列表。 #实现插入功能 #第一步:将根节点(self.root)设置成当前位置节点(cur),即从根节点开始遍历。根节点的父节点(father)初始设置为None。 def bfs_insert(self,node): father = None cur = self.root # 第二步:查找可以插入的位置 # 1. 当前位置节点(cur)的值与待插入节点(node)的值相等,返回-1(代表无法进行插入操作)。并将父节点(father)值修改为当前位置节点(cur),代表该节点已经遍历完成。 while cur != None: if cur.value == node.value: return -1 father = cur if node.value < cur.value: cur = cur.left else: cur = cur.right node.father = father if father == None: self.root = node elif node.value < father.value: father.left = node else: father.right = node def bfs(self): if self.root == None: return None retList = [] q = queue.Queue() q.put(self.root) while q.empty() is not True: node = q.get() retList.append(node.value) if node.left != None: q.put(node.left) if node.right != None: q.put(node.right) return retList def bfs_search(self,value): cur = self.root while cur != None: if cur.value == value: return cur elif cur.value < value: cur = cur.right else: cur = cur.left return None def bfs_delete(self,node): father = node.father if node.left == None: if father == None: self.root = node.right if node.right != None: node.right.father = None elif father.left == node: father.left = node.right if node.right != None: node.right.father = father else: father.right = node.right if node.right != None: node.right.father = father return ‘delete successfully‘ tmpNode = node.left while tmpNode.right != None: tmpNode = tmpNode.right tmpNode.right = node.right if node.right != None: node.right.father = tmpNode if father == None: self.root = node.left node.left.father = None elif father.left == node: father.left = node.left node.left.father = father else: father.right = node.left node.left.father = father node = None return ‘delete successfully‘ if __name__ == ‘__main__‘: varList = [24,34,5,4,8,23,45,35,28,6,29] nodeList = [TreeNode(var) for var in varList] bst = BST(nodeList) print (bst.bfs()) node = bst.bfs_search(34) bst.bfs_delete(node) print (bst.bfs()) node1 = TreeNode(1) bst.bfs_insert(node1) print (bst.bfs())