二叉树
Binary Tree
我们从 二叉树 (Binary Tree) 开始。下面的整理只针对 Binary Tree，不会涉及其他树。
📊 二叉树的常见操作与复杂度
| 操作 | 平均时间复杂度 | 最坏情况复杂度 | 说明 |
|---|---|---|---|
| 插入 (Insert) | O(log n) | O(n) | 如果树接近平衡，插入是 O(log n)，最坏情况下退化成链表 |
| 查找 (Search) | O(log n) | O(n) | 与插入相同 |
| 删除 (Delete) | O(log n) | O(n) | 删除后可能需要重组子树 |
| 遍历 (Traversal: 前序/中序/后序/层序) | O(n) | O(n) | 必须访问所有节点 |
| 求高度 (Height) | O(n) | O(n) | 必须访问所有节点 |
| 找最小/最大值 (Min/Max) | O(log n) | O(n) | 沿着一条路径查找 |
✅ 上表已经覆盖了 二叉树的核心操作及复杂度，这就是二叉树的主要内容。
🔧 常见使用场景
- 表达式解析（AST，语法树）
- 分层结构表示（组织架构、菜单树）
- 排序与查找的基础（二叉搜索树 BST 就是扩展）
- 游戏 AI 决策树
💻 Zig 基础代码示例：二叉树实现
下面演示一个简化的 二叉树：插入、查找、遍历。
const std = @import("std");
const Node = struct {
value: i32,
left: ?*Node,
right: ?*Node,
};
const BinaryTree = struct {
root: ?*Node,
pub fn init() BinaryTree {
return BinaryTree{ .root = null };
}
fn createNode(value: i32) *Node {
const allocator = std.heap.page_allocator;
var node = allocator.create(Node) catch unreachable;
node.* = Node{ .value = value, .left = null, .right = null };
return node;
}
pub fn insert(self: *BinaryTree, value: i32) void {
self.root = insertNode(self.root, value);
}
fn insertNode(node: ?*Node, value: i32) ?*Node {
if (node == null) {
return createNode(value);
}
if (value < node.?.value) {
node.?.left = insertNode(node.?.left, value);
} else {
node.?.right = insertNode(node.?.right, value);
}
return node;
}
pub fn search(self: *BinaryTree, value: i32) bool {
var current = self.root;
while (current != null) {
if (value == current.?.value) return true;
if (value < current.?.value)
current = current.?.left
else
current = current.?.right;
}
return false;
}
pub fn inorder(self: *BinaryTree) void {
inorderTraversal(self.root);
}
fn inorderTraversal(node: ?*Node) void {
if (node == null) return;
inorderTraversal(node.?.left);
std.debug.print("{} ", .{node.?.value});
inorderTraversal(node.?.right);
}
};
pub fn main() !void {
var tree = BinaryTree.init();
tree.insert(5);
tree.insert(3);
tree.insert(7);
tree.insert(1);
tree.insert(4);
std.debug.print("Inorder Traversal: ", .{});
tree.inorder();
std.debug.print("\n", .{});
std.debug.print("Search 4: {}\n", .{tree.search(4)});
std.debug.print("Search 10: {}\n", .{tree.search(10)});
}运行结果（可能类似）：
Inorder Traversal: 1 3 4 5 7
Search 4: true
Search 10: false要不要我接下来帮你整理 二叉树的变体（比如 Binary Search Tree, BST），还是你只想在“Binary Tree”这里先停？