Python构建一颗二分搜索树
程序员文章站
2023-12-29 11:31:40
...
二分搜索树特点:
- 二分搜索树的每个节点的值,大于其左子树的所有节点的值;小于其右子树的所有节点的值;
- 每一颗子树也是二分搜索树。
Python代码实现:
class Node:
'''定义节点'''
def __init__(self, val):
self.val = val # 当前值
self.left = None # 左孩子
self.right = None # 右孩子
class BST:
def __init__(self):
self.root = None # 根节点
self.count = 0 # 节点个数
def size(self):
'''返回节点个数'''
return self.count
def is_empty(self):
'''二分搜索树是否为空'''
return self.count == 0
def insert(self, item):
'''
调用_insert函数添加元素item,
返回新二分搜索树的根节点
'''
self.root = self._insert(self.root, item)
def is_contain(self, item):
'''查看该二分搜索树中是否包含某个元素'''
return self._contain(self.root, item)
def _insert(self, node, item):
'''递归实现添加元素'''
# 如果此节点为空,则将元素添加到此节点
if node is None:
self.count += 1
return Node(item)
# 传入的值若小于此节点值,则应放入该节点的左子树中
if item < node.val:
node.left = self._insert(node.left, item)
# 传入的值若大于此节点值,则应放入该节点的右子树中
elif item > node.val:
node.right = self._insert(node.right, item)
# 传入的值若等于此节点值,则不做事情
else:
pass
return node
def _contain(self, node, item):
'''递归查找是否包含某个元素'''
# 当前传入节点为空,未找到该元素
if node is None:
return False
# 等于当前节点值,找到了该元素
if item == node.val:
return True
# item小于当前节点值,则继续在左子树中查找
elif item < node.val:
return self._contain(node.left, item)
# item大于当前节点值,则继续在右子树中查找
else:
return self._contain(node.right, item)
def breadth_travel(self):
'''广度遍历'''
queue = [self.root]
while queue:
cur_node = queue.pop(0)
print(cur_node.val, end=' ')
if cur_node.left is not None:
queue.append(cur_node.left)
if cur_node.right is not None:
queue.append(cur_node.right)
def preorder(self, node):
'''前序遍历'''
if node is None:
return
print(node.val, end=' ')
self.preorder(node.left)
self.preorder(node.right)
def inorder(self, node):
'''中序遍历'''
if node is None:
return
self.inorder(node.left)
print(node.val, end=' ')
self.inorder(node.right)
def postorder(self, node):
'''后序遍历'''
if node is None:
return
self.postorder(node.left)
self.postorder(node.right)
print(node.val, end=' ')
if __name__ == '__main__':
import random
random.seed(666)
tree = BST()
for _ in range(10):
tree.insert(random.randint(10, 100))
# 中序遍历可将二分搜索树值从小到大排列
print('中序遍历: ', end='')
tree.inorder(tree.root)
print()
print('是否存在"80":', tree.is_contain(80))