引言

在前面的文章中，我们已经系统学习了线性数据结构——链表、栈、队列。线性结构的特点是元素之间存在一对一的先后关系。然而，现实世界中的很多数据关系是一对多的：文件系统中的目录与子目录、公司的组织架构、网页的 DOM 结构……

树（Tree）正是用来描述这种层级关系的非线性数据结构。它是整个数据结构体系中最重要的篇章之一，也是后续学习堆、B 树、红黑树、图等高级结构的基础。

第一部分：树的基本概念

一、什么是树

树是由n（n ≥ 0）个节点组成的有限集合：

• 当 n = 0 时，称为空树

• 当 n > 0 时，有一个特殊的节点称为根节点（Root），其余节点可分为 m 个互不相交的有限集合，每个集合本身又是一棵树，称为根的子树（Subtree）

二、核心术语

度、深度、高度的对比：

三、树的表示方法

1. 双亲表示法（用数组存父节点下标）

#define MAX_NODES 100 typedef struct { char data; // 节点数据 int parent; // 父节点下标（根节点的 parent = -1） } PTNode; typedef struct { PTNode nodes[MAX_NODES]; int n; // 节点数量 } PTree;

2. 孩子表示法（每个节点带子节点链表）

typedef struct ChildNode { int child_index; // 子节点在数组中的下标 struct ChildNode* next; // 下一个兄弟 } ChildNode; typedef struct { char data; ChildNode* first_child; // 第一个子节点的链表头 } CTBox; typedef struct { CTBox nodes[MAX_NODES]; int n; } CTree;

3. 孩子兄弟表示法（最常用，二叉树的基础）

typedef struct CSNode { char data; struct CSNode* first_child; // 第一个孩子 struct CSNode* next_sibling; // 下一个兄弟 } CSNode;

第二部分：二叉树

一、二叉树的定义

二叉树是每个节点最多只有两个子节点的树，子节点分为左子节点和右子节点。

typedef struct BinTreeNode { int data; // 数据域 struct BinTreeNode* left; // 左子节点 struct BinTreeNode* right; // 右子节点 } BinTreeNode;

二、两种特殊的二叉树

1. 满二叉树（Full Binary Tree）

每一层的节点数都达到最大值。第 k 层有 2^(k-1) 个节点，总节点数为 2^h - 1（h 为层数）。

2. 完全二叉树（Complete Binary Tree）

叶子节点只出现在最底层和次底层，且最底层的叶子节点都连续集中在左边。

完全二叉树的重要特性：可以用数组高效存储。

三、二叉树的性质

性质3证明：

四、二叉树的遍历

遍历是二叉树最基础也是最重要的操作。共有四种遍历方式：

4.1 递归实现

#include <stdio.h> #include <stdlib.h> typedef struct TreeNode { int data; struct TreeNode* left; struct TreeNode* right; } TreeNode; // 前序遍历：根 → 左 → 右 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); }

4.2 层序遍历（BFS，需要队列）

#include <stdbool.h> #define MAX_QUEUE 100 typedef struct { TreeNode* data[MAX_QUEUE]; int front, rear; } Queue; void initQueue(Queue* q) { q->front = q->rear = 0; } bool isEmpty(Queue* q) { return q->front == q->rear; } void enqueue(Queue* q, TreeNode* node) { q->data[q->rear++] = node; } TreeNode* dequeue(Queue* q) { return q->data[q->front++]; } // 层序遍历 void levelorder(TreeNode* root) { if (root == NULL) return; Queue q; initQueue(&q); enqueue(&q, root); while (!isEmpty(&q)) { TreeNode* node = dequeue(&q); printf("%d ", node->data); if (node->left != NULL) enqueue(&q, node->left); if (node->right != NULL) enqueue(&q, node->right); } }

层序遍历过程图解：

4.3 非递归实现（需要栈）

// 非递归中序遍历 void inorder_iterative(TreeNode* root) { TreeNode* stack[100]; int top = -1; TreeNode* cur = root; while (cur != NULL || top != -1) { // 一直走到最左边 while (cur != NULL) { stack[++top] = cur; cur = cur->left; } // 弹出栈顶，访问它，然后转向右子树 cur = stack[top--]; printf("%d ", cur->data); cur = cur->right; } }