数据结构编程实践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 = valueself.left = Noneself.right = Noneclass BinarySearchTree:def __init__(self):self.root = Nonedef 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 nodeif 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 = titleself.price = priceclass TreeNode:def __init__(self, book):self.book = bookself.left = Noneself.right = Noneclass BookBST:def __init__(self):self.root = Nonedef 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 nodeif 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 resultdef _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 = nameself.score = scoreclass TreeNode:def __init__(self, student):self.student = studentself.left = Noneself.right = Noneclass StudentBST:def __init__(self):self.root = Nonedef 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 Noneif node.student.name == name:return nodeleft_result = self._search_recursive(node.left, name)if left_result:return left_resultreturn self._search_recursive(node.right, name)def range_query(self, low, high):result = []self._range_query_recursive(self.root, low, high, result)return resultdef _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 = wordself.frequency = frequencyclass TreeNode:def __init__(self, word_freq):self.word_freq = word_freqself.left = Noneself.right = Noneclass WordFrequencyBST:def __init__(self):self.root = Nonedef 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 += 1elif 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 nodeif 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 resultdef _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 方法：按字母顺序遍历所有单词及其频率。