数据结构第5章：树和二叉树完全指南（自整理详细图文笔记）

名人说：莫道桑榆晚，为霞尚满天。——刘禹锡（刘梦得，诗豪）
原创笔记：Code_流苏(CSDN)（一个喜欢古诗词和编程的Coder😊）
上一篇：《数据结构第4章 数组和广义表》

zero：思维导图

一、树的基本概念

1. 什么是树？

想象一下家族族谱或者公司的组织架构图，它们都是典型的树结构。在计算机中，树（Tree）是由结点（Node）和边（Edge）组成的层次型数据结构。

2. 树的基本术语

让我们通过一个直观的例子来理解这些术语：

• 根结点：树的顶端，没有父结点的结点（就像族谱中的祖先）
• 父结点（双亲结点）：上一层的结点
• 子结点（孩子结点）：下一层的结点
• 兄弟结点：同一个父结点的子结点
• 叶子结点：没有子结点的结点（度为0）
• 分支结点：有子结点的结点（度大于0）
• 树的高度/深度：从根到叶子的最长路径上的结点数
• 路径长度：路径上边的个数

3. 树的存储结构

顺序存储 - 双亲表示法

这种方法用数组存储，每个结点保存数据和父结点的下标：

typedef struct {char data;      // 结点数据int parent;     // 父结点下标，根结点为-1
} PTNode;typedef struct {PTNode nodes[MAXSIZE];int nodeCount;  // 结点数量
} PTree;

链式存储 - 孩子兄弟表示法

采用"左孩子右兄弟"的策略，每个结点包含：

• 数据域
• 指向第一个孩子的指针
• 指向右兄弟的指针

typedef struct TreeNode {char data;struct TreeNode* firstChild;  // 第一个孩子struct TreeNode* nextSibling; // 右兄弟
} TreeNode;

二、二叉树详解

1. 二叉树的定义与特点

二叉树（Binary Tree）是每个结点最多有两个子结点的树结构，具有以下特点：

• 每个结点的度不超过2（最多2个孩子）

• 子树有左右之分，顺序不能颠倒

• 即使只有一个子结点，也要明确是左孩子还是右孩子

  A.b为a的左子树

  
  B.c为a的右子树
  

2. 特殊的二叉树类型

满二叉树

高度为h，含有 2^h - 1 个结点的二叉树。特点是每一层都"满员"。

完全二叉树

除了最后一层，其他层都是满的，且最后一层的结点都靠左排列。

反例：

二叉排序树（BST）

满足"左 < 根 < 右"性质的二叉树，支持高效的查找操作。

平衡二叉树（AVL树）

任意结点的左右子树高度差不超过1的二叉排序树。

3. 二叉树的重要性质

• 性质1：叶结点数 = 度为2的结点数 + 1 即：$n_0=n_2+1$
• 性质2：第k层最多有 2^(k-1) 个结点
• 性质3：高度为h的二叉树最多有 2^h - 1 个结点
• 性质4：n个结点的完全二叉树高度为 ⌊log₂n⌋ + 1

4. 二叉树的存储结构

顺序存储

使用数组，下标之间有规律：

• 结点i的左孩子：2i
• 结点i的右孩子：2i + 1
• 结点i的父结点：⌊i/2⌋

a.完全二叉树的顺序存储

b.非完全二叉树（一般二叉树）的顺序存储

可以看出非完全二叉树会浪费很多存储单元，不适合进行顺序存储

链式存储（最常用）

typedef struct BiTNode {char data;                  // 数据域struct BiTNode* lchild;     // 左孩子指针struct BiTNode* rchild;     // 右孩子指针
} BiTNode, *BiTree;

5. 二叉树的遍历

二叉树遍历是指按照某种规则访问每个结点有且仅有一次。

先序遍历（根-左-右）

void PreOrder(BiTree T) {if (T) {visit(T);           // 访问根结点PreOrder(T->lchild); // 遍历左子树PreOrder(T->rchild); // 遍历右子树}
}

中序遍历（左-根-右）

void InOrder(BiTree T) {if (T) {InOrder(T->lchild);  // 遍历左子树visit(T);            // 访问根结点InOrder(T->rchild);  // 遍历右子树}
}

后序遍历（左-右-根）

void PostOrder(BiTree T) {if (T) {PostOrder(T->lchild); // 遍历左子树PostOrder(T->rchild); // 遍历右子树visit(T);             // 访问根结点}
}

层序遍历（使用队列）

void LevelOrder(BiTree T) {Queue Q;InitQueue(&Q);if (T) EnQueue(&Q, T);while (!IsEmpty(Q)) {DeQueue(&Q, &T);visit(T);if (T->lchild) EnQueue(&Q, T->lchild);if (T->rchild) EnQueue(&Q, T->rchild);}
}

6. 线索二叉树

线索二叉树是利用空闲指针域存储前驱和后继信息的特殊二叉树。

typedef struct ThreadNode {char data;struct ThreadNode* lchild, *rchild;int ltag, rtag;  // 0表示指向孩子，1表示指向线索
} ThreadNode, *ThreadTree;

优点：可以快速找到前驱和后继结点，提高遍历效率
缺点：插入删除操作变复杂

三、树、森林与二叉树的转换

1. 树转二叉树

口诀：“加线、抹线、旋转”

1. 加线：兄弟结点间连虚线
2. 抹线：只保留每个结点与最左孩子的连线
3. 旋转：虚线向右下方旋转45°

2. 森林转二叉树

1. 先将森林中每棵树转换为二叉树
2. 将后面的二叉树作为前面二叉树根结点的右子树

3. 遍历关系

• 树的先根遍历 ≡ 二叉树的先序遍历
• 树的后根遍历 ≡ 二叉树的中序遍历
• 森林的先序遍历 ≡ 二叉树的先序遍历

四、树和二叉树的应用

1. 哈夫曼树与哈夫曼编码

什么是哈夫曼树？

哈夫曼树是带权路径长度最短的二叉树，广泛应用于数据压缩。

关键概念：

• 带权路径长度 = 路径长度 × 结点权值
• 树的带权路径长度 = 所有叶结点的带权路径长度之和

哈夫曼算法构造步骤

1. 将所有结点放入优先队列（按权值排序）
2. 每次取出两个权值最小的结点
3. 创建新结点作为它们的父结点，权值为两者之和
4. 将新结点放回队列
5. 重复直到只剩一个结点（根结点）

哈夫曼编码

• 左分支标0，右分支标1（或相反）
• 从根到叶结点的路径就是该字符的编码
• 保证前缀编码性质：任何编码都不是其他编码的前缀

特点：

• 频率高的字符编码短
• 频率低的字符编码长
• 平均编码长度最短

2. 并查集

并查集是处理不相交集合的树型数据结构。

核心操作：

• Find(x)：查找x属于哪个集合
• Union(x, y)：合并x和y所在的集合

// 查找操作（带路径压缩）
int Find(int x) {if (parent[x] != x) {parent[x] = Find(parent[x]);  // 路径压缩}return parent[x];
}// 合并操作
void Union(int x, int y) {int rootX = Find(x);int rootY = Find(y);if (rootX != rootY) {parent[rootX] = rootY;}
}

五、实战编程与常见问题

1. 经典算法实现

求二叉树的高度

// 递归求二叉树高度
int TreeHeight(BiTree T) {if (T == NULL) return 0;int leftHeight = TreeHeight(T->lchild);int rightHeight = TreeHeight(T->rchild);return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

统计二叉树结点个数

// 递归统计结点数
int CountNodes(BiTree T) {if (T == NULL) return 0;return CountNodes(T->lchild) + CountNodes(T->rchild) + 1;
}

判断是否为完全二叉树

bool IsComplete(BiTree T) {if (T == NULL) return true;Queue Q;InitQueue(&Q);EnQueue(&Q, T);bool flag = false;  // 标记是否遇到空结点while (!IsEmpty(Q)) {BiTree current;DeQueue(&Q, &current);if (current == NULL) {flag = true;} else {if (flag) return false;  // 遇到空结点后又遇到非空结点EnQueue(&Q, current->lchild);EnQueue(&Q, current->rchild);}}return true;
}

2. 面试高频题目

题目1：二叉树的镜像

问题：翻转一棵二叉树（每个结点的左右子树交换）

BiTree MirrorTree(BiTree T) {if (T == NULL) return NULL;// 交换左右子树BiTree temp = T->lchild;T->lchild = T->rchild;T->rchild = temp;// 递归处理子树MirrorTree(T->lchild);MirrorTree(T->rchild);return T;
}

题目2：二叉树的最大路径和

问题：给定一个二叉树，找到任意一条路径的最大数字和

int maxSum = INT_MIN;int MaxPathSumHelper(BiTree T) {if (T == NULL) return 0;// 递归计算左右子树的最大贡献值int left = max(0, MaxPathSumHelper(T->lchild));int right = max(0, MaxPathSumHelper(T->rchild));// 当前路径的最大值int currentMax = T->data + left + right;maxSum = max(maxSum, currentMax);// 返回以当前结点为根的最大路径和return T->data + max(left, right);
}

题目3：验证二叉搜索树

bool IsValidBST(BiTree T, int minVal, int maxVal) {if (T == NULL) return true;if (T->data <= minVal || T->data >= maxVal) {return false;}return IsValidBST(T->lchild, minVal, T->data) && IsValidBST(T->rchild, T->data, maxVal);
}// 调用入口
bool ValidateBST(BiTree T) {return IsValidBST(T, INT_MIN, INT_MAX);
}

3. 性能优化技巧

非递归遍历（避免栈溢出）

// 非递归中序遍历
void InOrderNonRecursive(BiTree T) {Stack S;InitStack(&S);BiTree current = T;while (current != NULL || !IsEmpty(S)) {// 一直向左走到底while (current != NULL) {Push(&S, current);current = current->lchild;}// 弹出并访问结点Pop(&S, &current);visit(current);// 转向右子树current = current->rchild;}
}

层序遍历的变种（按层输出）

void PrintByLevel(BiTree T) {if (T == NULL) return;Queue Q;InitQueue(&Q);EnQueue(&Q, T);while (!IsEmpty(Q)) {int levelSize = QueueSize(&Q);// 处理当前层的所有结点for (int i = 0; i < levelSize; i++) {BiTree current;DeQueue(&Q, &current);printf("%d ", current->data);if (current->lchild) EnQueue(&Q, current->lchild);if (current->rchild) EnQueue(&Q, current->rchild);}printf("\n");  // 换行表示层结束}
}

4. 实际应用案例

文件系统目录树

typedef struct FileNode {char name[256];bool isDirectory;struct FileNode* firstChild;struct FileNode* nextSibling;struct FileNode* parent;
} FileNode;// 添加子文件/目录
void AddChild(FileNode* parent, FileNode* child) {child->parent = parent;child->nextSibling = parent->firstChild;parent->firstChild = child;
}// 遍历目录（类似树的先根遍历）
void ListDirectory(FileNode* root, int depth) {if (root == NULL) return;// 打印缩进for (int i = 0; i < depth; i++) printf("  ");printf("%s%s\n", root->name, root->isDirectory ? "/" : "");// 递归遍历子目录FileNode* child = root->firstChild;while (child != NULL) {ListDirectory(child, depth + 1);child = child->nextSibling;}
}

总结

树和二叉树是数据结构中的重要概念，它们以层次化的方式组织数据，具有以下特点：

1. 树结构模拟了现实世界的层次关系，直观易懂
2. 二叉树是最重要的树类型，支持多种高效的操作
3. 遍历算法是操作树的基础，四种遍历方式各有用途
4. 转换技巧："左孩子右兄弟"是树与二叉树转换的核心
5. 实际应用广泛：文件系统、表达式求值、数据压缩、数据库索引等

通过本章的学习，我们不仅掌握了树的理论知识，还学会了实际编程技巧。树结构的思想将伴随我们整个编程生涯，从简单的文件管理到复杂的算法设计，都离不开树的概念。

在后续的学习中，我们还会遇到更多基于树的高级数据结构，如堆、B树、红黑树等。掌握好基础的树和二叉树知识，将为学习这些高级结构打下坚实的基础。

📝 学习小贴士：树结构无处不在！下次看到文件夹、组织架构图、族谱时，不妨想想它们的树结构特点，这样能帮助你更好地理解和应用树的概念。

Code_流苏(CSDN)（一个喜欢古诗词和编程的Coder）
点赞加关注，收藏不迷路！本篇文章对你有帮助的话，还请多多点赞支持！