【图解数据结构】大佬的入门笔记：一文带你彻底搞懂“树”与“二叉树”

数据结构是程序员的内功心法，而“树”结构，无疑是这心法中极为重要的一章。它无处不在，从你电脑的文件夹到复杂的数据库索引，背后都有树的身影。

这篇文章将带你从最基础的“树”概念出发，层层递进，最终聚焦于我们最常用、最重要的“二叉树”。无论你是初学者还是准备面试的同学，这篇详尽的笔记都将帮助你构建坚实的知识体系。

---

🌳 1. 万物之始：到底什么是“树”？

在计算机科学中，“树”是一种非线性的数据结构，它模仿了自然界中树的形态，只不过是一棵倒挂的树——根在上，叶在下。

1.1 树的概念与结构

树（Tree）是由 n (n >= 0) 个有限结点组成的一个具有层次关系的集合。它有以下核心特点：

• 递归定义：树由一个特殊的根结点 (Root) 和若干棵互不相交的子树 (Subtree) 构成。这些子树本身也都是独立的树。
• 层级关系：除根结点外，每个结点有且仅有一个父结点（也叫前驱）。一个结点可以有零个或多个子结点（也叫后继）。
• 无环与连通：树中的子树之间不能有交集（否则就变成了更复杂的“图”结构）。从根到任意结点都有唯一的路径。一棵 N 个结点的树，恰好有 N-1 条边。

一个简单的树结构示例

1.2 树的相关术语

要学好树，得先统一“黑话”，下面这张图和列表涵盖了所有基本术语：

树的术语图解

• 父结点 (Parent)：结点的上一级结点，如 A 是 B 的父结点。
• 子结点 (Child)：结点的下一级结点，如 B、C 是 A 的子结点。
• 兄弟结点 (Sibling)：拥有相同父结点的结点，如 B 和 C 互为兄弟。
• 结点的度 (Degree)：一个结点拥有的子树（或子结点）的个数。上图中，A的度为2，B的度为2，C的度为0。
• 树的度：一棵树中，所有结点度的最大值。
• 叶子结点 (Leaf)：度为 0 的结点，也称终端结点。🍃
• 分支结点 (Branch)：度不为 0 的结点，也称非终端结点。
• 结点的层次 (Level)：从根开始，根为第 1 层，根的子结点为第 2 层，以此类推。
• 树的高度/深度 (Height/Depth)：树中结点的最大层次。
• 祖先 (Ancestor)：从根到某结点路径上的所有结点，都是该结点的祖先。
• 子孙 (Descendant)：某结点的子树中的任意结点，都称作该结点的子孙。
• 森林 (Forest)：m (m > 0) 棵互不相交的树的集合。

1.3 树的表示方法

如何用代码来表示这种灵活的结构呢？最经典的方法之一是 “孩子兄弟表示法”。

这种方法非常巧妙，无论一个结点的度是多少，我们都可以用固定的结构来表示它：

struct TreeNode
{
    // 指向我的第一个孩子
	struct TreeNode* firstChild; 
    // 指向我的下一个兄弟
	struct TreeNode* nextSibling; 
    // 结点存储的数据
	int data; 
};

• firstChild 指针永远指向自己的第一个孩子。
• nextSibling 指针则将自己的所有兄弟连接起来形成一个链表。

1.4 树的应用场景

最经典的应用莫过于我们每天都在使用的 文件系统。根目录 / 就是树的根，各个文件夹是分支结点，文件则是叶子结点，构成了一个清晰的层级结构。

---

✨ 2. 主角登场：二叉树

通用树的结构灵活，但也意味着实现起来相对复杂。在实际应用中，我们更常使用一种结构更规整、更简单的特例——二叉树 (Binary Tree)。

2.1 概念与结构

顾名思义，二叉树是“分叉不超过两个”的树。它是一个有限的结点集合，这个集合或者为空，或者由一个根结点加上两棵互不相交的、分别称为左子树和右子树的二叉树组成。

二叉树的核心特点：

1. 度数限制：二叉树中不存在度大于 2 的结点。每个结点最多只有两个孩子。
2. 有序性：子树有左右之分，其次序不能任意颠倒。一棵结点的左子树和右子树交换后，就变成了另一棵不同的二叉树。

2.2 两种特殊的二叉树

在二叉树家族中，有两位“明星成员”，它们的结构非常规整。

2.2.1 满二叉树 (Full Binary Tree)

定义：一个二叉树，如果它的每一层结点数都达到了该层的最大值，则称其为满二叉树。它像一个完美的等边三角形。

如果一棵满二叉树的深度为 k，那么它的总结点数一定是 $2^k-1$。

2.2.2 完全二叉树 (Complete Binary Tree)

定义：一棵深度为 k，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1 到 n 的结点一一对应时，称之为完全二叉树。

说人话就是：这棵树除了最后一层，其他层都是满的。并且，最后一层的结点都从左到右连续排列，中间没有空缺。

💡 重要关系：满二叉树是一种特殊的完全二叉树。

graph TD
    subgraph 满二叉树 (也是完全二叉树)
        A1-->B1; A1-->C1;
        B1-->D1; B1-->E1;
        C1-->F1; C1-->G1;
    end
    subgraph 完全二叉树 (但不是满二叉树)
        A2-->B2; A2-->C2;
        B2-->D2; B2-->E2;
        C2-->F2;
    end
    subgraph 非完全二叉树
        A3-->B3; A3-->C3;
        B3-->D3; C3-->F3;
    end

2.3 💡 二叉树的重要性质

这几个性质在笔试面试中经常作为计算题出现：

1. 若规定根的层数为 1，则一棵非空二叉树的第 i 层上最多有 $2^{i-1}$ 个结点。
2. 若规定根的层数为 1，则深度为 h 的二叉树的最大结点数是 $2^h-1$。
3. 对于任何一棵二叉树，若叶子结点数为 $n\_0$，度为2的结点数为 $n\_2$，则 $n\_0=n\_2+1$。
4. 具有 n 个结点的完全二叉树的深度为 $$\begin{gathered} lfloor \\ log\_2n \\ rfloor+1 \end{gathered}$$。

---

💾 3. 计算机如何“存放”一棵二叉树？

理论要落地，必须有合适的存储结构。

3.1 顺序结构 (数组存储)

使用数组来存储二叉树，将树的结点按照层序遍历的顺序依次放入数组。

• 优点：对于完全二叉树来说，这种方式非常节省空间，并且可以根据数组下标快速计算出父子关系（父 i，左孩 2i+1，右孩 2i+2），无需指针。
• 缺点：对于非完全二叉树（特别是“歪脖子树”），会浪费大量存储空间。

现实应用：数据结构中的堆 (Heap) 通常就是一棵完全二叉树，因此总是用数组来存储。注意，此处的“堆”与操作系统内存管理中的“堆区”是两个完全不同的概念。

3.2 链式结构 (指针存储)

这是最常用、最灵活的方式。为每个结点创建一个结构体，包含数据和指向孩子的指针。

• 二叉链：最常见的结构，包含三个域：数据域、左孩子指针、右孩子指针。

  typedef struct BTNode {
      int data;
      struct BTNode* left;
      struct BTNode* right;
  } BTNode;
  

• 三叉链：在二叉链的基础上，增加一个指向父结点的指针。这在某些高级数据结构（如红黑树）中非常有用，方便向上回溯。

---

🎬 总结与预告

恭喜你！至此，你已经掌握了从“树”到“二叉树”的所有核心概念。我们来快速回顾一下：

• 树是一种递归定义的、具有层次关系的非线性结构。
• 二叉树是一种特殊的、有序的、度不超过2的树。
• 满二叉树和完全二叉树是两种结构规整、性质优美的二叉树。
• 存储方式主要有适合完全二叉树的数组和更通用的链表。

理论是基础，实践是王道。在下一期中，我们将亲手用C语言代码实现二叉树的创建、遍历、销毁等所有核心操作，将今天所学的理论知识转化为真正的编程能力！

如果觉得这篇文章对你有帮助，请不要吝啬你的 点赞 👍、收藏 ⭐、关注 ✅！我们下期见！