树 | Trees
定义 | Definition
树是一种层级数据结构，由节点和边组成。树中的节点按照层次关系排列，每个节点可以有多个子节点，但只能有一个父节点。
A tree is a hierarchical data structure composed of nodes and edges. Nodes in a tree are arranged in a hierarchical order, where each node can have multiple children but only one parent.
树的性质 | Properties of Trees
-
根节点 | Root Node: 树的顶层节点称为根节点，没有父节点。
-
叶节点 | Leaf Node: 没有子节点的节点称为叶节点。
-
内节点 | Internal Node: 具有至少一个子节点的节点称为内节点。
-
高度 | Height: 从根节点到叶节点的最长路径的边数称为树的高度。
-
深度 | Depth: 从根节点到某个节点的边数称为该节点的深度。
-
度 | Degree: 一个节点的子节点数量称为该节点的度。
-
Root Node: The top node of a tree, having no parent node.
-
Leaf Node: A node with no children.
-
Internal Node: A node that has at least one child.
-
Height: The number of edges on the longest path from the root node to a leaf node.
-
Depth: The number of edges from the root node to a particular node.
-
Degree: The number of children a node has.
树的类型 | Types of Trees
二叉树 | Binary Tree
每个节点最多有两个子节点的树，称为二叉树。
A tree in which each node has at most two children is called a binary tree.
特殊类型的二叉树 | Special Types of Binary Trees
-
满二叉树 | Full Binary Tree: 每个节点要么有两个子节点，要么没有子节点。
-
完全二叉树 | Complete Binary Tree: 除了最后一层，所有层的节点都是满的，并且最后一层的所有节点尽可能地靠左。
-
完美二叉树 | Perfect Binary Tree: 所有内节点都有两个子节点，并且所有叶节点都在同一层。
-
Full Binary Tree: Every node has either two or no children.
-
Complete Binary Tree: All levels are fully filled except possibly for the last level, which is filled from left to right.
-
Perfect Binary Tree: All internal nodes have two children, and all leaf nodes are at the same level.
二叉搜索树 | Binary Search Tree (BST)
二叉搜索树是一种特殊的二叉树，其中每个节点的左子节点的值小于该节点的值，右子节点的值大于该节点的值。
A binary search tree is a special type of binary tree where the value of the left child is less than the parent node, and the value of the right child is greater than the parent node.
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(root, key):
if root is None:
return TreeNode(key)
if key < root.value:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
return root
def search(root, key):
if root is None or root.value == key:
return root
if key < root.value:
return search(root.left, key)
return search(root.right, key)平衡二叉树 | Balanced Binary Tree
平衡二叉树是指任意节点的左右子树的高度差不超过 1 的二叉树。常见的平衡二叉树包括 AVL 树和红黑树。
A balanced binary tree is one where the height difference between the left and right subtrees of any node is no more than 1. Common balanced binary trees include AVL trees and Red-Black trees.
AVL 树 | AVL Tree
AVL 树是一种自平衡二叉搜索树，每个节点的左右子树高度差最多为 1。
An AVL tree is a self-balancing binary search tree where the height difference between the left and right subtrees of any node is at most 1.
class AVLTreeNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
def insert(node, key):
if not node:
return AVLTreeNode(key)
if key < node.key:
node.left = insert(node.left, key)
else:
node.right = insert(node.right, key)
node.height = 1 + max(get_height(node.left), get_height(node.right))
balance = get_balance(node)
if balance > 1 and key < node.left.key:
return right_rotate(node)
if balance < -1 and key > node.right.key:
return left_rotate(node)
if balance > 1 and key > node.left.key:
node.left = left_rotate(node.left)
return right_rotate(node)
if balance < -1 and key < node.right.key:
node.right = right_rotate(node.right)
return left_rotate(node)
return node
def left_rotate(z):
y = z.right
T2 = y.left
y.left = z
z.right = T2
z.height = 1 + max(get_height(z.left), get_height(z.right))
y.height = 1 + max(get_height(y.left), get_height(y.right))
return y
def right_rotate(y):
x = y.left
T2 = x.right
x.right = y
y.left = T2
y.height = 1 + max(get_height(y.left), get_height(y.right))
x.height = 1 + max(get_height(x.left), get_height(x.right))
return x
def get_height(node):
if not node:
return 0
return node.height
def get_balance(node):
if not node:
return 0
return get_height(node.left) - get_height(node.right)红黑树 | Red-Black Tree
红黑树是一种自平衡二叉搜索树，满足以下特性：
- 每个节点要么是红色，要么是黑色。
- 根节点是黑色。
- 所有叶节点都是黑色（叶节点是空节点）。
- 如果一个节点是红色，则它的两个子节点都是黑色。
- 从任一节点到其每个叶子的所有路径都包含相同数量的黑色节点。
A Red-Black Tree is a self-balancing binary search tree with the following properties:
- Each node is either red or black.
- The root is black.
- All leaves (NIL nodes) are black.
- If a node is red, then both its children are black.
- Every path from a node to its descendant NIL nodes has the same number of black nodes.
树的遍历 | Tree Traversal
前序遍历 | Pre-order Traversal
访问根节点 → 前序遍历左子树 → 前序遍历右子树
Visit the root node → Pre-order traverse the left subtree → Pre-order traverse the right subtree
def pre_order_traversal(root):
return [root.value] + pre_order_traversal(root.left) + pre_order_traversal(root.right) if root else []中序遍历 | In-order Traversal
中序遍历左子树 → 访问根节点 → 中序遍历右子树
In-order traverse the left subtree → Visit the root node → In-order traverse the right subtree
def in_order_traversal(root):
return in_order_traversal(root.left) + [root.value] + in_order_traversal(root.right) if root else []后序遍历 | Post-order Traversal
后序遍历左子树 → 后序遍历右子树 → 访问根节点
Post-order traverse the left subtree → Post-order traverse the right subtree → Visit the root node
def post_order_traversal(root):
return post_order_traversal(root.left) + post_order_traversal(root.right) + [root.value] if root else []层次遍历 | Level-order Traversal
按层次从上到下，从左到右依次访问各节点。
Visit nodes level by level from top to bottom, left to right.
from collections import deque
def level_order_traversal(root):
if not root:
return []
result, queue = [], deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
if node:
level.append(node.value)
queue.append(node.left)
queue.append(node.right)
result.append(level)
return result进阶知识 | Advanced Knowledge
Trie 树 | Trie
Trie 树是一种用于快速检索的树状数据结构，主要用于字符串的存储和检索。
A Trie, also known as a prefix tree, is a tree-like data structure used for efficient retrieval of keys, mainly strings.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word并查集 | Disjoint Set
并查集是一种数据结构，用于处理一些不相交集合的合并及查询问题。
A Disjoint Set, also known as Union-Find, is a data structure used to manage a collection of disjoint sets and support union and find operations.
class DisjointSet:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
rootX = self.find(x)
rootY = self.find(y)
if rootX != rootY:
if self.rank[rootX] > self.rank[rootY]:
self.parent[rootY] = rootX
elif self.rank[rootX] < self.rank[rootY]:
self.parent[rootX] = rootY
else:
self.parent[rootY] = rootX
self.rank[rootX] += 1常见问题 | Common Issues
-
递归深度限制 | Recursion Depth Limit: 在处理深度较大的树时，递归可能会导致栈溢出问题，需考虑使用迭代方式。
-
边界条件处理 | Handling Boundary Conditions: 在插入、删除和查找操作中，需特别注意处理空节点和叶节点的情况。
-
Recursion Depth Limit: When dealing with deep trees, recursion can lead to stack overflow issues, consider using iterative approaches.
-
Handling Boundary Conditions: Pay special attention to handling null nodes and leaf nodes during insertion, deletion, and search operations.