数据结构与算法之树

数据结构与算法之树（一）二叉树概念及遍历方式（图文并茂）

数据结构与算法之树（二）二叉查找树

数据结构与算法之树（三）AVL树

数据结构与算法之树（四）红黑树

数据结构与算法之树（一）二叉树概念及遍历方式（图文并茂）

文章目录

数据结构与算法之树（一）二叉树概念及遍历方式（图文并茂）一、树的基本概念二、二叉树的定义2.1 二叉树的定义2.2 满二叉树2.3 完全二叉树 三、二叉树的存储方式3.1 链式存储3.2 顺序存储 四、二叉树的遍历4.1 前序遍历4.2 中序遍历4.3 后续遍历

一、树的基本概念

首先我们看一看树长什么样

以上都是我画的树，其中每个元素我们称之为节点，用线连着相邻两个元素的关系我们称为父子关系

我们以下面这副图来讲解树中的各种概念

在上述这副图中，我们可以说A节点是B节点的父节点，B节点是A节点的子节点

因为B、C、D三个节点它们的父节点都是A节点，所以称它们为兄弟节点

我们把没有父节点的节点称为根节点，如A节点就是一个根节点

我们把没有子节点的节点称为叶子节点或叶节点，如E、F、G节点

关于树的概念还有高度、深度、层

高度：该节点到叶节点经历的边数

深度：该节点到根节点经历的边数

层：该节点的深度+1

树的高度：根节点的高度

上面这几个概念可能不好理解，看一下下面这个例子就好理解了

到这里你应该搞懂了树的众多概念了，我将其归纳如下，看你是否还能回忆起来

1.节点

2.父子关系

3.子节点

4.父节点

5.兄弟节点

6.叶子节点或叶节点

7.高度

8.深度

9.层

二、二叉树的定义

2.1 二叉树的定义

二叉树是一种特殊的树，所谓二叉树，其和树的区别是每个节点最多有两个子节点，如下图所示

又有两种特殊的二叉树：满二叉树、完全二叉树

2.2 满二叉树

满二叉树：所有的叶子节节点都在最底层，除叶子节点外，每个节点都有左右两个子节点

如下图就是一棵满二叉树

2.3 完全二叉树

完全二叉树：从上到下，从左到右，节点是连续的

下图就是一棵完全二叉树

上述这棵树，你按从上到下，从左到右的顺序看，确实它的节点是连续的，如下图就不是完全二叉树

上图不是完全二叉树，因为7和9之间少了一个节点

下面再回顾一下，关于二叉树这些定义，你理解了吗？

1.二叉树与树的区别

2.满二叉树的定义

3.完全二叉树的定义

三、二叉树的存储方式

二叉树是一种定义，关于其在内存中具体存储的方式有一下两种方式

1.基于指针的链式存储法

2.基于数组的顺序存储法

3.1 链式存储

我们先看一下直观的链式存储，这种存储方式的每个节点有三个字段，一个存储数据，一个为左子节点指针，一个为右子节点指针，如下定义

TreeNode { T data; //数据 TreeNode* left; //指向左子节点 TreeNode* right; //指向右子节点 }; 12345

我们只要存储树根，然后通过各个节点的左右子节点指针，就可以连成一棵树，如下所示

3.2 顺序存储

我们可以把一棵树的根节点编号为0，然后从上到下，从左到右，对每个节点进行编号，如下图所示

从上面这棵树，我们可以得到规律

左子节点的编号 = 父节点编号*2 + 1

右子节点的编号 = 父节点编号*2 + 2

父节点的编号 = （子节点编号-1）/ 2

到这里你可以停下来，根据上述的规则自己推导一下

如果我们将上述每个节点的编号对应数组的下标，然后将其存储到数组中，各个节点之间的父子关系我们完全可以通过上述的规律推导出来，这就是基于数组的顺序存储

上图是一颗完全二叉树，所以编完号之后，我们的数组是没有空缺项的，如果对于下面这棵树来编号，那么它的顺序存储会是怎样？

根据我们的编号规则，即使节点为NULL，也要为它编号，因为只有这样子，父子节点才会满足上述规律

NULL节点在数组中也是占用一项的，只是用于占位并不使用，所以其顺序存储如下

可以看到下标为5和8的数组元素为空

所以到这里我们可以看到顺序存储的缺点，就是如果当一棵树不是完全二叉树的时候，那么可能会存在许多空缺节点，使用顺序存储会造成内存空间的浪费

四、二叉树的遍历

二叉树的遍历分为前序遍历、中序遍历、后续遍历，它们的遍历顺序定义如下

前序遍历：当前节点、左子树、右子树

中序遍历：左子树、当前节点、右子树

后序遍历：左子树、右子树、当前节点

我们可以发现，如果当前节点的访问顺序在最前，那么就是前序遍历。当前节点的访问顺序在中间，那么就是中序遍历。当前节点的访问顺序在最后，那么就是后续遍历

下面我将超详细地演示前序遍历，这可能是你见过最详细地二叉树遍历教程了

首先准备一颗树，其中没有颜色的节点表示为空，我将其画出来是为了演示

然后再准备一个三角形

这个三角形是用来辅助我们观察，现在定义这样一个规则，三角形的定点表示我们关注节点（A节点），左下角表示左子树（B节点），右下角表示右子树（C节点）

二叉树的遍历其实是一个递归的过程，下面我将按照递归调用过程的步骤一步一步讲解前序遍历

4.1 前序遍历

前序遍历的顺序是先访问关注节点，再访问左子树，再访问右子树，请牢牢记住这个规则

前序遍历的结果我这里先给出

A B D E C F 1

OK，现在开始

1.首先我们的关注节点肯定从根节点开始

2.根据前序遍历的规则，我们会先访问关注节点（A节点），然后再访问左子树（B节点），此时关注节点就会跳转到B节点

3.根据前序遍历的规则，我们继续访问当前关注节点（B节点），然后再访问左子树（D节点），此时关注节点跳转到D节点

4.我们继续访问当前节点（D节点），然后再访问左子树，此时发现左子树为空，那么就继续放回到D节点

5.在D节点的时候，当前关注节点（D节点）已访问过，左子树也已经访问过，那么根据前序遍历的规则，就会访问右子树，可是现在发现右子树为空，那么关注节点就会继续返回到D节点

6.此时关注节点还是D节点，左子树访问过，右子树访问过，那么关注节点就会按原路返回到B节点

7.现在关注节点为B节点，左子树已经访问过，根据前序遍历的规则，现在访问右子树，关注节点跳转到E节点

8.现在关注节点为E节点，访问E节点，然后继续访问左子树，可是发现左子树为空，那么关注节点就会继续返回到E节点

9.此时关注节点已经访问过，左子树访问过，根据前序遍历的规则，就会继续访问右子树，此时发现右子树为空，那么就会继续返回到E节点

10.此时关注节点为E节点，当前关注节点已经访问过，左子树访问过，右子树访问过，那么关注节点就会原路放回到B节点

11.现在的关注节点为B节点，关注节点访问过，左子树访问过，右子树访问过，那么关注节点就会原路返回到A节点

12.此时关注节点为A节点，关注节点已经访问过，左子树访问过，根据前序遍历的规则，此时会关注节点会跳转到右子树（C节点），关注节点跳转到C节点

13.此时关注节点为C节点，会先访问关注节点（C节点），然后访问左子树，发现左子树为空，那么关注节点就会继续返回到C节点

14.现在关注节点为C节点，关注节点访问过，左子树访问过，现在访问右子树，关注节点跳转到F节点

15.现在关注节点为F节点，先访问关注节点（F节点），然后访问左子树，发现左子树为空，那么关注节点就继续返回到F节点

16.此时关注节点为F节点，关注节点已访问，左子树已访问，现在访问右子树，发现右子树为空，所以继续返回到F节点

17.现在关注节点是F节点，关注节点已访问，左子树已访问，右子树已访问，那么关注节点就原路返回到C节点

18.现在关注节点为C节点，关注节点已访问，左子树已访问，右子树已访问，那么关注节点就原路返回到A节点，此时整个前序遍历结束

二叉树的遍历实际上就是一个递归的过程，上述的前序遍历的代码如下

void preOrder(Node* root) { if (root == null) return; print root // 此处为伪代码，表示打印 root 节点 preOrder(root->left); //左子树 preOrder(root->right); //右子树

}

123456789

可以看到非常的简单，其本质就是递归自动地帮我们不断地压栈和出栈

如果你仔细观察，你会发现每个节点都会被访问3次，这就表明，在不断地压栈和出栈过程中，一个节点其对应的栈高度在整个过程中会到达三次

关于中序遍历和后续遍历，我这里会给出答案，不会再从头到尾推一边，第一觉得你自己应该去推一边，第二这实在太累人了

4.2 中序遍历

中序遍历的顺序：左子树、关注节点、右子树

中序遍历的结果

D B E A C F 1

遍历的过程

中序遍历的递归代码

void inOrder(Node* root) { if (root == null) return; preOrder(root->left); //左子树 print root // 此处为伪代码，表示打印 root 节点 preOrder(root->right); //右子树

}

123456789

4.3 后续遍历

后续遍历的顺序：左子树、右子树、关注节点

后续遍历的结果

D B E A C F 1

遍历的过程

后续遍历的递归代码

void postOrder(Node* root) { if (root == null) return; preOrder(root->left); //左子树 preOrder(root->right); //右子树 print root // 此处为伪代码，表示打印 root 节点

}

123456789

到这里你可能又会发现，三种遍历方式它们的路径都相同，只是访问节点的时机不同而已

是的，我们从三种遍历方式的代码种也可以看出，它们递归调用顺序都是一样的，只是节点的访问时间不同，所以就出现了这种情况

本篇文章到这里就结束了，适当总结一下，本文讲解的树的众多概念，讲解了什么是二叉树，什么是满二叉树，什么是完全二叉树，二叉树的存储方式，二叉树的三种遍历方式，详细剖析了前序遍历的过程

</div><div id="content_views" class="markdown_views prism-atom-one-light"> <!-- flowchart 箭头图标 勿删 --> <svg xmlns="http://www.w3.org/2000/svg" style="display: none;"> <path stroke-linecap="round" d="M5,0 0,2.5 5,5z" id="raphael-marker-block" style="-webkit-tap-highlight-color: rgba(0, 0, 0, 0);"></path> </svg> <p><strong>数据结构与算法之树</strong></p>

数据结构与算法之树（一）二叉树概念及遍历方式（图文并茂）

数据结构与算法之树（二）二叉查找树

数据结构与算法之树（三）AVL树

数据结构与算法之树（四）红黑树

数据结构与算法之树（一）二叉树概念及遍历方式（图文并茂）

文章目录

数据结构与算法之树（一）二叉树概念及遍历方式（图文并茂）一、树的基本概念二、二叉树的定义2.1 二叉树的定义2.2 满二叉树2.3 完全二叉树 三、二叉树的存储方式3.1 链式存储3.2 顺序存储 四、二叉树的遍历4.1 前序遍历4.2 中序遍历4.3 后续遍历

一、树的基本概念

首先我们看一看树长什么样

以上都是我画的树，其中每个元素我们称之为节点，用线连着相邻两个元素的关系我们称为父子关系

我们以下面这副图来讲解树中的各种概念

在上述这副图中，我们可以说A节点是B节点的父节点，B节点是A节点的子节点

因为B、C、D三个节点它们的父节点都是A节点，所以称它们为兄弟节点

我们把没有父节点的节点称为根节点，如A节点就是一个根节点

我们把没有子节点的节点称为叶子节点或叶节点，如E、F、G节点

关于树的概念还有高度、深度、层

高度：该节点到叶节点经历的边数

深度：该节点到根节点经历的边数

层：该节点的深度+1

树的高度：根节点的高度

上面这几个概念可能不好理解，看一下下面这个例子就好理解了

到这里你应该搞懂了树的众多概念了，我将其归纳如下，看你是否还能回忆起来

1.节点

2.父子关系

3.子节点

4.父节点

5.兄弟节点

6.叶子节点或叶节点

7.高度

8.深度

9.层

二、二叉树的定义

2.1 二叉树的定义

二叉树是一种特殊的树，所谓二叉树，其和树的区别是每个节点最多有两个子节点，如下图所示

又有两种特殊的二叉树：满二叉树、完全二叉树

2.2 满二叉树

满二叉树：所有的叶子节节点都在最底层，除叶子节点外，每个节点都有左右两个子节点

如下图就是一棵满二叉树

2.3 完全二叉树

完全二叉树：从上到下，从左到右，节点是连续的

下图就是一棵完全二叉树

上述这棵树，你按从上到下，从左到右的顺序看，确实它的节点是连续的，如下图就不是完全二叉树

上图不是完全二叉树，因为7和9之间少了一个节点

下面再回顾一下，关于二叉树这些定义，你理解了吗？

1.二叉树与树的区别

2.满二叉树的定义

3.完全二叉树的定义

三、二叉树的存储方式

二叉树是一种定义，关于其在内存中具体存储的方式有一下两种方式

1.基于指针的链式存储法

2.基于数组的顺序存储法

3.1 链式存储

我们先看一下直观的链式存储，这种存储方式的每个节点有三个字段，一个存储数据，一个为左子节点指针，一个为右子节点指针，如下定义

TreeNode { T data; //数据 TreeNode* left; //指向左子节点 TreeNode* right; //指向右子节点 }; 12345

我们只要存储树根，然后通过各个节点的左右子节点指针，就可以连成一棵树，如下所示

3.2 顺序存储

我们可以把一棵树的根节点编号为0，然后从上到下，从左到右，对每个节点进行编号，如下图所示

从上面这棵树，我们可以得到规律

左子节点的编号 = 父节点编号*2 + 1

右子节点的编号 = 父节点编号*2 + 2

父节点的编号 = （子节点编号-1）/ 2

到这里你可以停下来，根据上述的规则自己推导一下

如果我们将上述每个节点的编号对应数组的下标，然后将其存储到数组中，各个节点之间的父子关系我们完全可以通过上述的规律推导出来，这就是基于数组的顺序存储

上图是一颗完全二叉树，所以编完号之后，我们的数组是没有空缺项的，如果对于下面这棵树来编号，那么它的顺序存储会是怎样？

根据我们的编号规则，即使节点为NULL，也要为它编号，因为只有这样子，父子节点才会满足上述规律

NULL节点在数组中也是占用一项的，只是用于占位并不使用，所以其顺序存储如下

可以看到下标为5和8的数组元素为空

所以到这里我们可以看到顺序存储的缺点，就是如果当一棵树不是完全二叉树的时候，那么可能会存在许多空缺节点，使用顺序存储会造成内存空间的浪费

四、二叉树的遍历

二叉树的遍历分为前序遍历、中序遍历、后续遍历，它们的遍历顺序定义如下

前序遍历：当前节点、左子树、右子树

中序遍历：左子树、当前节点、右子树

后序遍历：左子树、右子树、当前节点

我们可以发现，如果当前节点的访问顺序在最前，那么就是前序遍历。当前节点的访问顺序在中间，那么就是中序遍历。当前节点的访问顺序在最后，那么就是后续遍历

下面我将超详细地演示前序遍历，这可能是你见过最详细地二叉树遍历教程了

首先准备一颗树，其中没有颜色的节点表示为空，我将其画出来是为了演示

然后再准备一个三角形

这个三角形是用来辅助我们观察，现在定义这样一个规则，三角形的定点表示我们关注节点（A节点），左下角表示左子树（B节点），右下角表示右子树（C节点）

二叉树的遍历其实是一个递归的过程，下面我将按照递归调用过程的步骤一步一步讲解前序遍历

4.1 前序遍历

前序遍历的顺序是先访问关注节点，再访问左子树，再访问右子树，请牢牢记住这个规则

前序遍历的结果我这里先给出

A B D E C F 1

OK，现在开始

1.首先我们的关注节点肯定从根节点开始

2.根据前序遍历的规则，我们会先访问关注节点（A节点），然后再访问左子树（B节点），此时关注节点就会跳转到B节点

3.根据前序遍历的规则，我们继续访问当前关注节点（B节点），然后再访问左子树（D节点），此时关注节点跳转到D节点

4.我们继续访问当前节点（D节点），然后再访问左子树，此时发现左子树为空，那么就继续放回到D节点

5.在D节点的时候，当前关注节点（D节点）已访问过，左子树也已经访问过，那么根据前序遍历的规则，就会访问右子树，可是现在发现右子树为空，那么关注节点就会继续返回到D节点

6.此时关注节点还是D节点，左子树访问过，右子树访问过，那么关注节点就会按原路返回到B节点

7.现在关注节点为B节点，左子树已经访问过，根据前序遍历的规则，现在访问右子树，关注节点跳转到E节点

8.现在关注节点为E节点，访问E节点，然后继续访问左子树，可是发现左子树为空，那么关注节点就会继续返回到E节点

9.此时关注节点已经访问过，左子树访问过，根据前序遍历的规则，就会继续访问右子树，此时发现右子树为空，那么就会继续返回到E节点

10.此时关注节点为E节点，当前关注节点已经访问过，左子树访问过，右子树访问过，那么关注节点就会原路放回到B节点

11.现在的关注节点为B节点，关注节点访问过，左子树访问过，右子树访问过，那么关注节点就会原路返回到A节点

12.此时关注节点为A节点，关注节点已经访问过，左子树访问过，根据前序遍历的规则，此时会关注节点会跳转到右子树（C节点），关注节点跳转到C节点

13.此时关注节点为C节点，会先访问关注节点（C节点），然后访问左子树，发现左子树为空，那么关注节点就会继续返回到C节点

14.现在关注节点为C节点，关注节点访问过，左子树访问过，现在访问右子树，关注节点跳转到F节点

15.现在关注节点为F节点，先访问关注节点（F节点），然后访问左子树，发现左子树为空，那么关注节点就继续返回到F节点

16.此时关注节点为F节点，关注节点已访问，左子树已访问，现在访问右子树，发现右子树为空，所以继续返回到F节点

17.现在关注节点是F节点，关注节点已访问，左子树已访问，右子树已访问，那么关注节点就原路返回到C节点

18.现在关注节点为C节点，关注节点已访问，左子树已访问，右子树已访问，那么关注节点就原路返回到A节点，此时整个前序遍历结束

二叉树的遍历实际上就是一个递归的过程，上述的前序遍历的代码如下

void preOrder(Node* root) { if (root == null) return; print root // 此处为伪代码，表示打印 root 节点 preOrder(root->left); //左子树 preOrder(root->right); //右子树

}

123456789

可以看到非常的简单，其本质就是递归自动地帮我们不断地压栈和出栈

如果你仔细观察，你会发现每个节点都会被访问3次，这就表明，在不断地压栈和出栈过程中，一个节点其对应的栈高度在整个过程中会到达三次

关于中序遍历和后续遍历，我这里会给出答案，不会再从头到尾推一边，第一觉得你自己应该去推一边，第二这实在太累人了

4.2 中序遍历

中序遍历的顺序：左子树、关注节点、右子树

中序遍历的结果

D B E A C F 1

遍历的过程

中序遍历的递归代码

void inOrder(Node* root) { if (root == null) return; preOrder(root->left); //左子树 print root // 此处为伪代码，表示打印 root 节点 preOrder(root->right); //右子树

}

123456789

4.3 后续遍历

后续遍历的顺序：左子树、右子树、关注节点

后续遍历的结果

D B E A C F 1

遍历的过程

后续遍历的递归代码

void postOrder(Node* root) { if (root == null) return; preOrder(root->left); //左子树 preOrder(root->right); //右子树 print root // 此处为伪代码，表示打印 root 节点

}

123456789

到这里你可能又会发现，三种遍历方式它们的路径都相同，只是访问节点的时机不同而已

是的，我们从三种遍历方式的代码种也可以看出，它们递归调用顺序都是一样的，只是节点的访问时间不同，所以就出现了这种情况

本篇文章到这里就结束了，适当总结一下，本文讲解的树的众多概念，讲解了什么是二叉树，什么是满二叉树，什么是完全二叉树，二叉树的存储方式，二叉树的三种遍历方式，详细剖析了前序遍历的过程

</div>