数据结构编程实践20讲(Python版)—06二叉搜索树
本文目录
往期链接
| 01 数组 | 02 链表 | 03 栈 | 04 队列 | 05 二叉树 |
|---|
06 二叉搜索树（Binary Search Tree，BST）
S1 说明
二叉搜索树是一种特殊的二叉树，具有以下性质：
- 节点的值：每个节点的值大于其左子树中所有节点的值，并小于其右子树中所有节点的值。
- 递归性质：左右子树也是二叉搜索树。
二叉搜索树的主要操作：
插入：在树中插入新节点时，从根节点开始，按照 BST 的性质找到合适的位置。
查找：从根节点开始，比较目标值与当前节点的值，决定向左子树或右子树继续查找。
删除：有三种情况：
- 删除的节点是叶子节点。
- 删除的节点只有一个子节点。
- 删除的节点有两个子节点（需找到右子树的最小值或左子树的最大值替代）。
应用场景：
查找表：可以用作实现高效的查找表。
数据库索引：许多数据库使用 BST 或其变种（如 B 树）来实现索引。
自动排序：可以通过中序遍历得到一个有序序列。
动态集合：支持动态插入和删除的集合操作。
区间查询：可以快速查找某个值是否在特定范围内。
图形算法：在某些图形算法（如可视化或图形处理）中需要快速查找。
S2 示例
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, value):
if not self.root:
self.root = TreeNode(value)
else:
self._insert_recursive(self.root, value)
def _insert_recursive(self, node, value):
if value < node.value:
if node.left is None:
node.left = TreeNode(value)
else:
self._insert_recursive(node.left, value)
else:
if node.right is None:
node.right = TreeNode(value)
else:
self._insert_recursive(node.right, value)
def search(self, value):
return self._search_recursive(self.root, value)
def _search_recursive(self, node, value):
if node is None or node.value == value:
return node
if value < node.value:
return self._search_recursive(node.left, value)
return self._search_recursive(node.right, value)
# 示例使用
if __name__ == "__main__":
bst = BinarySearchTree()
numbers = [7, 3, 9, 1, 5, 8, 10]
for num in numbers:
bst.insert(num)
# 查找
print(bst.search(5)) # 输出节点对象
print(bst.search(6)) # 输出 None
S3 问题： 在线图书馆系统
利用二叉搜索树来实现动态查找和范围查询。构建有一个在线图书馆系统，用户可以通过书名快速查找书籍，并支持查找特定范围内的书籍价格。我们可以使用二叉搜索树来存储书籍信息（如书名和价格），以便高效地进行查找和范围查询。
Python3程序
class Book:
def __init__(self, title, price):
self.title = title
self.price = price
class TreeNode:
def __init__(self, book):
self.book = book
self.left = None
self.right = None
class BookBST:
def __init__(self):
self.root = None
def insert(self, book):
if not self.root:
self.root = TreeNode(book)
else:
self._insert_recursive(self.root, book)
def _insert_recursive(self, node, book):
if book.title < node.book.title:
if node.left is None:
node.left = TreeNode(book)
else:
self._insert_recursive(node.left, book)
else:
if node.right is None:
node.right = TreeNode(book)
else:
self._insert_recursive(node.right, book)
def search(self, title):
return self._search_recursive(self.root, title)
def _search_recursive(self, node, title):
if node is None or node.book.title == title:
return node
if title < node.book.title:
return self._search_recursive(node.left, title)
return self._search_recursive(node.right, title)
def range_query(self, low, high):
result = []
self._range_query_recursive(self.root, low, high, result)
return result
def _range_query_recursive(self, node, low, high, result):
if node:
if low < node.book.title:
self._range_query_recursive(node.left, low, high, result)
if low <= node.book.title <= high:
result.append(node.book)
if high > node.book.title:
self._range_query_recursive(node.right, low, high, result)
# 示例使用
if __name__ == "__main__":
library = BookBST()
library.insert(Book("Harry Potter", 20))
library.insert(Book("The Hobbit", 15))
library.insert(Book("1984", 10))
library.insert(Book("War and Peace", 25))
library.insert(Book("Pride and Prejudice", 18))
# 查找特定书籍
book = library.search("1984")
if book:
print(f"Found: {book.book.title}, Price: ${book.book.price}")
else:
print("Book not found.")
# 范围查询
print("Books in the price range 15 to 20:")
for b in library.range_query("15", "20"):
print(f"{b.title}: ${b.price}")
输出
Found: 1984, Price: $10
Books in the price range 15 to 20:
1984: $10
代码说明
- Book 类：表示书籍，包含书名和价格。
- TreeNode 类：表示二叉搜索树的节点，包含书籍信息和指向左右子节点的指针。
- BookBST 类：实现了二叉搜索树的功能，包括插入、查找和范围查询。
S4 问题： 学生成绩管理系统
Python3程序
class Student:
def __init__(self, name, score):
self.name = name
self.score = score
class TreeNode:
def __init__(self, student):
self.student = student
self.left = None
self.right = None
class StudentBST:
def __init__(self):
self.root = None
def insert(self, student):
if not self.root:
self.root = TreeNode(student)
else:
self._insert_recursive(self.root, student)
def _insert_recursive(self, node, student):
if student.score < node.student.score:
if node.left is None:
node.left = TreeNode(student)
else:
self._insert_recursive(node.left, student)
else:
if node.right is None:
node.right = TreeNode(student)
else:
self._insert_recursive(node.right, student)
def search(self, name):
return self._search_recursive(self.root, name)
def _search_recursive(self, node, name):
if node is None:
return None
if node.student.name == name:
return node
left_result = self._search_recursive(node.left, name)
if left_result:
return left_result
return self._search_recursive(node.right, name)
def range_query(self, low, high):
result = []
self._range_query_recursive(self.root, low, high, result)
return result
def _range_query_recursive(self, node, low, high, result):
if node:
if low < node.student.score:
self._range_query_recursive(node.left, low, high, result)
if low <= node.student.score <= high:
result.append(node.student)
if high > node.student.score:
self._range_query_recursive(node.right, low, high, result)
if __name__ == "__main__":
bst = StudentBST()
bst.insert(Student("张仪", 85))
bst.insert(Student("李耳", 70))
bst.insert(Student("王叁", 90))
bst.insert(Student("赵武", 60))
bst.insert(Student("刘流", 75))
student = bst.search("王叁")
if student:
print(f"找到: {student.student.name}, 分数: {student.student.score}")
else:
print("没找到学生")
print("分数在70到85之间的学生及成绩:")
for s in bst.range_query(70, 85):
print(f"{s.name}: {s.score}")
输出
找到: 王叁, 分数: 90
分数在70到85之间的学生及成绩:
李耳: 70
刘流: 75
张仪: 85
代码说明
Student 类：
代表一个学生，包含姓名（name）和分数（score）两个属性。
TreeNode 类：
表示二叉搜索树的一个节点，包含一个 Student 对象和指向左右子节点的引用。
StudentBST 类：
实现了二叉搜索树的主要功能，包括插入、搜索和范围查询。
主要方法：
- insert: 插入新的学生记录
- search: 根据姓名查找学生
- range_query: 查找特定分数范围内的学生
S5 问题： 单词频率统计系统
Python3程序
class WordFrequency:
def __init__(self, word, frequency):
self.word = word
self.frequency = frequency
class TreeNode:
def __init__(self, word_freq):
self.word_freq = word_freq
self.left = None
self.right = None
class WordFrequencyBST:
def __init__(self):
self.root = None
def insert(self, word):
if not self.root:
self.root = TreeNode(WordFrequency(word, 1))
else:
self._insert_recursive(self.root, word)
def _insert_recursive(self, node, word):
if word == node.word_freq.word:
node.word_freq.frequency += 1
elif word < node.word_freq.word:
if node.left is None:
node.left = TreeNode(WordFrequency(word, 1))
else:
self._insert_recursive(node.left, word)
else:
if node.right is None:
node.right = TreeNode(WordFrequency(word, 1))
else:
self._insert_recursive(node.right, word)
def search(self, word):
return self._search_recursive(self.root, word)
def _search_recursive(self, node, word):
if node is None or node.word_freq.word == word:
return node
if word < node.word_freq.word:
return self._search_recursive(node.left, word)
return self._search_recursive(node.right, word)
def inorder_traversal(self):
result = []
self._inorder_recursive(self.root, result)
return result
def _inorder_recursive(self, node, result):
if node:
self._inorder_recursive(node.left, result)
result.append(node.word_freq)
self._inorder_recursive(node.right, result)
# 使用示例
if __name__ == "__main__":
bst = WordFrequencyBST()
# 插入单词
text = "the quick brown fox jumps over the lazy dog"
for word in text.split():
bst.insert(word.lower())
# 查询特定单词的频率
word_to_search = "the"
result = bst.search(word_to_search)
if result:
print(f"'{word_to_search}' appears {result.word_freq.frequency} times.")
else:
print(f"'{word_to_search}' not found.")
# 打印所有单词及其频率
print("\nAll words and their frequencies:")
for word_freq in bst.inorder_traversal():
print(f"{word_freq.word}: {word_freq.frequency}")
输出
'the' appears 2 times.
All words and their frequencies:
brown: 1
dog: 1
fox: 1
jumps: 1
lazy: 1
over: 1
quick: 1
the: 2
代码说明
WordFrequency 类： 存储单词及其频率。
-TreeNode 类： 表示二叉搜索树的节点。
WordFrequencyBST 类： 实现了二叉搜索树的主要功能。
- insert 方法：插入新单词或增加已存在单词的频率。
- search 方法：查找特定单词的频率。
- inorder_traversal 方法：按字母顺序遍历所有单词及其频率。
原文地址：https://blog.csdn.net/qq_32882309/article/details/142759813
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！