Binary Search Trees (BST) 二叉搜索树 (BST)

Master BST properties, traversals, and complexity analysis 掌握 BST 属性、遍历及复杂度分析

🎯 Take the Quiz (Members Only)做测验（会员专属）

🌳 BST Properties 🌳 BST 属性

A Binary Search Tree (BST) is a tree where for every node: 二叉搜索树 (BST) 是一种树，对于每个节点：

All values in the left subtree are less than the node's value.左子树中的所有值都小于节点的值。
All values in the right subtree are greater than the node's value.右子树中的所有值都大于节点的值。
Both subtrees must also be BSTs.左右子树也必须是 BST。

Complexity Summary 复杂度总结

Average Case:平均情况： O(log n) (Balanced tree)（平衡树）
Worst Case:最坏情况： O(h) or O(n) (Skewed tree/Degenerated into a list)（偏斜树/退化为链表）

🛠️ Lab 04 Tasks 🛠️ 实验 04 任务

TASK 1 bstNumLeaves — Count Leaf Nodes bstNumLeaves — 统计叶子节点

A leaf node is a node with no children (left == NULL && right == NULL).叶子节点是没有孩子的节点。

int bstNumLeaves(struct node *t) {
    if (t == NULL) return 0;
    if (t->left == NULL && t->right == NULL) return 1;
    return bstNumLeaves(t->left) + bstNumLeaves(t->right);
}

Complexity:复杂度： O(n) (visits every node)（访问每个节点）

TASK 2 bstRange — Range of Values bstRange — 数值范围

Range = Max Value - Min Value. Min is leftmost, Max is rightmost.范围 = 最大值 - 最小值。最小在最左，最大在最右。

int bstRange(struct node *t) {
    if (t == NULL) return -1;
    struct node *curr = t;
    while (curr->left != NULL) curr = curr->left;
    int min = curr->value;
    curr = t;
    while (curr->right != NULL) curr = curr->right;
    int max = curr->value;
    return max - min;
}

Complexity:复杂度： O(h) (visits one path)（访问一条路径）

TASK 4 bstClosest — Find Closest Value bstClosest — 寻找最接近的值

Search the tree like a normal search, but keep track of the value with the smallest absolute difference.像普通搜索一样搜索树，但记录绝对差最小的值。

int bstClosest(struct node *t, int val) {
    int closest = t->value;
    struct node *curr = t;
    while (curr != NULL) {
        if (abs(curr->value - val) < abs(closest - val)) closest = curr->value;
        if (val < curr->value) curr = curr->left;
        else if (val > curr->value) curr = curr->right;
        else return curr->value;
    }
    return closest;
}

Complexity:复杂度： O(h)

🚶 Traversals 🚶 遍历

TASK 5 Level-Order (BFS) 层序遍历 (BFS)

Visit nodes layer by layer using a Queue.使用队列一层一层访问节点。

1. Enqueue root 2. While queue not empty: a. Dequeue node x, PRINT x b. Enqueue x->left (if exists) c. Enqueue x->right (if exists)

TASK 6 Iterative Pre-Order (DFS) 迭代前序遍历 (DFS)

Order: Root -> Left -> Right. Use a Stack.顺序：根 -> 左 -> 右。使用栈。

⚠️ Stack Trick:栈技巧：

Push RIGHT child first, then LEFT child. This ensures the Left child is popped and processed first.先压入右孩子，再压入左孩子。这样能保证左孩子先被弹出和处理。