一、树的概念和结构
1.1树的概念
树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合(n=0 时称为空树)。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
- 有一个特殊的结点，称为根结点，根节点没有前驱结点。
- 除根节点外，其余结点被分成几个互不相交的集合，每个集合又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。
- 因此，树是递归定义的。
如下图，A为整个树的根节点。而B，C，D可以看做子树的根节点，在下面分别长出三棵子树。
1.2树的逻辑结构
树的逻辑结构表示有：树状表示法，文氏图表示法，凹入表示法和括号表示法。
1.2.1树状表示法
树是最基本的逻辑结构表示法，使用一棵树倒置表示，非常直观。
1.2.2文氏图标表示法
使用集合以及集合包含关系描述树结构。
1.2.3凹入表示法
使用线段的伸缩的关系描述树结构。
1.2.4括号表示法
将树的根结点写在括号的左边，除根结点之外的其余结点写在括号中，并用逗号分隔。
1.3 树的一些专业术语
节点：树的数据元素。
叶节点和终端节点：度为零的节点(除根节点外，分支节点也称为内部节点)。
终端节点或分支节点：度不为0的节点。
双亲结点或父节点：上层的那个节点，也是直接的前驱。如图，C为G的父节点。
孩子节点或子节点：下层的节点的子树，也是直接后继。如图，G为C的子节点。
兄弟节点：拥有相同父节点(同一双亲下的同一层)的节点称为兄弟节点。
堂兄弟节点：双亲位于同一层的节点，但是并非同一个双亲。
节点的度：一个节点含有的子节点的个数称为该节点的度，有几个直接的后继就是几个度 ，也称为次数。
树的度：一棵树中最大的节点的度称为树的度。
树的高度或深度：树中节点的最大层次，如图，高度为4。
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推。
祖先：从跟到该节点所经分支上的所有节点。A是所有节点的祖先。
子孙：该节点下层子树中的任意一个节点。
森林：由m（m>0）棵互不相交的树的集合称为森林。
有序树：节点各个子树从左到右有顺序关系，也称为自由树，不能互换。
无序树：与有序树相反，可以互换的。
二叉树：每个节点最多含有两个子树的树称为二叉树。
完全二叉树：叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。
1.4树的性质
性质一：树中结点数等于所有结点的度数加一
根据树的定义,在一棵树中,除根结点以外,每个结点有且仅有一个直接前驱,也就是说,每个结点与指向它的 一个分支一一对应,所以,除根结点以外的结点数等于所有结点的分支数(即度数),而根结点无直接前驱,因此,还要加一。
性质二：度为m的树中第i层上至多有m的（i-1）次方个结点（(m^i-1)i大于等于1）
性质三：高度为h的m次树至多有（m^h）-1除以（m-1）1.5树的表示法
利用顺序存储和链式存储的特点，完全可以实现对树的存储结构的表示。介绍三种不同的表示法：双亲表示法、孩子表示法、孩子兄弟表示法。
1.5.1双亲表示法
我们假设以一段连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。也就是说，每个结点除了直到自己是谁外，还要直到自己的双亲在哪里。就像
| data | parent |
|---|
其中data就是数据域，存储结点的信息。而parent是指针域，存储该结点的双亲在数组中的下标。
双亲表示法的结点结构定义代码：
//树的双亲表示法结点结构定义
#define MAX_TREE_SIZE 100
typedef int TElemType; //树结点的数据类型，目前暂定整形
typedef struct PTNode{ //结点结构
TElemType data; //结点数据域
int parent; //双亲位置
}PTNode;
typedef struct{ //树结构
PTNode nodes[MAX_TREE_SIZE]; //结点数组
int r,n; //根节点的位置和结点数
}有了这样的结构定义，我们就可以实现双亲定义法了。由于跟结点没有双亲，所以我们约定根结点的位置域设置为-1，这就意味着，我们所有结点都直到他双亲的位置。如图为树结构和双亲表示法的图表。
我们可以通过上面快速的找到结点的双亲。但是我们要知道结点的孩子只有遍历整个结构了。
1.5.2孩子表示法
换一种完全不同的想法。由于树中每个结点可能有很多的子树，可以考虑用多重链表，即每一个结点有多个指针域，其中每个指针指向一个子树的根节点，我们把这种方法叫做多重链表表示法。不过，树的每个结点的度，也就是它孩子个数是不同的。所以可以设计两种方案来解决。
- 方案一
指针域的个数等于树的度。
如图，data就是数据域，child1····是指针域，用来指向该结点的孩子结点。
以1.5.1中的树结构为例来实现。
我们可以看到。^这个符号就是代表当前这个指针域并没有用到。这样如果树的各结点的度差距过大的话，显然非常浪费空间。按需分配空间显然更好，这样就有第二种方案了。
- 方案二
每个结点指针域的个数等于该结点的度，我们专门来取一个位置来存储结点指针域的个数。如图。
如图，data就是数据域。degree是度域，也就是存在该结点的孩子结点数。child1····是指针域，用来指向该结点的孩子结点。
那么对应的树图就应该是这样。
显然，方案二克服了浪费空间的缺点，但是由于各个结点的链表结构是不相同的，在加上要维护结点的度的数值，在运算上显然有损耗。
能否有更好的方法？既可以减少浪费，又能使结点结构相同。
我们把每一个结点放入顺序存储结构中是合理的，但是每个结点的孩子多少是不确定的，所以我们再对每个结点的孩子建立一个单链表来体现他们的关系。这就是我们的孩子表示法。
具体办法：把每个结点的孩子排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针有组成一个线性表，采用顺序存储结构，存进一个一维数组。如图。
为此，设计两种结构，一个是孩子链表的孩子结点。
child是数据域，存储某个结点在表头数组中的下标。next是指针域，用来存储某结点的下一孩子结点的指针。
另一个是表头数组的表头结点。
data是数据域，存储某结点的数据信息。firstchild是头指针域，存储该节点的孩子链表的头指针。
以下是孩子表示法的结构定义代码。
//树的孩子表示法结点结构定义
#define MAX_TREE_SIZE 100
typedef int TElemType; //树结点的数据类型，目前暂定整形
typedef struct CTNode{ //孩子结点
int child;
struct CTNode * next;
}*ChildPtr;
typedef struct{ //表头结构
TElemType data;
ChildPtr firstchild;
}CTBox;
typedef struct{ //树结构
CTBox nodes[MAX_TREE_SIZE]; //结点数组
int r,n; //根节点的位置和结点数
}我们可以改进一下。把双亲表示法和孩子表示法综合一下，加一个双亲域。如图。（双亲孩子表示法）
1.5.3孩子兄弟表示法
任何一棵树，它的结点的第一个孩子如果是唯一的，它的右兄弟如果存在也是唯一的，因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。
结点结构如图。
data是数据域，firstchild为指针域，存储第一个孩子结点的地址，rightsib是指针域，存储该结点的右兄弟的地址。
结构定义代码如下.
//树的孩子兄弟表示法结构定义
typedef struct CSNode{
TElemType data;
struct CSNode *firstchild，*rightsib；
}CSNode，*CSTree;仍然以1.5.1的树为例，这种方法实现的示意图如图。
这种方法给查找某结点的某个孩子带来了方便，只需要通过firstchild 找到此结点的左儿子，然后再通过左儿子找到二弟，一直下去，知道找到具体的孩子。当然，如果想要找到双亲，完全可以增加一个parent 指针域来解决。
二、二叉树概念及结构
2.1二叉树的概念
一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
二叉树的特点：
1、每个节点最多有两棵子树，即不存在超过度大于2的结点。
2、二叉树的子树有左右之分，次序不能任意颠倒。
3、树中某结点只有一棵子树，也要区分它是左子树还是右子树。
现实中的二叉树：
2.2几种特殊的二叉树
2.2.1二叉排序树
二叉排序树，又称二叉查找树、二叉搜索树、B树。
二叉排序树是具有下列性质的二叉树：
- 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
- 左、右子树也分别为二叉排序树。
也就是说，二叉排序树中，左子树都比节点小，右子树都比节点大，递归定义。
重要结论： 根据二叉排序树这个特点我们可以知道，二叉排序树的中序遍历一定是从小到大的。
根据二叉排序树的定义，我们可以知道在查找某个元素时：
先比较它与根节点，相等就返回；或者根节点为空，说明树为空，也返回；
如果它比根节点小，就从根的左子树里进行递归查找；
如果它比根节点大，就从根的右子树里进行递归查找。
这就是一个简单的二分查找。只不过和二分查找还是有些不同的地方的。
2.2.2平衡二叉树
平衡二叉树，又称AVL树，用于解决二叉排序树高度不确定的情况，如果二叉排序树的子树间的高度相差太大，就会让二叉排序树操作的时间复杂度升级为O(n)，为了避免这一情况，为最坏的情况做准备，就出现了平衡二叉树，使树的高度尽可能的小，其本质还是一棵二叉搜索树。
平衡二叉树的性质：
- 左子树和右子树的高度之差的绝对值小于等于1
- 左子树和右子树也是平衡二叉树
为了方便起见，给树上的每个结点附加一个数字，给出该结点左子树与右子树的高度差，这个数字称为结点的平衡因子（BF），平衡因子=结点左子树的高度-结点右子树的高度。
因此平衡二叉树所有结点的平衡因子只能是-1、0、1,例如：
2.2.3B树类型
2.2.3.1B树（B-树、B_树）
一种平衡的多叉树，称为B树（或B-树、B_树，B：balanced说明B树和平衡树有关系）。
一棵m阶B树是一棵平衡的m路搜索树，它或者是空树，或者是满足下列性质的树：
1.树中每个结点至多有m棵子树。(即至多含有m-1个关键字，两颗子树指针夹着一个关键字)；
2.若根结点不是终端结点，则至少有两颗子树。(至少一个关键字)；
3.除根结点外的所有非叶子结点至少有[m/2]棵子树。(即至少含有[m/2]-1个关键字)；
4.所有的叶子结点出现在同一个层次上，不带信息。(就像是折半查找判断树中查找失败的结点)。
5.每一个结点中的关键字满足从左到右依次增大的规则。简单理解为：平衡多路查找树为B树（每一个子节点上都是有数据的），叶子节点之间无指针相邻，它的出现就是为了减少磁盘IO操作，思想是降低树的高度，从==“瘦高”–>“矮胖”==。
B树的搜索，从根结点开始，如果查询的关键字与结点的关键字相等，那么就命中；否则，如果查询关键字比结点关键字小，就进入左儿子；如果比结点关键字大，就进入右儿子；如果左儿子或右儿子的指针为空，则报告找不到相应的关键字；重复，直到所对应的儿子指针为空，或已经是叶子结点
如果B树的所有非叶子结点的左右子树的结点数目均保持差不多（平衡），那么B树的搜索性能逼近二分查找；但它比连续内存空间的二分查找的优点是，改变B树结构（插入与删除结点）不需要移动大段的内存数据，甚至通常是常数开销；但B树在经过多次插入与删除后，有可能导致不同的结构。
B-树的特性：
1. 关键字集合分布在整颗树中；
2. 任何一个关键字出现且只出现在一个结点中；
3. 搜索有可能在非叶子结点结束；
4. 其搜索性能等价于在关键字全集内做一次二分查找；
5. 自动层次控制；
优点：由于m阶B树每个结点最少m/2个结点的限制，是为了最大限度的减少查找路径的长度，提供查找效率
缺点：不便于范围查询2.2.3.2B+树
B+树是B树的一种变形形式，B+树上的叶子结点存储关键字以及相应记录的地址，叶子结点以上各层作为索引使用，数据对象的插入和删除仅在叶子节点上进行。
一个m阶的B+树具有如下几个特征:
1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来保存数据的索引，所有数据都保存在叶子节点。
2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。通常用于数据库和操作系统的文件系统中。B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。
它比 B 树的查询性能更高。
从图片可以看出，叶子结点用指针连在一起，每一个父节点的元素都出现在子节点中，是子节点的最大（或最小)元素。
在上面这棵树中，根节点元素8是子节点2,5,8的最大元素，也是叶子节点6,8的最大元素。
需要注意的是，根节点的最大元素（这里是15)，也就等同于整个B+树的最大元素。以后无论插入删除多少元素，始终要保持最大元素在根节点当中。
至于叶子节点，由于父节点的元素都出现在子节点，因此所有叶子节点包含了全量元素信息。并且每一个叶子节点都带有指向下一个节点的指针，形成了一个有序链表。
总结：
B+树的三个特点：
1.关键字数和子树相同
2.非叶子节点仅用作索引，它的关键字和子节点有重复元素
3.叶子节点用指针连在一起
第一点，在 B 树中，节点的关键字用于在查询时确定查询区间，因此关键字数比子树数少一；而在 B+ 树中，节点的关键字代表子树的最大值，因此关键字数等于子树数。
第二点，除叶子节点外的所有节点的关键字，都在它的下一级子树中同样存在，最后所有数据都存储在叶子节点中。
根节点的最大关键字其实就表示整个 B+ 树的最大元素。
第三点，叶子节点包含了全部的数据，并且按顺序排列，B+ 树使用一个链表将它们排列起来，这样在查询时效率更快。
由于 B+ 树的中间节点不含有实际数据，只有子树的最大数据和子树指针，因此磁盘页中可以容纳更多节点元素，也就是说同样数据情况下，B+ 树会 B 树更加“矮胖”，因此查询效率更快。B+ 树的查找必会查到叶子节点，更加稳定。
当需要查询某个范围内的数据时，由于 B+ 树的叶子节点是一个有序链表，只需在叶子节点上遍历即可，不用像 B 树那样挨个中序遍历比较大小。
因此，得出B+树的三个优点
1.层级更低，IO 次数更少
2.每次都需要查询到叶子节点，查询性能稳定
3.叶子节点形成有序链表，范围查询方便
B树也有优点，其优点在于，由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。2.2.3.3B*树
B*树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3(代替B+树的1/2)；
B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；
B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；所以，B*树分配新结点的概率比B+树要低，空间使用率更高
B树类型总结：
1.二叉搜索树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；
2.B树(B-树)：多路搜索树，每个结点存储M/2到M（M是指M阶B树）个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；
3.B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；
4.B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/32.2.4红黑树
解决二叉查找树多次插入新节点而导致的不平衡问题。
红黑树(Red Black Tree)是一种自平衡的二叉查找树。除了符合二叉查找树的基本特性外，它还具有下列的【附加特性】:
1.节点是红色或黑色。
2.根节点是黑色。
3.每个叶子节点都是黑色的空节点（NIL节点）。
4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
正是因为这些规则限制，才保证了红黑树的自平衡。红黑树从根到叶子的最长路径不会超过最短路径的2倍。当插入或删除节点的时候，红黑树的规则有可能被打破。这时候就需要做出一些调整，来继续维持我们的规则。
什么情况下会破坏红黑树的规则，什么情况下不会破坏规则呢？我们举两个简单的例子：
1.向原红黑树插入值为14的新节点：
由于父节点15是黑色节点，因此这种情况并不会破坏红黑树的规则，无需做任何调整。
2.向原红黑树插入值为21的新节点：
由于父节点22是红色节点，因此这种情况打破了红黑树的规则4（每个红色节点的两个子节点都是黑色），必须进行调整，使之重新符合红黑树的规则。调整有两种方法:变色和旋转。而旋转又分成两种形式:左旋转和右旋转。
变色：
为了重新符合红黑树的规则，尝试把红色节点变为黑色，或者把黑色节点变为红色。
下图所表示的是红黑树的一部分，需要注意节点25并非根节点。因为节点21和节点22连续出现了红色，不符合规则4，所以把节点22从红色变成黑色
但这样并不算完，因为凭空多出的黑色节点打破了规则5，所以发生连锁反应，需要继续把节点25从黑色变成红色。
此时仍然没有结束，因为节点25和节点27又形成了两个连续的红色节点，需要继续把节点27从红色变成黑色。
左旋转：
逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子。
图中，身为右孩子的Y取代了X的位置，而X变成了自己的左孩子。此为左旋转。
右旋转：
顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子
图中，身为左孩子的Y取代了X的位置，而X变成了自己的右孩子。此为右旋转。
以刚才所举的例子,首先，我们需要做的是变色，把节点25及其下方的节点变色
此时节点17和节点25是连续的两个红色节点，为了维持红黑树的规则，我们把节点8和节点17进行变色，由红色节点编程黑色节点。这样以来就形成了新的红黑树。
**红黑树和AVL树区别
RB-Tree和AVL树作为二叉搜索树(BBST)，其实现的算法时间复杂度相同，AVL作为最先提出的BBST，貌似RB-tree实现的功能都可以用AVL树是代替，那么为什么还需要引入RB-Tree呢？
1.红黑树不追求完全平衡，即不像AVL那样要求节点的 高度差的绝对值 <= 1，它只要求部分达到平衡，但是提出了为节点增加颜色，红黑是用非严格的平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决，而AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多。
2.就插入节点导致树失衡的情况，AVL和RB-Tree都是最多两次树旋转来实现复衡rebalance，旋转的量级是O(1)。
3.删除节点导致失衡，AVL需要维护从被删除节点到根节点root这条路径上所有节点的平衡，旋转的量级为O(logN)，而RB-Tree最多只需要旋转3次实现复衡，只需O(1)，所以说RB-Tree删除节点的rebalance的效率更高，开销更小。
4.AVL的结构相较于RB-Tree更为平衡，插入和删除引起失衡，RB-Tree复衡效率更高；当然，由于AVL高度平衡，因此AVL的Search效率更高。
5.针对插入和删除节点导致失衡后的rebalance操作，红黑树能够提供一个比较便宜的解决方案，降低开销，是对search，insert ，以及delete效率的折衷，总体来说，RB-Tree的统计性能高于AVL，故引入RB-Tree是功能、性能、空间开销的折中结果。
6.AVL更平衡，结构上更加直观，时间效能针对读取而言更高；维护稍慢，空间开销较大。红黑树，读取略逊于AVL，维护强于AVL，空间开销与AVL类似，内容极多时略优于AVL，维护优于AVL。总结：实际应用中，若搜索的次数远远大于插入和删除，那么选择AVL，如果搜索，插入删除次数几乎差不多，应该选择RB-Tree。
2.2.5堆
这里我们所说的堆是一种数据结构，和操作系统内存管理中的堆是两回事。
普通的二叉树不适合用数组来存储，因为可能会存在大量的空间浪费，只有完全二叉树适合使用顺序存储结构。
堆的概念：
将一个集合K = {k0，k1， k2，…，kn-1}，把所有元素都按照完全二叉树的顺序存储方式来存储，并且满足每个子树的根结点数值都大于等于（或小于等于）他们各自的子结点数值，这样的结构就叫堆。将根节点最大的堆叫大堆，根节点最小的堆叫小堆。
堆的性质：
1.堆中某个节点的值总是不大于或不小于其父节点的值。
2.堆总是一棵完全二叉树。
2.2.6完全二叉树
完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点
完全二叉树特点：
1.叶子结点只能出现在最下层和次下层。
2.最下层的叶子结点集中在树的左部。
3.倒数第二层若存在叶子结点，一定在右部连续位置。
4.如果结点度为1，则该结点只有左孩子，即没有右子树。
5.同样结点数目的二叉树，完全二叉树深度最小。2.2.7满二叉树
除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。
满二叉树特点：
1.叶子只能出现在最下一层。出现在其它层就不可能达成平衡。
2.非叶子结点的度(结点拥有的子树数目称为结点的度)一定是2
3.在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多2.3二叉树存储结构
2.3.1顺序存储结构
顺序存储结构实际就是用数组来存储，只适合完全二叉树，不适合一般的二叉树，因为不是完全二叉树会有空间的浪费。二叉树顺序存储结构在物理上是一个数组，在逻辑上是一颗二叉树。
2.3.2链式存储结构
二叉树的链式存储结构是值，用链表来表示一颗二叉树，即用链来表示元素的逻辑关系。通常的方法是链表中每个节点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链接点的存储地址。
2.3.2.1建二叉树
想要创建一棵二叉树，我们首先要建一个二叉树节点。
typedef int BTDataType;
typedef struct BinaryTreeNode
{
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
BTDataType data;
}BTNode;
//创建一个节点
BTNode* BuyNode(BTDataType x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
assert(node);
node->data = x;
node->left = NULL;
node->right = NULL;
return node;
}有了节点之后，我们就可以用n个节点来拼成一棵树。这里采用前序遍历的思想，往下递归时先把节点的值填充，等返回时节点和节点就会连到一起。
// 通过前序遍历的数组构建二叉树,0代表空指针
BTNode* CreatBinaryTree(BTDataType* arr,int* pi)
{
if (arr[*pi] == 0)
{
(*pi)++;
return NULL;
}
BTNode* root = BuyNode(arr[*pi]);
(*pi)++;
root->left = CreatBinaryTree(arr, pi);
root->right = CreatBinaryTree(arr, pi);
return root;
}2.3.2.2二叉树的遍历
遍历的概念：遍历是按照某种规则，对二叉树中的结点进行某种相应的操作，且每个结点只操作一次。
前序、中序以及后序遍历
这三种遍历都是深度优先。遵循的顺序如下：
1.前序遍历——访问根结点的操作发生在遍历其左右子树之前。
2.中序遍历——访问根结点的操作发生在遍历其左右子树之中。
3.后序遍历——访问根结点的操作发生在遍历其左右子树之后。以前序遍历为例:
//前序遍历
void pre_order(BTNode* root)
{
if (root == NULL)
{
printf("%c ", '#');
return;
}
printf("%d ", root->data);
pre_order(root->left);
pre_order(root->right);
}层序遍历
层序遍历，顾名思义，就是一层一层的遍历。这里我们要借助队列。
以这棵树为例，我们想要层序遍历。先把1放入队列中。然后开始循环下列操作：取队头的节点并删除掉，在删除的同时把队头节点的左右子节点放到队列中。这样把第一层的节点取完后第二层就会放到队列中，第二层节点取完后第三层的节点就会被放到队列中，循环此操作，实现层序遍历。
代码如下：
//层序遍历
void level_order(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
{
QueuePush(&q, root);
}
BTNode* front;
while (!QueueEmpty(&q))
{
front = QueueFront(&q);
printf("%d", front->data);
QueuePob(&q);
if (front->left)
{
QueuePush(&q, front->left);
}
if (front->right)
{
QueuePush(&q, front->right);
}
}
printf("\n");
QueueDestory(&q);
}2.3.2.3二叉树的销毁
二叉树的遍历要采用后续遍历，不然父节点销毁后会找不到子节点。
void tree_destory(BTNode* root)
{
if (root == NULL)
{
return;
}
//要采用后序遍历，不然父节点销毁了就找不到子节点了
tree_destory(root->left);
tree_destory(root->right);
free(root);
}
