树与二叉树基础：从现实到代码的桥梁

说实话，每次讲到树结构，我都会想起刚入行时的一个项目。那时候我还在做嵌入式文件系统，需要管理一堆目录和文件。用数组？太死板。用链表？查找太慢。后来我意识到，树结构才是正解。嗯，今天我们就来聊聊这个让无数程序员又爱又恨的数据结构。

树的定义与术语

树是什么？说白了，它是一种非线性的数据结构。你想想看，线性结构就像排队买奶茶，一个接一个。但树不一样，它有一个根，然后分叉出去，再分叉，像极了公司的组织架构。

我习惯把树拆成几个核心概念来理解：

• 根节点：整棵树的起点，没有父节点。就像你家户口本上的户主。
• 叶子节点：没有孩子的节点。说白了就是最底层的那些。
• 父节点与子节点：上下级关系。A是B的父节点，B就是A的子节点。
• 兄弟节点：同一个爹的孩子之间互称兄弟。
• 深度与高度：深度是从根往下数，高度是从叶子往上数。这两个概念我当年搞混过好几次。

树还有一个重要概念叫度。一个节点有几个孩子，它的度就是几。整棵树中最大的度，就是这棵树的度。比如二叉树，度就是2。

二叉树的定义与性质

二叉树是树家族里最常用的成员。为什么？因为简单、高效。每个节点最多两个分支，左子树和右子树。我做过的大部分项目，只要用到树结构，基本都是二叉树或其变种。

二叉树有几个重要性质，我建议你记牢：

1. 性质一：第i层最多有 2^(i-1) 个节点。比如第3层最多4个节点。
2. 性质二：深度为k的二叉树，最多有 2^k - 1 个节点。深度为3的树，最多7个节点。
3. 性质三：叶子节点数 = 度为2的节点数 + 1。这个性质在验证树结构时特别有用。

二叉树还有两种特殊形态：满二叉树和完全二叉树。满二叉树就是所有层都塞满了节点，完全二叉树则是除了最后一层，其他层都满，最后一层从左到右连续排列。为什么强调完全二叉树？因为它可以用数组来存，省空间！

二叉树的存储结构

存储二叉树，我常用的有两种方式：

1. 顺序存储（数组）

完全二叉树用数组存特别合适。根节点放下标1，左孩子是2i，右孩子是2i+1。但普通二叉树用数组存会浪费空间——有些位置空着也得占着。

// 顺序存储示例
#define MAX_SIZE 100
int tree[MAX_SIZE];  // 下标从1开始

// 访问节点
int left_child = 2 * parent_index;
int right_child = 2 * parent_index + 1;

2. 链式存储（指针）

这是我最常用的方式。每个节点包含数据域和两个指针域，左孩子和右孩子。灵活，不浪费空间。

// 链式存储结构
typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 创建节点
TreeNode* createNode(int data) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

遍历二叉树

遍历，说白了就是把树里的每个节点都走一遍。怎么走？有三种经典方式：

遍历方式	访问顺序	应用场景
前序遍历	根 → 左 → 右	复制树结构
中序遍历	左 → 根 → 右	二叉搜索树排序输出
后序遍历	左 → 右 → 根	删除树、计算表达式

这三种遍历，递归实现最直观。我刚开始学的时候，递归代码看得头晕。后来我画了个图，一步步走，才真正理解。

// 前序遍历
void preOrder(TreeNode* root) {
    if (root == NULL) return;
    printf("%d ", root->data);  // 先访问根
    preOrder(root->left);       // 再左子树
    preOrder(root->right);      // 最后右子树
}

// 中序遍历
void inOrder(TreeNode* root) {
    if (root == NULL) return;
    inOrder(root->left);        // 先左子树
    printf("%d ", root->data);  // 再访问根
    inOrder(root->right);       // 最后右子树
}

// 后序遍历
void postOrder(TreeNode* root) {
    if (root == NULL) return;
    postOrder(root->left);      // 先左子树
    postOrder(root->right);     // 再右子树
    printf("%d ", root->data);  // 最后访问根
}

你可能会问：为什么要学这三种遍历？我举个例子。有一次我需要计算一个表达式树的值，后序遍历就派上了用场——先算左右子树，再算根节点。而如果你要输出一个二叉搜索树的有序序列，中序遍历就是最佳选择。

知识体系总览

下面这张图是我自己整理的树与二叉树知识框架，你可以对照着复习：

树与二叉树这块，说白了就是递归思想加指针操作。你只要把这两个基本功练扎实了，后面的平衡二叉树、红黑树、B树什么的，学起来都会轻松很多。