数据结构（二）：高级数据结构¶

树（Tree）¶

二叉树¶

每个节点最多有两个子节点。

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

二叉搜索树（BST）¶

左子树所有节点 < 根节点 < 右子树所有节点。

树的遍历¶

// 前序遍历：根 → 左 → 右
void preorder(struct TreeNode* root) {
    if (root == NULL) return;
    printf("%d ", root->val);
    preorder(root->left);
    preorder(root->right);
}

图（Graph）¶

存储方式¶

// 邻接矩阵
int graph[100][100] = {0};
graph[1][2] = 1;  // 1→2 有边

// 邻接表
struct Edge {
    int to, weight;
    struct Edge* next;
};

遍历¶

DFS：深度优先，递归/栈实现
BFS：广度优先，队列实现

哈希表（Hash Table）¶

通过哈希函数将键映射到存储位置。

int hash(int key) {
    return key % TABLE_SIZE;
}

时间复杂度：平均 O(1)
冲突处理：链地址法、开放地址法

实践建议¶

学习路径

先掌握数组和链表 → 学习栈和队列 → 理解树和图 → 最后学习哈希表。