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

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

节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6
叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I...等节点为叶节点
非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G...等节点为分支节点
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点
兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点
树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层次； 如上图：树的高度为4
堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点
节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
森林：由m（m>0）棵互不相交的树的集合称为森林；

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既要保存值域，也要保存结点和结点之间
的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法
等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

 树在实际中的运用（表示文件系统的目录树结构）

一棵二叉树是结点的一个有限集合，该集合:
2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

 从上图可以看出：
1. 二叉树不存在度大于2的结点

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

注意：对于任意的二叉树都是由以下几种情况复合而成的：

 现实中的二叉树：

 特殊的二叉树：

1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是
说，如果一个二叉树的层数为K，且结点总数是 ，则它就是满二叉树。
2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K
的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对
应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有 个结点.
2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是 .
3. 对任何一棵二叉树, 如果度为0其叶结点个数为 , 度为2的分支结点个数为 ,则有N0 ＝N2 ＋1
5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对
1. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空
间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们后面的章节会专门讲解。二叉树顺
序存储在物理上是一个数组，在逻辑上是一颗二叉树。

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是
链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所
在的链结点的存储地址 。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面课程
学到高阶数据结构如红黑树等会用到三叉链.

二叉树的顺序结构及实现

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结
构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统
虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

 二叉树链式结构的实现

2. 非空：根节点，根节点的左子树、根节点的右子树组成的

 从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。

前序、中序以及后序遍历
学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉
树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历
是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：
1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历

 前序遍历递归图解：

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

 节点个数以及高度等

二叉树叶子节点个数 

// 二叉树叶子节点个数
 

 


 

 


 

// 二叉树第k层节点个数
 

  二叉树查找值为x的节点
 


 

// 二叉树查找值为x的节点
 

// 判断二叉树是否是完全二叉树
 

 
 

 
 

 判断二叉树是否是完全二叉树
 
 

//判断二叉树是否是完全二叉树
 // 遇到空了以后，检查队列中剩下的节点
// 1、剩下全是空给，则是完全二叉树
// 2、剩下存在非空，则不是完全二叉树

一棵二叉树是结点的一个有限集合，该集合:

2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

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

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

3. 对任何一棵二叉树, 如果度为 0 其叶结点个数为 n0 , 度为 2 的分支结点个数为n2  ,

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

二叉树我们是用链表实现的，下面是结构：

我们可以看到一个节点中有三个变量，一个存放数据，一个指向左子树，一个指向右子树。将char类型重命名是为了后面更方便的更改类型，将结构体重命名为BTNode是为了更简单的写出指针类型。 

下面是实现的完整代码，然后我们依次进行讲解，在下面我们可以看到队列，这是因为二叉树的层序遍历和完全二叉树的判断用队列非常方便。

 先看第一个：二叉树遍历

1.前序遍历：先遍历根 然后是左子树 然后是右子树

如图所示，在递归的过程中，第一个节点为1，1不为空打印1然后递归1的左子树，1的左子树为2，不为空打印2，然后递归2的左子树，2的左子树为空打印NULL然后返回刚刚2的那个函数，2的左子树已经递归了所以该2的右子树，2的右子树为空打印NULL然后返回2的函数，2的函数执行完了返回1的函数，这时候1的左子树递归完成了，现在递归1的右子树，这里与1的左子树递归出来是一样的，然后成功用前序遍历出这棵树。后面的中序遍历就是先去遍历左子树不打印，然后左子树遍历完了在打印节点然后再去遍历右子树。

2.中序遍历：先遍历左子树，然后遍历根，再遍历右子树

 与前序相同就不再讲述。

3.后序遍历：先遍历左子树，然后遍历右子树，最后遍历根节点。

 第二个：求二叉树的节点数

 求二叉树的节点很简单，当这个节点为空时就返回0否则就返回这个节点的左子树的节点加右子树的节点再加自己。单靠代码可能不好看出来，那么我们画个图看看。

相信大家也看懂这个图了，本质就是计算一个节点的左子树的节点+右子树的节点再加自己。

第三个：求二叉树的叶子节点数

叶子节点我们在上篇已经讲过，就是度为0的节点。我们从这个角度出发，度为0就是左子树为空并且右子树为空，所以只需要将上面的代码稍微修改即可。

 在这里一定要注意，当树为空要返回0否则就是死递归。下面是递归图：

 我们可以看到求叶子节点的递归非常简单，只需要记得当树为空返回0，如果没有这个条件当一棵树或者一个节点只有左边没有右边时就会死递归。

 求树的高度只需要看一棵树中它的左子树高还是右子树高，我们返回高的那个然后再加上根的一层就是总高度，当一样高时随便返回一颗子树的高度即可。在这里需要注意的是一定要用两个值去分别记录左右子树的高度，否则效率非常差每一层递归都要重新计算高度。

如递归图所示当有变量记录其左右高度时会比直接递归快很多。

第五个：求第K层节点数

怎么求第K层节点数呢？我们发现当我们要求一棵树的第三层时，从根节点的角度看是第三层，从第二层的角度看是第二层，从第三层的角度看是第一层，也就是说每次都可以转化为这个节点的左子树的K-1层的节点+这个节点的右子树的K-1层节点，当K=1也就是自己就是第一层时那么只有自己一个节点，所以返回1即可。

第六个：二叉树查找值为x的节点

 查找值为x的节点我们要考虑几个问题，第一个是如果找到了这个节点能否直接返回，第二个是当找不到的时候要返回空指针，当这个节点为空时也要返回空指针，我们在递归的过程中一定要保证每一个都有返回值。在这里当我们找到这个节点时为什么要用变量保存呢？因为当我们找到这个节点后我们应该要函数直接返回而不是继续去递归它的左右子树。

通过递归图我们可以看到每次找到节点后返回这个节点必须要有变量去保存这个节点，否则就白找了，并且通过判断变量是否为空的情况就可以知道有没有找到，当任意一个变量不为空时直接返回了找到的这个节点就不会去递归其他的节点。 

这个其实是牛客网的一道题，就是通过前序遍历来让一个字符串被二叉树存储。

 如图当遇到字符#时，就是空指针，str是传来的字符串，i是记录字符串位置的下标，在这里一定要注意此函数要传下标的地址，因为我们在递归的过程中i会++如果不是传地址的话每次递归后的i++后对上一次函数栈帧不起作用，我们通过递归图来演示。

如图所示当走完全部字符串后返回二叉树的根节点，这样就创建好了一颗二叉树。在这里要注意的是不管遇到空指针还是正常字符都需要让下标I++。在这里我们开辟的空间到最后结束程序都要记得销毁。

 销毁二叉树同样需要递归来实现，我们只需要先找到左子树最后一个节点然后依次销毁即可。在这里需要注意的是当这个节点为空时，一定要返回。

第九个：二叉树的层序遍历

层序遍历我们是用队列实现的，先将根节点入队列，每次出队头元素前都需要将这个节点的左右子树入队列。当队列为空说明所有节点都遍历完了，直接销毁队列即可。

 当然每次入队列我们是不会入空树的因为层序遍历就是每层从左到右根的遍历。每次用一个变量去保存队列头元素，这样方便出队列和入队列。入节点的子树的时候每次左右子树不为空再入队列。在这里要说明一下，队列里保存的是二叉树结构体的指针而不是节点，如果保存的是节点就会出错。如下面代码要保存树的节点的地址。

第十个：判断是不是完全二叉树

完全二叉树可以在最后一个节点只有左子树，但一定不会在已经有空树的后面还有节点如下图所示：

如图所示，非完全二叉树有空节点后后面还会有节点，而完全二叉树在某一个节点为空时它的右边全是空节点，依据这个特性我们就很容易的判断一棵树是否为完全二叉树。

我们继续用队列实现，这次空节点也要入队列，当队列的头变成空节点时我们出队列并且退出循环，当队列不为空时我们继续拿队头元素，一旦这个元素不是空节点就说明不是完全二叉树，当队列全部出完也没有遇到非空的节点时，那么就说明这棵树为完全二叉树。

二叉树最重要的就是递归，要深刻的理解递归过程就必须要多画图，只要理解了递归那么再去写二叉树就手到擒来了。