树和二叉树详细讲解

妖狐艹你老母 2024-03-16 22:50 29阅读 0赞

## 前言 ##

在上篇文章中，向大家介绍了**线性数据结构中的栈、队列和串三种数据结构，** 相对来说比较简单，栈的特点是先进后出(FILO)，队列的特点是先进先出(FIFO)。栈包含入栈和出栈两个操作，两个操作操作的都是栈顶元素；队列包含入队和出队两个操作，元素从队尾进入队列，需要时从队头取出元素。

--------------------

全文大约【**4500】** 字，不说废话，只讲可以让你学到技术、明白原理的纯干货！本文带有丰富的案例及配图视频，让你更好地理解和运用文中的技术概念，并可以给你带来具有足够启迪的思考…

## 一. 树的简介 ##

### 1. 概念 ###

**树(Tree)** 是非线性结构的典型代表。在树型数据结构中，数据元素之间存在一对多的关系。在数据结构中，对树的定义是：**树是由n(n>0)个有限结点组成一个具有层次关系的集合**。当n=0时，称为空树。

之所以把这些由层次关系的结点集合称之为树，主要是因为其在形状上看起来特别像一棵倒挂的树，即树根朝上，树叶朝下。首先**壹哥**给出树结构所具备的特点：

(1). 树有且仅有一个特定的**根(Root)结点**。

(2). 除了根结点，其余每个结点都有且只有一个直接前驱，这个前驱结点叫**父结点**.

(3). 树的每个结点都可以有多个后继，叫做**子结点**。没有后继的结点称为**叶子结点**。有父结点，也有子结点，这样的结点被称为**中间结点或分支结点**。

(4). 除了根结点，其余结点可分为m(m>0)个互不相交的有限集合。其中每一个集合本身又是一棵树，称为子树。

![89f7e6f7c41047df9ef23262d2b8c3d7_tplv-k3u1fbpfcp-zoom-1.image][]

但是，如果产生子树相交的情况，就不符合树结构的定义，也就不属于树了。比如下图：

![749427bacf5e4d01abffd3e700439c89_tplv-k3u1fbpfcp-zoom-1.image][]

如上两图所示，左图中②和③有相交，右图中结点②和节点③均与节点⑤相连，这两种情况下都不能称之为树。

### 2. 基本术语 ###

#### 2.1 树的高度和深度 ####

**树的最大层级数，被称为树的高度或深度**。我们通过图例说明如下：

![70e72296fff24253a374ed583d81a22f_tplv-k3u1fbpfcp-zoom-1.image][]

如上图所示，该树的高度是4，深度为4。根结点在第1层，结点8、9、10位于第4层。

**备注**：托马斯·科尔曼等人所著的《算法导论》一书中，树的高度是从“0”开始计数的，在本篇文章中，我们遵照惯例，树的高度是从“1”开始计数。

#### 2.2 结点关系 ####

**具有同一父结点的结点互相称为兄弟结点**。比如，上文图例所示中：结点2和3，结点4和5，结点6和7，结点8和9彼此是兄弟结点。

#### 2.3 树的度数 ####

特别的，我们把：**一个结点的子结点的个数称为该结点的度数**。**度为0的结点就是叶子结点**，而度不为0的结点就是分支结点。同时，我们还规定：**一棵树的度指的是该树中结点的最大度数**。比如，上文所示图例中：结点2、3、4的度为2，结点6的度为1，结点5、7、8、9、10的度为0。这棵树的度为2。

### 3. 树的分类 ###

根据度的大小，我们可以**将树可以分为二叉树和多路树。堆也属于一种多路树结构，另外根据度的大小，堆也分为二叉堆和多叉堆**。具体的逻辑关系如下图所示：

![在这里插入图片描述][85167aa10c284d48b52d7b57206d5fad.png]

在如上的示例图中，给出了树型数据结构所涉及的常见的分类种类，在后续的文章中，我们会逐渐学习到，大家稍安勿躁，**接下来让我们先从二叉树开始学起。**

## 二. 二叉树 ##

### 1. 概念 ###

**二叉树(Binary Tree)** 是树的一种常见形式。二叉树的任意结点最多可以有两个子结点，也可以只有一个或者没有子结点。因此**二叉树的度数一定小于等于2**。二叉树结点的两个子结点，一个被称为**左子结点**，一个被称为**右子结点**。二叉树严格区分左右子结点，两个子结点的顺序是固定的，即使只有一棵子树也要区分左右。

如果我们把二叉树继续进行分类，就会衍生出**满二叉树**和**完全二叉树**。

*  **满二叉树**：满二叉树是一种理想状态。二叉树的所有非叶子结点都存在左右子结点，每个非叶子结点的度都是2，并且所有叶子结点都在同一层上，那么这个树就是满二叉树。

![f9dc0e4dbe7141be81e1d04431a154bd_tplv-k3u1fbpfcp-zoom-1.image][]

**如上图所示：** 左图中，所有非叶子结点都存在左右子结点，每个非叶子结点的度都是2，同时所有叶子结点均在同一层，符合满二叉树的定义，所以左图是满二叉树。右图中，虽然每个非叶子结点都有左右子结点，且每个非叶子结点的度都是2，但所有叶子结点并不在同一层，因此不属于满二叉树。由此，我们 可以知道，判断一棵二叉树是否是满二叉树，有三个条件：

*  每个非叶子结点都存在左右2个子结点
 *  每个非叶子结点的度都是2
 *  所有叶子结点均在同一层

以上三个条件，实际前两个条件描述的是同一回事。

*  **完全二叉树**：如果二叉树中除去最后一层结点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。

![b6506f6bfe0540bfaddb584a207f2ac0_tplv-k3u1fbpfcp-zoom-1.image][]

如上图所示，结合完全二叉树的定义，可以知道完全二叉树需要满足两个条件：

*  除最后一层外为满二叉树；
 *  最后一层的结点依次从左至右，中间不能有缺失。

### 2. 性质 ###

二叉树的性质，也是二叉树有关的一些结论，所谓结论，就是指这些设计到二叉树相关的特性的内容，可以直接作为结果或者结论进行引用。我们依然分类进行描述：

#### 2.1 普通二叉树的性质 ####

*  **第i层最多可以有2** **i-1** **个结点**：根据结论，我们可以验证二叉树第1层最多有1个结点，第2层最多有2个结点，第3层最多有4个结点，依次类推。当然，需要注意的是，此处说的是最多，并不是一定会有，要区分清楚。
 *  **若二叉树深度为k，则二叉树最多有2** **k** **-1个结点**：该结论也可以通过举例验证，二叉树的深度为1时，结点最多就1个；深度为2时，结点最多有3个；深度为3时，结点最多为7个。依次类推，均符合该结论公式。
 *  **若叶子结点数为n0，度为2的结点数为n2，则n0=n2+1**：该结论也可以用另外一句话表述，即叶子结点数比度为2的结点多1个。

#### 2.2 满二叉树的性质 ####

满二叉树是特殊的二叉树，因此所有的普通二叉树的性质满二叉树都满足。除此之外，满二叉树特有的性质有：

*  满二叉树中**第i层一定有2** **i-1** **个结点**。
 *  深度为k的满二叉树一定**有2** **k** **-1个结点，且一定有2** **k-1** **个叶子结点**。
 *  具有n个结点的**满二叉树的深度为log** **2** **(n+1)** 。

#### 2.3 完全二叉树的性质 ####

![1c8ab1fa023947cd9eb43f8653c893d9_tplv-k3u1fbpfcp-zoom-1.image][]

如上图所展示的是一棵完全二叉树，为了方便区分该二叉树的每一个结点，我们其将含有的结点按照层次从左到右依次标号，依次为1-11。若根据该规则，则对于任意一个结点i，完全二叉树具有以下结论：

*  若i>1，则**i结点的父结点的编号是i/2(向下取整)** 。比如：i=5结点，其父结点编号为2，满足结论。
 *  若2*i>n(n为总结点的个数)，则结点i肯定没有左叶子结点，否则其左子结点是结点2*i。
 *  若2*i+1>n，则结点i肯定没有右子结点；否则右子结点是结点2*i+1。
 *  完全二叉树只能有0个或1个度为1的结点，**叶子结点数比度为2的结点数多1个**。

**总结：** 对于普通二叉树，满二叉树，以及完全二叉树的特点和其所具有的性质，在使用时最简单的方式是通过画图例的方式进行验证，当然如果我们能把上文中列出的所有性质公式都记住自然是最好的。

### 3. 二叉树的存储 ###

在前面的文章中，我们已经学习过数组和链表，此处刚好可以使用这种结构对二叉树的结点进行存储。因此，二叉树的存储一共有两种方式，分别是：**顺序存储、链式存储**。

#### 3.1 顺序存储(数组) ####

所谓的顺序存储，指的是使用数组存储的二叉树。

我们在使用数组存储时，会按照层级顺序把二叉树的结点放到数组中对应的位置上。如果某一个结点的左子结点或右子结点空缺，则数组的相应位置也要空出来。对于一个稀疏的二叉树(子结点不满)来说，用顺序存储是非常浪费空间的。所以**二叉树的顺序存储一般只适用于完全二叉树**，或者说完全二叉树才适合使用顺序表存储。当顺序存储普通二叉树时，需要提前将普通二叉树转化为完全二叉树。

![d804d97a08a54535beda266aa2200dca_tplv-k3u1fbpfcp-zoom-1.image][]

如上图所示，给定的二叉树是一棵普通的二叉树。若使用数组进行存储，首先需要将该二叉树补充调整为一棵完全二叉树如上右图所示，需要添加的两个结点使用虚线表示（不存储具体数据，空余），然后再使用数组存储该完全二叉树。可以看到，上图的数组中，下标4和下标5位置空余，原因是两位位置恰好对应的是补充的两个结点。

由此，我们也能进一步理解：若使用数组存储普通二叉树，往往会浪费存储空间。

#### 3.2 二叉树链式存储(链表) ####

**我们推荐大家使用链表对二叉树进行存储**。链式存储二叉树，其结点结构与双向循环链表一致，每一个结点包含三个部分：**存储数据的data变量、指向左子结点的left指针、指向右子结点的right指针**，这样的链表称为二叉链表。如下图所示：

![3f48e48686874ca7b27b85398201f4db_tplv-k3u1fbpfcp-zoom-1.image][]

## 三. 遍历操作 ##

在前面的文章中，我们已经介绍过数组的遍历和链表的遍历。所谓遍历就是按照某种逻辑规则，依次访问集合的每个元素的操作。对于二叉树，同样可以按照某种逻辑依次访问二叉树的每一个结点。二叉树的遍历可以分为两大类：**深度优先遍历、广度优先遍历**。

### 1. 深度优先遍历 ###

所谓**深度优先(** **depth first search，DFS** **)** ，顾名思义就是偏向于纵深，“一头扎到底”的访问方式。深度优先遍历又根据遍历顺序的不同分为三种：**前序遍历、中序遍历、后序遍历**。

#### 1.1 前序遍历 ####

所谓前序遍历，是指二叉树遍历每个子树的时候，都是按照根结点、左子树、右子树的顺序来遍历，因为根结点在前，所以叫做前序遍历。**前序遍历中根结点的优先级别最高**。如下图所示：

![67b142b02d774f17897d5ff07fdb40b2_tplv-k3u1fbpfcp-zoom-1.image][]

**如上图所示：**

*  先访问第一层，第一次只有一个结点，可以得到A结点。
 *  再访问第二层，第二层中B是A的左子树，而B又是第三层D和E的父结点，因此要先访问B结点。
 *  访问B后，再访问B的下一层即第三层。在第三层中，B的左子树D，又包含一个右子树G，因此，对于D和G来说，应该先访问D。因此访问D结点。
 *  访问D后，访问下一层即第四层，D只有一个右子树G，因此访问G结点。
 *  G结点访问结束后，意味着D和G组成的这课分支子树就结束了，进一步访问BDE这三个结点组成的分支子树。因为B和D已经被访问过了，所以访问E结点。
 *  访问E后，BDE组成的分支子树已经遍历结束，继续遍历ABC结点组成的子树，由于A和B已经被访问，因此访问C结点。
 *  依次类推，和左侧访问规则一样，继续访问得到F结点和H结点。

#### 1.2 中序遍历 ####

如果二叉树遍历每个子树的时候，都是按照左子树、根结点、右子树的顺序来遍历，因为**根结点在中间，所以叫做中序遍历**。如下图所示：

![e25ac814a4dd4d58909663eb8edb6c99_tplv-k3u1fbpfcp-zoom-1.image][]

如上图所示，虚线箭头和数字就是按照中序遍历的规则对二叉树进行遍历的步骤，最后可得到中序遍历顺序：D G B E A C H F。通过上面二叉树的图示和结果，我们还可以发现一个中序遍历的规律：**第一个元素是树结构中最左侧的元素，最后一个是树结构中最右侧的元素，根结点在中间位置输出**。

#### 1.3 后序遍历 ####

二叉树遍历每个子树的时候，都是按照左子树、右子树、根结点的顺序来遍历，因为根结点在最后，所以叫做后序遍历。如下图所示：

![dae80d1a0d774a16acd32b4f55a9a274_tplv-k3u1fbpfcp-zoom-1.image][]

如上图所示，虚线箭头和数字表示除了二叉树的后续遍历的步骤。我们发现出规律：**后序遍历第一个输出的元素是根结点左侧最底层第一个元素，最后一个输出的是根结点元素**。

### 2. 广度优先遍历 ###

**广度优先遍历(** **Breadth First Search，BFS** **)也叫层序遍历**，就是按照二叉树中的层次从左到右依次遍历每层中的结点。层序遍历的实现思路是利用队列来实现。先将树的根结点入队，然后再让队列中的结点出队。队列中每一个结点出队的时候，都要将该结点的左子结点和右子结点入队。当队列中的所有结点都出队，树中的所有结点也就遍历完成。此时队列中结点的出队顺序就是层次遍历的最终结果。如下图所示：

![c41c477067614a46857d0ebb634a60dd_tplv-k3u1fbpfcp-zoom-1.image][]

如上图所示，广度优先遍历比较容易理解，从上到下按层依次对二叉树的结点进行遍历，最后可得到遍历结果。

--------------------

## 四. 结语 ##

通过本篇内容，带大家开始学习树型数据结构，在实际应用中，二叉树又是使用最广泛的，特别是二叉树的几种遍历操作的规则，需要做着重掌握。在面试或应试考试中，通常会根据前序、中序、后序中的两种序列，询问另外一种树的遍历结果，大家要重点关注。

--------------------

**扫描文末二维码，get更多学习资料** ↓↓↓  
![在这里插入图片描述][2233363350674d4e83035506636ef9a6.png_pic_center]

[89f7e6f7c41047df9ef23262d2b8c3d7_tplv-k3u1fbpfcp-zoom-1.image]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/7595909d33f04166820a4f21963e7429.png
[749427bacf5e4d01abffd3e700439c89_tplv-k3u1fbpfcp-zoom-1.image]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/67ecd63efcd745739d871281aab0483d.png
[70e72296fff24253a374ed583d81a22f_tplv-k3u1fbpfcp-zoom-1.image]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/54f57e6c88124f2c8df2642c2ac05695.png
[85167aa10c284d48b52d7b57206d5fad.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/d69a7ecdb0f9471e8f0f6b8a5a6963f5.png
[f9dc0e4dbe7141be81e1d04431a154bd_tplv-k3u1fbpfcp-zoom-1.image]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/856e248039074df5a7c576b2b05ffd90.png
[b6506f6bfe0540bfaddb584a207f2ac0_tplv-k3u1fbpfcp-zoom-1.image]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/553070db367942bd83de8ddcb2070ba4.png
[1c8ab1fa023947cd9eb43f8653c893d9_tplv-k3u1fbpfcp-zoom-1.image]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/95e4365cb7eb484d8f55ea9034782219.png
[d804d97a08a54535beda266aa2200dca_tplv-k3u1fbpfcp-zoom-1.image]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/4556af5e518c4e42b2a5af7f468e3e1e.png
[3f48e48686874ca7b27b85398201f4db_tplv-k3u1fbpfcp-zoom-1.image]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/499490916f0e493db8069fffb572a388.png
[67b142b02d774f17897d5ff07fdb40b2_tplv-k3u1fbpfcp-zoom-1.image]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/9a37e000f82e46b0b9b65f4dc6ec0f45.png
[e25ac814a4dd4d58909663eb8edb6c99_tplv-k3u1fbpfcp-zoom-1.image]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/0baf9f0d38ef47599e8226bb2acb0034.png
[dae80d1a0d774a16acd32b4f55a9a274_tplv-k3u1fbpfcp-zoom-1.image]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/d9f5b43c907c4b53843dd7f3e0d6b621.png
[c41c477067614a46857d0ebb634a60dd_tplv-k3u1fbpfcp-zoom-1.image]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/6fcecde638384e628b56376cb213b032.png
[2233363350674d4e83035506636ef9a6.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/cb39333f6188419c9d86996b655db7d0.png