数据结构：二叉树

一、树型结构

1、基本概念

2、重要概念

3、树的表示形式

二、二叉树

1、概念

2、两种特殊的二叉树

3、二叉树的性质

4、二叉树的存储

5、二叉树的遍历

二叉树的构建

（1）前序遍历

（2）中序遍历

（3）后序遍历

（4）层序遍历

6、二叉树的基本操作

一、树型结构

1、基本概念

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

（2）树有一个特殊的结点，称为根结点，根结点没有前驱结点，除根结点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、......、Tm，其中每一个集合Ti (1 <= i <=m)又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继结点。

以上面的树为例：

A为树的根结点，也为B,C,D的前驱结点。

B,C,D为A的后继结点。

而C就没有后继结点。

（3）树是递归定义的

对于树的递归定义，我们可以这样理解，A作为根结点，有B,C,D三个子树，而B,C,D又分别可以作为根结点，像B有E和F子树，D有G子树只要我们有足够的结点，就可以不断往下拓展，就像递归一样。

（4）非树

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

除了根结点外，每个结点有且仅有一个父节点

一个N个结点的树有N-1条边

2、重要概念

如上图所示：

（1）结点的度：一个结点含有子树的个数称为该结点的度；

例如A的子树有三个分别为B，C，D，因此A的度为3

（2）树的度：一棵树中，所有结点度的最大值称为树的度；

在这棵树中结点度的最大值为3，因此树的度为3

（3）叶子结点或终端结点：度为0的结点称为叶结点；

在这棵树中度为0的结点为C,E,F,G,H，这些结点都成为叶子结点

（4）双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点；

例如A是B的父结点，B是E的父结点

（5）孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点；

例如B是A的子结点，E是B的子结点

（6）根结点：一棵树中，没有双亲结点的结点；

例如A是树的根结点

（7）结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推

A在第一层，B，C，D在第二层，E，F，G，H在第三层

（8）树的高度或深度：树中结点的最大层次；

如上图树的高度为3

（9）非终端结点或分支结点：度不为0的结点；

如上图A，B，D为分支结点

注意：如果只有A一个结点。此时的A就不是分支结点

（10）兄弟结点：具有相同父结点的结点互称为兄弟结点；

B，C，D具有相同的父节点A，因此 B，C，D为兄弟结点

（11）堂兄弟结点：双亲在同一层的结点互为堂兄弟；

如上图，E，F的父节点为B，G，H的父节点为D，而B和D在同一层上，因此E，F，G，H为堂兄弟结点

（12）结点的祖先：从根到该结点所经分支上的所有结点；

例如 F的祖先是A和B

（13）子孙：以某结点为根的子树中任一结点都称为该结点的子孙。

例如E，F为B的子孙

（14）森林：由m（m>=0）棵互不相交的树组成的集合称为森林

3、树的表示形式

实际中树有很多种表示方式：双亲表示法，孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。我们这里先简单的了解其中最常用的孩子兄弟表示法。

 class Node {int value;          // 树中存储的数据 Node firstChild;    // 第⼀个孩⼦引⽤Node nextBrother;   //下一个兄弟的引用             }

二、二叉树

1、概念

一棵二叉树是结点的一个有限集合，该集合：或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。

注意：

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

二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

注意：以下这些均为二叉树

2、两种特殊的二叉树

满二叉树:一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵二叉树的层数为K，且结点总数是(2^k)-1，则它就是满二叉树。

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

而下面的这张图它跳过了五号结点的位置直接放到的6号结点的位置，导致编号不是一一对应的，这就不是完全二叉树

3、二叉树的性质

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

如下图，我们第三层的结点最多有4个：

（2）若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是(2^k)-1。(k>=0)

（3）对任何一棵二叉树,如果其叶结点个数为n0,度为2的非叶结点个数为n2,则有n0＝n2＋1

虽然这样看着非常容易的就看出来了他们的关系，但实际实际上我们是如何推导出来的呢？

首先我们知道度为0的结点数加上度为1的结点数再加上度为2的结点数，就是我们二叉树的总结点数即：n0+n1+n2 = n;

我们知道对于具有n个结点的树，他的边数为n-1；,而对于度为0的结点是没有边的，度为1的结点有一条边，度为2的结点有两条边，这样我们就可以得到一个新的式子：0*n0+1*n1+2*n2 = n-1 即：n1+2n2 +1= n

那么我们可以结合这两个式子即：n0+n1+n2 = n1+2n2+1

最后我们将这个式子进行化简即：n0=n2+1

（4）具有n个结点的完全二叉树的深度k为上取整

（5）对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i的结点有：

若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点

若2i+1<n，左孩子序号：2i+1，否则无左孩子

若2i+2<n，右孩子序号：2i+2，否则无右孩子

4、二叉树的存储

二叉树的存储结构分为：顺序存储和类似于链表的链式存储

二叉树的链式存储是通过一个一个的节点引用起来的，常见的表示方式有二叉和三叉表示方式即：

孩子表示法和孩子双亲表示法

孩子表示法

//孩⼦表⽰法class Node {int val;Node left;Node right;}

孩子双亲表示法

//孩⼦双亲表⽰法class Node {int val;Node left;Node right;Node parent;}

5、二叉树的遍历

二叉树的构建

在我们进行对于二叉树的遍历我们先来创建一个二叉树，以下图的树为例

我们先来创建一个结点，来作为二叉树的每个结点

再来简单的构建一棵树

而对于学习二叉树结构，最简单的方式就是遍历。所谓遍历是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。

（1）前序遍历

前序遍历又称先序遍历访问的顺序为：根结点--->根的左子树--->根的右子树：即：根左右

。

我们从根节点开始走，先走左子树，遇到一个结点打印一个结点，当我们的左子树为空时我们返回null，回到此时子树的根结点，然后再往右子树走，走到空返回，这样不断的递归就得到了我们的先序遍历的结果：ABDEHCFG

代码演示：

，

（2）中序遍历

中序遍历访问的顺序为：根的左子树--->根结点--->根的右子树：即：左根右。

我们先从根结点进入，走根的左子树，当此时根的左子树为空时，返回到此时的根结点，并打印此时的根节点，然后走此时根的右子树，不为空，在走新的左子树和右子树，为空就返回null，在这样的不断递归下就得到了我们的中序遍历结果：DBEHAFCG

（3）后序遍历

后序遍历访问的顺序为：根的左子树--->根的右子树--->根结点：即：左右根。

我们还是先从根结点进入，先走左子树，如果左子树为空了再走右子树，当右子树也为空的，我们就走完了此时根结点的左右子树，在打印我们此时的根结点，这样就得到了我们后序遍历的结果：DHEBFGCA

（4）层序遍历

层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

那么我们该怎样一层一层的按顺序得到元素实现层序遍历呢？

其实我们可以创建一个队列，我们先将我们的根节点放入队列中，如果我们此时的队列不为空，我们就将队头结点弹出并打印，同时我们也判断弹出的结点，左节点是否为空，不为空放入队列中，同理右结点也是如此。

例如：当我们弹出B时，就会把B的左右结点放入队列中，接下来我们就会弹出C，并将C的左右结点放入队列中，而这后我们要弹出的元素就是我下一层的D，在这样的方式下我们就实现了，我们的层序遍历。

图示：

代码演示：

6、二叉树的基本操作

（1）遍历思路：获取树中节点的个数

当root不为空时，nodeSize就++；

代码演示

子问题思路 ：获取树中节点的个数

我们先遍历左子树，遍历完左子树再遍历右子树，我们来看他的执行过程

代码演示

（2）遍历思路：获取叶子节点的个数

所谓叶子节点就是度为0的结点，既然是这样我们可以就可以找到左右子树为空的结点，找到就让leafSize++;

代码演示：

子问题思路：求叶子结点个数

我们还可以去找到左子树的叶子结点再加上右子树的叶子结点，加在一起就是我们的总共的叶子结点，这个方式和我们上面的过程差不多大家可以对照以下。

（3）获取第 K 层节点的个数

我们的要获得第K层的结点数，首先我们要先找到我的第K层，既然是这样我们可以从第一层即根结点处往下走，每走一层就让K--，当K等于1时，就代表我们此时就在我们的第K层，而我们的第K层结点数，就是此层的左右结点数。

代码演示

（4）获取二叉树的高度

对于二叉树的高度，其实就是让我们求出左子树的右子树的最大值，然后加上1（我们的根结点）

代码演示

（5）检测值为 value 的元素是否存在

查找元素是否存在，其实只要我们遍历二叉树即可，我们先遍历左子树查找，左子树没找到再上右子树找

（6）判断一棵树是不是完全二叉树

什么是完全二叉树，再上面我们已经进行了解，其实简单来说就是我们要按照正确的顺序进行存放，不能够跳着存放。而刚才我们学习了层序遍历，我们发现他的遍历顺序其实和我们完全二叉树的顺序是一样的，那么我们就可以利用层序遍历来判断是否为完全二叉树。

（大家可以先去预习以下，上面的层序遍历。）

首先我们还是依照层序遍历，而这时在我们弹出队头元素后我们判断弹出的元素是否为空，

如果不为空，就将弹出元素的左右结点放入队列中（在这里我们发现，我们没有限制左右结点为不为空，这时就代表我们的null也可以放入队列中），

如果为空了，就代表我们要结束循环，因为对于一个完全二叉树，利用层序遍历的方式去得到，如果我们此时得到的是null，就代表我们完全二叉树已经走完了，此时我们队列中的元素应该都为null,如果此时我们遍历我们的队列，发现此时队列中，有不为空的元素，就代表这棵树不是完全二叉树。

完全二叉树