引言：

这个文章写的说实话是很没有意思的，因为根本就没有什么人看这个东西，所以这个东西说实话只是写给我们自己看的；今天是北京时间2022/12/13的下午2点57分，刚睡醒，一看微信中的消息（人快要笑死了），有的消息真的是很搞笑的，还有就是我们今天我们要开始放我们的寒假了（本来是安排说在2023年放的，现在提前了），所以大家都是非常的激动的，有的在收拾行李，有的在联系里，有的在买票，可以说是氛围确实有点过年的味道（仅此而已），亏的某些人临危不乱（还在这个地方写我这个没人看的博客（当然除了我自己）），当然这个地方我还要介绍一下我的高中同学黄某佳（一个喜欢天天自称是哥和喜欢别人叫她哥的……），此人可以说是极度的会找理由，反正我是说不过她，然后导致我明天回不了家（虽然我也不是很想回去），但是她是真的滑稽（有点像是上世纪的那个谁（卓别林），但是自然只是有了人家的搞笑，其它的也就没有了），并且我们呢，已经是好久没写博客了，快一个星期了，对于平常日更的我，这个好像是有一点的异常，但是这个是有原因的，因为我们前几天大部分的时间都用在了做题目上了（虽然并没有做几个题目，因为做题真的是一个很困难的事情），所以准确的来说我的时间应该是用来复习之前的有关数据结构的知识了，然而大部分应该还是用在了睡觉的上面，睡觉真的是一个好东西（所以这个地方别的东西先不教，我们就先教大家睡觉，睡觉真的是一个人活着最重要的事情，任何情况就没有睡觉解决不了的，不管你是开心还是难过，只要你沉下心来睡一觉，任何事情都迎刃而解，任何事情对你来说都不过是搞笑的（无所谓啦），真的），这个位置我们也就不说了，我们接下来就学习一下我们的新知识（树），参天大树的树，花草树木的树，绿树成荫的树，蚍蜉撼树的树，当然也是玉树临风的树。

一、树和二叉树的相关知识

（一、）什么是树

1.树

（1.）日常生活中的树

是这个

还是这个

亦或者是这个（不过这棵树看成好像有点像一个萝卜）

很明显这几棵树跟我们（可怜的代码人）都没有什么关系（虽然我们的校园生活也和别人的一样是“五彩缤纷“的，（谁让现在的编译器一个一个都是有颜色的），真的是头痛），所以以下就是我们的代码人眼中的树（这个东西我们也只能先学一些基础，这个东西的博大精深不可言谈，这个位置可以劝退一下了，真的，我要不是……咱就不学了，代码人的难亦是不可言谈的（特别是一个叫平衡树的东西（红黑树和AVL树就是典型的代表哦！）））

（2.）树的基本概念（非线性结构）

树是一个非线性的数据结构，它是由n个有限结点组成一个具有层次关系的几个，把它叫做树是因为它看起来像是一颗倒挂的树，也就是说它是根朝上，而叶朝下的

• 并且它有一个特殊的结点，称为根结点，根结点没有前驱结点

• 除了根结点外，其余结点被分为M个互不相交的集合 T1、T2、T3……、Tm ，其中每一个集合Ti（1<=i<=m）又是一颗与树类似的子树，每颗子树的根结点有且只有一个前驱，可以有0个或多个后继

• 因此树是递归定义的

• 并且此时根据自我了解，此时的树的每一个枝干就有一点像是一个链表（是由一个一个的结点构成的）

（3.）代码人眼中的树：（当然这个是一个倒过来的树）

在计算器科学中，树是一种抽象数据类型或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。是一种非线性的数据结构，由n（n >=0）个结点组成的有限集合。

图片如下：

没错，就是这样的！一眼就可以看出来，有根、主干和叶子，组成就这样简单（只不过是倒过来了）

根：A

主干：B C D E

叶子：F G

所以按照以上的图片的结构，我们可以看出什么是树，并且我们可以得出一下的结论：

看得出来，每个节点都是和另一个节点有关系的。A->B C B->D C->E F

（4.）树组成的名称代表的都是什么意思：

根结点：每一个非空树都有且只有一个被称为根的结点。例如A为本颗树的根节点。

结点：使用树结构存储的每一个数据元素，例如元素A和B都代表一个节点。

叶子结点：该节点下没有任何子节点。例如 D、F、G等称为叶子节点。

树度：对于一个结点，拥有的子树数（结点有多少分支）。叶子节点的度为1。例如G的度为1，D的度是2,B C 的度是3 , A的度是4

子树：我们从节点上来看，B、C、D也是一颗树，B、C、D作为各自树的根节点，这种树我们理解为子树。讲白了，每个节点都是一棵树，它自己就是根节点。

空树：没有结点的树。

森林：由n个子树构成的集合。

（5.）树的结构

此时的树的结构的实现是有好几种的，但是我们现在不需要太关心

并且目前树的使用就是在于文件的目录的使用（树不是二叉树这个点要分清哦）（二叉树就是表示的是一个结点最后只能有两个孩子，不能像是树一样有好多个孩子）

并且此时的二叉树就只有两个孩子的树，所以普通的树在数据结构中此时并不适合存放数据，所以强调一下我们的普通的树只是比较适用来实现像我们磁盘中的文件的存储的目录的使用

（6.）树的类型（博大精深，头很痛）

6.1.二叉树：每个节点最多含有两个子树的树称为二叉树；

6.2.完全二叉树：对于一颗二叉树，假设其深度为d（d>1）。除了第d层外，其它各层的节点数目均已

达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树；

6.3.满二叉树：所有叶节点都在最底层的完全二叉树；

6.4.平衡二叉树（AVL树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树；

6.5.红黑树: 是一种自平衡二叉查找树，它是在1972年由鲁道夫·贝尔发明的，他称之为”对称二叉B树”

6.6.排序二叉树(二叉查找树)：也称二叉搜索树、有序二叉树；

6.7.霍夫曼树（哈夫曼树）：带权路径最短的二叉树称为哈夫曼树或最优二叉树；

6.8.B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多于两个子树

（7.）以上就是对树的一系列的了解，下面我们来介绍一下树中的经典（二叉树）

（二、）什么是二叉树

图片如下：

此时就非常的搞笑了，当一个普通人看见这个树，心想不就是一个普通的树吗？而当一个代码人看到这个树……，所以接下来就让我们了解一下什么是我们眼中的二叉树

（1.）首先我们可以把二叉树分为三个部分：

1.根结点 2.左子树 3.右子树（用于前序中序后序的实现和理解）

并且我们在实现我们的二叉树的时候我们使用的是一个叫分治算法的算法：分而治之，将一个大问题分成类似的子问题，子问题再分成类似的子问题……，直到子问题不能再被分割（也就是当这个结点为叶结点，也就是此结点指向的是一个空的时候）

所以接下来我们了解一下什么是

（2.）二叉树的前中后序

2.1.前序（先根）：先访问 根 然后左子树 再然后右子树 但是要注意的是这个位置是要一直访问到左子树的底才可以进行右子树的访问，只要左子树还有数据就一直都要访问左子树，直到左子树不可分割来了才行

2.2.中序（中根）：左子树 根 右子树 （这三种前序中序后序的访问方法就有好几种的访问方法，此时就是可以有三种不同的遍历的方法了）

2.3.后序（后序）：左子树 右子树 根

所以此时我们一定要把这个前中后序了解熟练，才可能把以后的有关二叉树的知识学会

2.4 接下来我们就拿一棵典型的树来了解一下这个前中后序：

树来：

虽然这个不是二叉树，但是也并不影响我们来了解什么是前中后序

（3.）特殊的二叉树

这个位置介绍的东西虽然上面有部分讲到，但是我们再详细专门针对二叉树来详细介绍一下

2.5.1.满二叉树

一个二叉树，如果每一个层的结点的数都达到最大值，则这个二叉树就是满二叉树，也就是说，如果一个二叉树的层数是h，且结点总数是（2^h）-1，则称这个数是一个满二叉树

2^0+

2^1+

2^2 +

2^3+

2^4+

……+

2^(h-1) = N(总结点的个数)

此时的这个表达式按照一个等比数列的求和就可以得到此时的结点个数就是（2^h）-1

并且此时的h（二叉树的高度（层数）此时也是可以利用这个原理直接求得的）：

h=log以2为底N的对数+1 此时有了这个公式，我们就可以在只知道某一个二叉树总结点个数的情况下得到任意某棵二叉树的高度

如图：

2.5.2.完全二叉树

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

假设此时完全二叉树的高度是h

1.前h-1层都是满的

2.最后一层不满，但是最后一层从左往右都是连续的（连续的必须是左右左右一直连续）

3.所以此时的完全二叉树的总结点的个数的算法就跟我的满二叉树是有所不同的

完全二叉树的总结点的个数的算法：2^h-1-x=N （此时的x代表的就是最后一层中缺少的结点的个数而已）并且此时的x的最大值就是（2的h次方-1）

完全二叉树的高度的计算为：h=log以2位底N的对数+1+x

4.完全二叉树的性质：

如果完全二叉树有n个结点，那么树最高为log2(n)+1 对于完全二叉树，从上至下，从左至右对每个结点从1-n编号，那么对于结点n有：

如果i=1，那么此结点为根结点，如果i>1那么该结点的父结点为不大于i/2的最大整数

如果2i>n，那么i结点没有左子树，如果2i<=n那么该结点的左子树编号为2i

如果2i+1>n，那么结点i没有右子树，如果2i+1<=n那么该结点的右子树编号为2i+1

（4.）搜索二叉树

什么是搜索二叉树呢？如图：

4.1 这个就是一个非常典型的搜索二叉树，通过这个图例，此时我们就可以得出搜索二叉树的特点

特点：任何一棵树，左子树都比根要小，右子树都比根要大，此时我们根据这个特征就可以很好的得到每一个数据的搜索和每一个数据的位置，并且当我们想要从这棵搜索二叉树总找到某一个数据的时候就可以进行一个一个的比较，然后就可以很轻松的找到这棵树中是否有这个数据（所以很适合搜索，并且最大的搜索次数就是这棵树的高度次），所以在现实中，二叉树的作用最多就是用来搜索

4.2 但是此时的这个搜索二叉树还是有一定的缺点的，比如下图所示：

这个图片中的示例就是为了告诉我们搜索二叉树的一定的缺点：当一个根结点的某一个子节点（左节点或者右节点）相较于另一个子结点过于的长的时候，此时的搜索效率就不大幅度的下降，就有可能会达到N次，所以此时我们针对于搜索二叉树的缺陷我们研究出了搜索效率更加高的二叉树（平衡二叉树），亦或者说是：红黑树，AVL树（就是使我们左右两边的结点数据比较的均匀分布），还是那句话遇到这个东西的时候，就是劝退的时候，因为这个东西是非常的博大进深的，所以我们一定要做好准备，迎接挑战，这个东西就是属于很复杂的数据结构（当然这个位置还有一个B数，虽然不是二叉树，但是也是一个搜索树，这个东西是与我的数据库有关的一个数据存储方式）

4.3 所以今天我们学习的这个二叉树本质上是没什么太大的用处的

但是可以为我们后面学习有关平衡树做铺垫，并且从考试的角度来说，很多的题都是出在普通的二叉树上的，所以也是意义重大的（还是那句话，你学的东西是不会少的，该你学的你跑不掉）

4.4.所以我们今天只是进行树的普通的理解，想要深入学习每一个树其实都是很复杂的，所以……

（5.）二叉树的性质

所以上面讲了这么多，我们也不要焦虑，我们要一步一步慢慢走，所以下面我们再深度了解一下什么是二叉树的性质：

（5.1）

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

2.若规定根结点层数为1，则深度为h的二叉树的最大结点数是2^h-1

3.对任何一棵二叉树，如果度为0其叶结点个数为n0，度为2的分支结点个数为n2，则有n0=n2+1

4.若规定根结点的层数为1，具有n个结点的满二叉树的深度，h=log以2为底N的对数+1

此时的第三点中的n0=n2+1是一个推导过程，具体的过程如下：

k: 总度数

k+1: 总结点数

n0: 度为0的结点

n1: 度为1的结点(只有一个孩子的结点)

n2: 度为2的结点(有左右两个孩子)

k=2n2+n1

k+1=n0+n1+n2

推出n0=n2+1

（5.2）

并且此时我们也对如何理解这个度的概念进行一个总结：

度：二叉树的度是指树中所以结点的度数的最大值。二叉树的度小于等于2，因为二叉树的定义要求二叉树中任意结点的度数（结点的分支数）小于等于2 ，所以在二叉树中二叉树是树形结构中一种特殊的树形结构：二叉树中的每个结点至多有2棵子树（即每个结点的度小于等于2），所以这个就是二叉树中的度 所以总的来说度就是一个根结点的分支的数量，假如一个根结点有两个结点，那么此时它的度就是为2（最大也是2），如果一个结点无分结点，那么此时它的度就是0,

（6.）与二叉树性质有关的题目讲解

所以此时我们就要牢牢的掌握这个公式n0=n2+1，因为这个公式与我们有的题目是有关的，例如以下题目：

1.某二叉树共有400个结点，其中有200个结点的度为2的结点，则该二叉树的叶结点数为（D）；

A.不存在此二叉树

B.200

C.198

D.201

2.在具有2n个结点的完全二叉树中，叶结点个数为（A）；

A.n

B.n+1

C.n-1

D.n/2

3.一棵完全二叉树的结点数为531个，那么这棵树的高度为（B）；

A.11

B.10

C.8

D.12

（5.4）以上的题目讲解

1.首先第一题就是套用上述的那个公式，不必多说

2.第二题相较第一题就相对有点难度了，（解题点在于要知道完全二叉树的概念和一棵二叉树的各个度的结点的个数），比如：

假设度为0的有x0个

假设度为1的有x1个

假设度为2的有x2个

此时根据题意就可以得到：2n=x0+x1+x2 （以为一个二叉树就是通过度为0 1 2 的结点构成的）

并且此时根据我的公式 x0=x2+1 带到上述方程式中得到 ：2x0+x1-1=2n

所以根据我们的未知数原则，此时我们需要再替换掉一个未知数x1

并且此时根据我的完全二叉树的原则可以得到，x1可能是1，也可能是0，因为x1代表的是度为1的结点，而在一棵二叉树中度为1的结点只有在最后一行可以找到，并且因为这个树是完全二叉树和总结点的个数是2n一个偶数，所以此时最后一行必须是只有一个单独的度为1的根结点（因为整棵二叉树的根结点为1，其它的根结点都是成双的，所以最后一行的度为0的结点为1,才可以和二叉树的第一行的根结点匹配成偶数，所以此时的x1是一个奇数，所以是1），所以得到2x0+1-1=2n，所以最终得到 x0=n；

3.第三题的意思就是要了解完全二叉树的同时要按照性质知道最后一层缺少的个数的范围

假设此时的树的高度是h，最后一层缺少了x个

此时就可以得到：2^h-1-x = 531

并且通过对完全二叉树的理解 此时的x的范围就是 [0,2^(h-1)-1]

然后此时我们通过将选项中的答案带入到表达式中，自然而然可以得到只有我的B答案是合理的

（三、）以上就是关于树和二叉树的基础知识了

文字走起，基础了解，下一遍博客我们就要进行二叉树的实现啦（头痛），撤退