Python树、二叉树、二叉搜索树（BST）

一、树（Tree）

基本概念

树是一种非线性数据结构，由节点和边组成，具有以下特点：

• 每个节点有零个或多个子节点

• 没有父节点的节点称为根节点

• 没有子节点的节点称为叶节点

• 每个非根节点有且只有一个父节点

树的术语

• 度(Degree): 节点的子树个数

• 深度(Depth): 根节点到该节点的路径长度

• 高度(Height): 节点到叶节点的最长路径

• 层次(Level): 根节点为第1层，依次递增

普通树的Python实现

class TreeNode:
"""树节点类"""
def __init__(self, data):
self.data = data # 节点数据
self.children = [] # 子节点列表

def add_child(self, child_node):
"""添加子节点"""
self.children.append(child_node)

def __str__(self, level=0):
"""可视化树结构"""
ret = " " * level + str(self.data) + "\\n" #先写好根节点数据
for child in self.children:
ret += child.__str__(level + 1)
return ret

# 创建树
root = TreeNode("公司")
sales = TreeNode("销售部")
sales.add_child(TreeNode("销售一组"))
sales.add_child(TreeNode("销售二组"))

tech = TreeNode("技术部")
tech.add_child(TreeNode("开发组"))
tech.add_child(TreeNode("测试组"))

root.add_child(sales)
root.add_child(tech)

print(root)
# 输出:
# 公司
# 销售部
# 销售一组
# 销售二组
# 技术部
# 开发组
# 测试组

二、二叉树（Binary Tree）

基本概念

二叉树是每个节点最多有两个子节点的树结构，称为：

• 左子节点

• 右子节点

二叉树的性质

 Python实现二叉树

class BinaryTreeNode:
"""二叉树节点类"""

def __init__(self, value):
self.value = value # 节点值
self.left = None # 左子节点
self.right = None # 右子节点

def __str__(self):
"""返回横躺字符画字符串"""
lines = []
self._build_lines(self, "", True, lines)
return "\\n".join(lines)

# 内部递归，把每一行 append 到 lines 列表
def _build_lines(self, node, prefix, is_left, lines):
if node is None:
return
self._build_lines(node.right,
prefix + ("│ " if is_left else " "), False, lines)
connector = "└── " if is_left else "┌── "
if prefix == "":
connector = ""
lines.append(prefix + connector + str(node.value))
self._build_lines(node.left,
prefix + (" " if is_left else "│ "), True, lines)

# 创建二叉树
root = BinaryTreeNode(1)
root.left = BinaryTreeNode(2)
root.right = BinaryTreeNode(3)
root.left.left = BinaryTreeNode(4)
root.left.right = BinaryTreeNode(5)

print(root)
# 输出:
# │ ┌── 3
# 1
# │ ┌── 5
# └── 2
# └── 4

二叉树遍历方式

• 前序遍历(Pre-order): 根 -> 左 -> 右
• 中序遍历(In-order): 左 -> 根 -> 右
• 后序遍历(Post-order): 左 -> 右 -> 根
• 层序遍历(Level-order): 按层次从上到下、从左到右

def preorder_traversal(node):
"""前序遍历"""
if node:
print(node.value, end=" ")
preorder_traversal(node.left)
preorder_traversal(node.right)

def inorder_traversal(node):
"""中序遍历"""
if node:
inorder_traversal(node.left)
print(node.value, end=" ")
inorder_traversal(node.right)

def postorder_traversal(node):
"""后序遍历"""
if node:
postorder_traversal(node.left)
postorder_traversal(node.right)
print(node.value, end=" ")

def levelorder_traversal(node):
"""层序遍历"""
if not node:
return
queue = [node]
while queue:
current = queue.pop(0)
print(current.value, end=" ")
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)

# 测试遍历
print("\\n前序遍历:", end=" ")
preorder_traversal(root) # 输出: 1 2 4 5 3

print("\\n中序遍历:", end=" ")
inorder_traversal(root) # 输出: 4 2 5 1 3

print("\\n后序遍历:", end=" ")
postorder_traversal(root) # 输出: 4 5 2 3 1

print("\\n层序遍历:", end=" ")
levelorder_traversal(root) # 输出: 1 2 3 4 5

三、二叉搜索树（BST-Binary Search Tree）

二叉搜索树是一种特殊的二叉树，满足：

• 左子树所有节点的值 < 根节点的值
• 右子树所有节点的值 > 根节点的值
• 左右子树也分别是BST

BST的性质

• 中序遍历BST会得到一个升序序列
• 查找、插入、删除的平均时间复杂度为O(log n)，最坏O(n)（退化为链表时）

Python实现BST

class BSTNode:
"""二叉搜索树节点类"""

def __init__(self, key):
self.key = key # 节点键值
self.left = None # 左子节点
self.right = None # 右子节点
self.parent = None # 父节点（可选）

def __str__(self):
"""可视化BST结构"""
return f"{self.key}(L:{self.left}, R:{self.right})"

class BinarySearchTree:
"""二叉搜索树类"""

def __init__(self):
self.root = None

def insert(self, key):
"""插入节点"""
if self.root is None:
self.root = BSTNode(key)
else:
self._insert_recursive(self.root, key)

def _insert_recursive(self, node, key):
"""递归插入辅助函数"""
if key < node.key:
if node.left is None:
node.left = BSTNode(key)
node.left.parent = node
else:
self._insert_recursive(node.left, key)
elif key > node.key:
if node.right is None:
node.right = BSTNode(key)
node.right.parent = node
else:
self._insert_recursive(node.right, key)
# 如果key == node.key，可以选择忽略或处理重复值
elif key == node.key:
# 策略 1：直接忽略（最简单）
return

# 策略 2：计数法（给节点加一个 count 属性）
# node.count += 1

def search(self, key):
"""查找节点"""
return self._search_recursive(self.root, key)

def _search_recursive(self, node, key):
"""递归查找辅助函数"""
if node is None or node.key == key:
return node
if key < node.key:
return self._search_recursive(node.left, key)
return self._search_recursive(node.right, key)

def delete(self, key):
"""删除节点"""
self.root = self._delete_recursive(self.root, key)

def _delete_recursive(self, node, key):
"""递归删除辅助函数"""
if node is None:
return node

if key < node.key:
node.left = self._delete_recursive(node.left, key)
elif key > node.key:
node.right = self._delete_recursive(node.right, key)
else:
# 找到要删除的节点
if node.left is None: #囊括了左右子树均为空的情况。
return node.right
elif node.right is None:
return node.left
else:
# 有两个子节点，找到右子树的最小节点替代，因为右子树的最小值一定比左子树大，但又比右子树小
successor = self._find_min(node.right)
node.key = successor.key
node.right = self._delete_recursive(node.right, successor.key)
return node

def _find_min(self, node):
"""找到子树中的最小节点"""
current = node
while current.left is not None:
current = current.left
return current

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.key)
self._inorder_recursive(node.right, result)

# 测试BST
bst = BinarySearchTree()
keys = [50, 30, 70, 20, 40, 60, 80]

for key in keys:
bst.insert(key)

print("中序遍历:", bst.inorder_traversal()) # 输出: [20, 30, 40, 50, 60, 70, 80]

# 查找测试
print("查找40:", bst.search(40) is not None) # 输出: True
print("查找45:", bst.search(45) is not None) # 输出: False

# 删除测试
bst.delete(30)
print("删除30后中序遍历:", bst.inorder_traversal()) # 输出: [20, 40, 50, 60, 70, 80]