数据结构——原来二叉树可以这么学？（1：二叉树的概念）

前言：

小编在之前写过了蛮多的数据结构，本来可以在很早之前我就可以写完这一篇文章的，但是小编之前也说过，我在暑假过于放纵自己，导致托更了很久，我也是很多天没有在接触数据结构了，对于数据结构树的知识也忘记了蛮多，小编在近日重新复习了许多，为了防止忘记知识点，特此形成一篇博客，那么废话不多说，开始我们今天的代码之旅~

正文：

1.树

1.1.树的概念和结构

前面我们在学习数据结构的时候我们学过线性表，线性表又包括顺序表，链表等等，今天我们将要学习一个非线性表——树！树是一种非线性的数据结构，它是由n个有限结点组成一个具有层次关系的集合，把它叫做树是因为它看起来是一个倒挂着的树，也就是说它的根朝上，叶朝下，下面小编找到了一个图片来帮助各位去理解：

上面就是树的结构，其中，树是有一个特殊的结点的，它被叫做根节点，就是上图中的A，根节点是没有前驱结点的，也就是说根节点头上是没有什么东西的；当然除了根节点外，其余的结点被分成M个互不相交的集合T1，T2，T3.....其中每一个集合又是一颗结构和数类似的子树。也就是说我们可以把上面的树分成好几个子树，就比如BEF就可以组成一个子树，每一颗子树的根节点有且仅有一个前驱结点，当然可以有0个或者好几个后继，因此，树是递归定义的，这里小编先提前透露一下，以后小编讲的链式二叉树就是依靠递归来实现的，各位读者朋友一定要好好的复习一下函数递归的知识。我们学习树时候一定要正确的去认识树的结构，树形结构中，子树之间是不可以相交的，如果相交了就不是树结构了（如果存在相交那就是小编以后会讲述的图了），如下图所示：

上述情况的结构并不是今天我们要学习的树的结构，树的各子树之间是不想交的，并且除了根节点以外，每个结点有且仅有一个父节点，这同样也说明了子树之间是不会相交的，，并且有着n歌结点的树应该有n - 1条边，可能很多读者朋友会好奇为什么会这样，下面小编通过举例子的方式来帮助大家去理解小编说的这个特点：

上图小编就解释了树的结点和边的关系以及树的结构，虽然这些可能在今后的学习中不会起到很大的作用，但是我们作为初学者，多了解一点是好的。以上就是树的概念和结构，下面小编将要讲述树的相关术语，这关乎以后小编对于树的讲解，各位一定要好好听哦~ .

1.2.树的相关术语

1.父结点/双亲结点：若一个结点含有子结点，则这个结点称为其子结点的父节点；如上图，A是B的父结点；小编用自己的话给各位翻译一下，简单来说如果一个结点有上边还有一个结点与它相连，此时我们可以把上面这个与他紧密相连的节点叫做父节点，可能有很多读者朋友会存在一个误区，就以H举例，通过此知识点我们可以知道D是它的父节点，那么A算不算它的父结点？这肯定是不可能的，A和H是不紧密相连的，它们之间隔着D，所以A万万不可能是H的父节点，顶多算是爷爷结点（开个玩笑切勿当真），各位一定区分好这个误区~

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,D,E,F,G均为兄弟节点。对于兄弟结点，可以用我们的日常生活作为理解，一个父母可能会生很多个孩子（假设都是男的），这些孩子是哥哥弟弟之间的关系，简称兄弟；把此时的父母当做父节点，那他们的孩子肯定是子节点，这些子节点之间是哥哥弟弟的关系，所以他们就是兄弟结点~这个也是比较容易理解的一个概念。

8.结点的层次：从根开始定义起，根的结点所在层为第一层，根的子结点就是第二层，以此类推就可以推出来树的层次；这个概念是比较容易理解的，我们只要知道结点在第几行那么就可以知道在第几层（注意这个概念仅仅针对于结点在第几层，而不是针对于树的层次，树的层次也是有术语的，马上就说），小编就不多赘述了，继续下一个术语的讲解。

9.树的高度或深度：树中结点的最大层次；如上图，树的高度是4；这个概念也是比较好了解的，我们只要看这个树有几层，那么高度肯定就是几层，把它类比为我们生活中的楼层，也是同理的。

10.结点的祖先：从根到该结点所经分支上的所有结点，如上图：A是所有结点的祖先；其实结点的祖先就是根节点，因为树的起源就是根结点，从根结点开始进行分子树，最后形成一颗大树，所以根结点是所有结点的起源，即是所有结点的祖先。

11.路径：一条从树中任意结点出发，沿父结点-子结点连接，达到结点的序列；比如A到Q的路径就是：A-E-J-Q；H到Q的路径是H-D-A-E-J-Q；路径其实就是从一个结点到另一个结点的路程，然后把途径的每一个结点都列举出来，这其实就是路径的意思。

12.子孙：以某结点为根的子树中任意一个结点都被称为该结点的子孙。如上图：所有结点都是A的子孙；这个其实也是比较容易理解的，也是可以比作为家庭关系，一对父母的孩子也有了孩子以后，这个孩子被称为孙子，孙女，并且孙子孙女的数量可能会很多，这叫做子孙满堂，此时的儿子，孙子，孙女等等都被称之为子孙，这便是子孙的含义。

13.森林：由m（m > 0）颗不相交的树的集合被称为森林。这个记住就好，这个就和我们现实当中的森林是一个概念的。

以上就是树的一些相关术语，很多的名词和我们现实生活中是息息相关的，各位读者朋友不要去死记硬背，小编认为理解比硬背重要很多，可能过了很多天以后，死记硬背的知识点会忘记（这点小编深有体会），但是自己理解记住的虽说也可能会忘，不过自己再看一遍还是会回忆起来的，所以理解很重要！在我们讲述完树的概念以及一些术语以后，我们自然也要去学会如何去表示树，毕竟只知道知识点但是不会用代码实现出来，这个知识点也是白学的，下面废话不多说，开始讲解树的表示方法。

1.3.树的表示

从上面小编讲的树的结构就可以看出来，树的结构相比于线性表来说就复杂了很多了，想要存储起来表示就显得十分麻烦，我们不仅要保存数域（结点的值），还需要保持结点和结点之间的关系，实际上，表示树的方法有着很多种，就比如：双亲表示法，孩子表示法，孩子双亲表示法，孩子兄弟表示法等等，由于小编学的并不是很多，这里小编先简单的介绍一下其中一个比较简单的表示方法：孩子兄弟表示法。

1.3.1.孩子兄弟表示法

顾名思义，孩子兄弟表示法，就是通过结构体把孩子结点和它相邻的兄弟结点表示出来，此外也不要忘记把它的值保存下来，这便是孩子兄弟表示法，说起来这个表示方法也确实很简单，光有文字可能有很多读者朋友难以理解，所以小编通过图文的方法来帮助各位去理解：

上图就是用孩子兄弟表示法所表示出的树的结构，我们可以通过一个结点，来找到它的兄弟结点以及孩子结点，咱们就拿根结点A举例，首先结点A的子节点是B，然后由于它没有兄弟结点，所以它的兄弟结点就是空，通过A的孩子结点B，我们还可以找到B的兄弟结点以及孩子结点，从而实现我们通过一个结点来找到整个树其中一个结点的目的，现在我们图也有了，概念也弄请了，下面小编给上它结构体的代码书写方法：

struct TreeNode
{
    struct TreeNode* child; //左边开始的第一个孩子结点
    struct TreeNode* brother;  //指向其右边的下一个兄弟结点
    int data; //储存的数据
}；

以上便就是树的其中一个表示方法，但是它并不是今天我们博客的重点，通过标题各位可以知道，小编本文可不是写树的，而是写树型结构中我们常用的一种结构：二叉树，前面这么大幅度的讲树，就是为了帮助大家学习二叉树之前了解树的相关知识，而不是开头直接就讲二叉树， 让各位摸不着头脑，下面，就进入今天的主角：二叉树的学习！

2.二叉树

2.1.二叉树的概念和结构

2.1.1.二叉树的概念

二叉树是树的一个分支，由它的名字我们就可以知道，二叉树应该是每个结点只有两个分支的，至于它相关的术语和数的术语是一致的，所以其实二叉树的概念还是蛮简单的，下面小编就讲述一下二叉树的结构。在看二叉树的结构之前，小编先给各位看一下我们现实生活当中的二叉树，来方便各位读者朋友更好地方理解二叉树的结构：

2.2.2.二叉树的结构

在树型结构中，我们最常使用的就是二叉树，一颗二叉树是结点的一个集合，该集合是由一个根结点加上两颗分别称之为左子树和右子树的二叉树组成或者为空，它的结构如下图所示：

通过上面的结构图，我们可以知道二叉树具体的结构，它的后代至多可以有两个，就比如1就有2,4两个孩子结点，如果多于两个结点，那么这就不是二叉树了，而是三叉数等等。此外，我们通过这个结构图，可以看出几个明显的特点：

1.二叉树不存在度大于2的结点

2.二叉树的子树有左右之分，次序不可以颠倒，因此二叉树是有序树。因为每个子树保存的值大多都是不同的。

以上便就是二叉树的几个特点，当然二叉树的结构并不仅仅就是上图所显示的，对于任意的二叉树可以有以下几种情况复合而成：

以上便就是二叉树的基础知识点，下面小编将要讲两类比较特殊的二叉树，非常的重要，各位一定要好好理解。

2.2.特殊的二叉树

2.2.1.满二叉树

一个二叉树，如果每一个层的结点树都达到最大值，也就是二，那么这个二叉树就是一个满二叉树。也就是说，如果一个二叉树有k层，并且结点的总个数是2^k - 1，那么这个二叉树就是一个满的二叉树；下面小编给出一个满二叉树的例子：

满二叉树可以理解为这棵树是饱满的，如果它有着后代，那么它的后代个数必然就是满的，此外，满二叉树的满字就可以体现出它的特点。以上便是满二叉树的相关知识点，下面小编介绍一个类似满二叉树的特殊二叉树。

2.2.2.完全二叉树

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树引出来的。对于深度为k个的，有n个结点的二叉树，当且仅当每一个结点都和深度为K的满二叉树中编号从1到n的结点一一对应时称之为完全二叉树。值得注意的是，满二叉树是完全二叉树的一种特殊的情况，下面小编先给各位读者朋友展示一下完全二叉树的样子：

下面小编用自己的话来介绍一下完全二叉树，假设完全二叉树有k层，那么除了第k层的数据，其余层数的结点都是满的，而第k层的数据不一定是满的，但是结点必须遵从从左到右依次排列，它是有顺序的！如果第k层的数据也是满的，那么这个二叉树便就是一颗满二叉树，这边印证了满二叉树是完全二叉树的一个特殊情况~以上便就是完全二叉树的相关知识点，我们通过了解了满二叉树和完全二叉树以后，下面我们便可以去了解二叉树有关的性质。

2.3.二叉树的性质

（1）如果规定根结点的层数为1，那么一棵非空二叉树的第i层最多有2 ^ （i - 1）i个结点（根据二叉树的结构便可以知道）

（2）如果规定根结点的层数为1，则深度为h的二叉树的最大结点就是2^h - 1个结点（通过等比数列的求和公式得出）

（3）如果规定根结点的层数为1，具有n个结点的满二叉树的深度h = log（n + 1）【log以2为底，n + 1为对数，这个性质我们通过第二个性质就可以推出来】

以上就是二叉树的性质，都是通过一些数学公式推出来的，由于难度不大小编就不在详细的解释了，我们每学习一个数据结构，我们就要去了解这个数据结构的存储结构，下面小编将要讲述二叉树的两个存储结构。

2.4.二叉树的存储结构

二叉一般分为两种方式进行存储，一种是顺序结构，一种是链式结构，下面小编就分别详细的讲一讲这两种结构，当然，小编会在后几篇文章分别实现这两种结构。

2.4.1.顺序结构

顺序结构就是使用数组来进行存储的，有点类似于我们以前学过的顺序表这种结构，不过一般顺序结构仅仅适用于完全二叉树，因为完全二叉树是有顺序的，所以数组可以实现它，并且不担心浪费空间的问题，但是对于其他的普通二叉树来说，会存在浪费空间的清空，因为可能有的树仅仅只有右子树和左子树，但是此时我们需要保存左子树，才可以保存到右子树，不过此时的左子树我们不去使用它便是了，这样的话我们就存在了浪费空间的情况，可能对于系统来说这点空间九牛一毛，不过我们需要养成不浪费空间的好习惯，可能以后我们在工作的时候这个习惯会帮助到我们，下面小编通过图文来带领各位读者朋友更加直观的知道顺序结构如何储存二叉树：

通过上图我们可以更加直观的看出完全二叉树使用顺序储存的优越性以及非完全二叉树使用顺序储存的劣势，以上就是二叉树的顺序结构，可能有很多读者朋友会疑惑：那我们如何储存非完全二叉树呢？看看一眼这个小节的题目，各位读者朋友可能就一目了然了：它来了它来了，它带着链式结构走来了，链式结构就是存储非完全二叉树的一个比较好的结构，下面就进行链式结构的讲解。

2.4.2.链式结构

二叉树的链式结构是指，用链表来去表示一个二叉树，即用链式关系来表示元素之间的关系。通常的方法是链表中有三个域（也可以理解为变量），类似于上面的孩子兄弟表示法，分别是数据域以及左右指针域，左右指针分别表示左孩子以及右孩子的存储结构。链式结构又分为二叉链和三叉链，小编目前仅仅学完了二叉链，不过小编在学习过程中了解到了红黑树用到了三叉链，等小编后面学完了在讲解三叉链，就比如上面说的链式的表示方法就是二叉链的使用方法，下面小编同样通过图文的方法来带领各位读者朋友去理解链式结构是如何存储的：

3.总结

以上便就是树的相关概念以及二叉树的相关概念，小编自认为自己写的有一些不足，请各位读者朋友多多见谅，这几天的脑子比较晕，本来这一篇还想去教各位读者朋友如何去实现顺序结构，想了想篇幅还是太大了，索性小编决定下一篇就写如何实现顺序结构，各位读者朋友敬请期待，如果文章有错误，请在评论区指出，小编会定期观看评论然后做出改正。那么，我们下一篇文章见啦~