二叉查找树(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())
来源: http://www.bubuko.com/infodetail-3518991.html