数据结构（C语言篇）：（十一）二叉树概念介绍

引言

二叉树是一种重要的数据结构，广泛应用于计算机科学的各个领域。其层次化的结构特点能够高效地支持数据的存储、查找和操作，是算法设计与优化的基础工具之一。二叉树的每个节点最多包含两个子节点，这种简洁而灵活的特性使其成为平衡树、堆、哈夫曼编码等高级数据结构的实现基础。通过深入理解二叉树的基本概念与遍历方式，可以更好地掌握递归、分治等核心算法思想，并为后续学习更复杂的树形结构（如二叉搜索树、AVL树）奠定理论基础。本文将系统介绍二叉树的定义、性质、存储方式及常见操作，帮助读者建立完整的知识框架。下面就让我们正式开始吧！

一、树

1.1 树的概念与结构

树是一种非线性的数据结构，它是由 n（n>=0） 个有限结点组成的一个具有层次关系的集合。把它叫做树是因为它看起来就好像一个倒挂着的树，也就是说它是根朝上，而叶朝下的。

对于树的结点，我们可以做出如下定义：

• 有一个特殊的结点，被称为根节点，根节点是没有前驱结点的。
• 除了根节点之外，其余的结点被分成了M(M>0) 个互不相交的集合 T1、T2、……、Tm ，其中每一个集合Ti(1 <= i <= m) ⼜是⼀棵结构与树类似的⼦树。每棵子树的根节点有且只有一个前驱结点，可以有0个或多个后继结点。因此我们可以称树为递归定义的。

对于树的结构，我们可以直观地拿来与现实中的树对比一下：

在树形结构中，子树之间是不能有交集的，否则就不是树形结构了。

我们同样也可以对非树形结构做出定义如下：

• 子树是不相交的（如果存在相交就是图了）；
• 除了根结点外，每个结点有且仅有⼀个⽗结点；
• ⼀棵N个结点的树有N-1条边。

同样地，非树形结构的示意图如下所示：

1.2 树的相关术语

1. 父结点/双亲结点：若一个结点含有子结点，那么就称呼这个结点为其子结点的父结点。如上图所示，A是B的父结点。
2. 子结点/孩子结点：一个结点含有的子树的根结点称为该结点的子结点。如上图所示，B是A的子结点。
3. 结点的度：一个结点有几个子结点，它的度就是多少。如A的度为6，F的度为2，K的度为0.
4. 树的度：一棵树中，最大的结点的度称为树的度。如上图，树的度为6。
5. 叶子结点/终端结点：度为0的结点称为叶结点。如上图，B、C、H、I……等结点称为叶结点。
6. 分支结点/非终端结点：度不为0的结点。如上图所示，D、E、F、G……等结点为分支结点。
7. 兄弟结点：具有相同父结点的结点互称为兄弟结点（亲兄弟）。如上图，B、C是兄弟结点。
8. 结点的层次：从根节点开始定义起，根为第一层，根的子结点为第二层，以此类推。
9. 树的高度或深度：树中结点的最大层次。如上图，树的高度为4。
10. 结点的祖先：从根到该结点所经过分支上的所有结点。如上图，树的高度为4。
11. 路径：一条从树中任意的结点出发，沿着父结点、子结点连接，达到任意结点的序列。比如上图中，A到Q的路径为：A-E-J-Q；H到Q的路径H-D-A-E-J-Q。
12. 子孙：以某结点为根的子树中任一结点都被称为该结点的子孙。如上图，所有结点都是A的子孙。
13. 森林：由 m（m>0） 棵互不相交的树的集合称为森林。

1.3 树的表示

对于树的表示，我们采用孩子兄弟表示法。

树结构相对于线性表是比较复杂的，其存储结构要表示起来还是比较麻烦的。既要保存值域，又要保存结点和结点之间的关系。实际上，树有很多种表示方法，例如：双亲表示法、孩子表示法、孩子双亲表示法以及孩子兄弟表示法等等。我们这里就来了解一下其中最常用的孩子兄弟表示法。

先来看看表示形式：

struct TreeNode
{
    struct Node* child; // 左边开始的第⼀个孩⼦结点
    struct Node* brother; // 指向其右边的下⼀个兄弟结点
    int data; // 结点中的数据域
};

画图分析如下：

1.4 树形结构的实际运用场景

文件系统是计算机存储和管理文件的一种方式，它是利用树形结构来组织和管理文件和文件夹的。在文件系统中，树形结构是被广泛应用的。它通过父结点和子结点之间的关系来表示不同的层级的文件和文件夹之间的关联。如下所示：

二、二叉树

2.1 概念与结构

在树形结构中，我们最常用的就是二叉树了，一棵二叉树是结点的一个有限集合，该集合是由一个根节点加上两棵别称为左子树和右子树的二叉树组成，或者为空。

由上图，我们可以看出，二叉树具备有如下的特点：

1. 二叉树不存在度大于2的结点；
2. 二叉树的子树有左右之分，次序是不能颠倒的，因此二叉树是一种有序树。

需要注意的是，对于任意的二叉树都是由以下几种情况复合而成的：

2.2 特殊的二叉树

2.2.1 满二叉树

一个二叉树，如果每一个层的结点数都达到最大值，那么这个二叉树就是满二叉树。这也就是说，如果一个二叉树的层数为K，且结点总数是

2^{k}-1

，那么它就是满二叉树。如下图所示：

那么我们应该推导计算满二叉树的结点数量的公式呢？

这个公式的推导基于等比数列求和，因为每一层的节点数呈指数级增长。对于高度为h的满二叉树，第k层的节点数为2^(k-1)，从第1层到第h层累加即为总节点数。例如，高度为3的满二叉树总节点数为1 + 2 + 4 = 7，符合公式2^3 - 1 = 7的结果。

另一种情况是满二叉树的定义可能被扩展为所有叶子节点位于同一层，此时总节点数仍为2^h - 1，其中h为树的高度。如果题目中给出的是满二叉树的层数（即深度），需要注意层数与高度的关系（通常高度=层数-1）。例如，层数为4的满二叉树总节点数为2^(4) - 1 = 15。

实际应用中，只需明确树的高度或层数即可快速计算。若已知叶子节点数L，满二叉树的总结点数也可表示为2L - 1，因为叶子节点数L = 2^(h-1)，代入原公式即可得到这一关系。

2.2.2 完全二叉树

完全二叉树是一种效率很高的数据结构，它是由满二叉树引出来的。对于深度为K的、有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时，就称之为完全二叉树。需要注意的是满二叉树是一种特殊的完全二叉树。

我们根据满二叉树的特点可以得到二叉树有以下性质：

1）若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有

2^{i-1}

个结点； 2）若规定根结点的层数为1，则深度为h的二叉树的最大结点数是

2^{h}-1

； 3）若规定根结点的层数为1，则具有n个结点的满二叉树的深度为

h=\log_2(n+1)

（log以2为底，n+1为对数）。

2.3 二叉树存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，另一种链式结构。

2.3.1 顺序结构

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为如果不是完全二叉树就会存在空间上的浪费，完全二叉树就更适合使用顺序结构来存储。

下面我们通过两个示意图来对比一下完全和非完全二叉树的顺序存储：

在现实中我们通常把堆（也是二叉树的一种，后面的博客中会专门为大家介绍）使用顺序结构的数组来存储。需要注意的是，这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，另一个是操作系统中管理内存的一块区域分段。

2.3.2 链式结构

二叉树的链式存储结构是指用链表来表示一棵二叉树，即用链来表示元素的逻辑关系。通常我们是让链表中的每个结点由三个域组成，即数据域和左右指针域。左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链，当前我们主要学习的就是二叉链。后续博主将会为大家介绍高阶数据结构（如红黑树等），此时就会用到三叉链。

我们依旧来画示意图，感受一下二叉链表和三叉链表在结构上的区别：

总结

本期博主为大家简单介绍了一下树和二叉树的相关概念，在下期博客中我们将来尝试实现二叉树。请大家多多关注哦！