前言：程序 = 数据结构 + 算法。本篇是二叉树基础，会介绍二叉树一些重要性质和概念，整理了前序、中序、后序遍历两种算法（递归和迭代）。本篇简书基于《大话数据结构》而写，非常推荐的入门书籍，如果能力较强可以直接去啃《数据结构和算法》。
一、学习二叉树的重要性
- 工作面试时，经常出现二叉树相关算法
- 二叉树是树核心和重点
- 支持强大的搜索算法
- 树、森林是一种非常复杂数据结构，但是树、森林可以转换成二叉树去处理（三者可以相互转换）
二、横扫基础知识
什么是二叉树？二叉树（Binary Tree）是 n （n >= 0）个节点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。这是官方定义，下面这棵树就是传说中的二叉树，不会出现超过二个分支。
特点：
- 每个结点最多有两棵子树
- 左子树和右子树是有顺序的不能任意颠倒，如下图就是五棵不同的二叉树。
满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树为满二叉树。
这个定义看图就能明白，就是一棵非常完美的二叉树。
完全二叉树：对一棵具有 n 个结点的二叉树按层序编号，如果编号为 i （1<= i <= n）的结点与同样深度的满二叉树中编号 i 的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。
这定义最好结合满二叉树图去理解，比如此图i=4或者i=10在满二叉树图中位置就是等于4和10。现在脑补一下，假设将此图i=5的左子树（也就是i=10这个结点），移动成i=7这个结点左子树，那么这棵树还是完全二叉树吗？答案肯定不是，因为满二叉树图i=7左子树对应的是i=14这个结点。
满二叉一定是一棵完全二叉树，但是完全二叉树不一定是满的。
作为两种特殊的二叉树，满二叉树和完全二叉树容易混淆，分不清也没关系，知道有这两棵树就OK了。
二叉树的五个性质：(前三个要求掌握)
性质1：在二叉树的第 i 层上至多有 2^(i-1)个结点（i>=1）。
性质2：深度为k的二叉树至多有 2^k - 1个结点（k>=1）。
性质3：对任何一棵二叉树 T ，如果其终端结点数为 n0，度为2的结点数为n2，则n0=n2+1。
性质4：具有n个结点的完全二叉树的深度为k的度为[log(2)n]+1([X]表示向下取整)。
性质5：如果对一棵有n个结点的完全二叉树（其深度为[log(2)n]+1）的结点按层序编号，对任一结点 i（1<=i<=n）有：
①如果i=1，则结点 i 是二叉树的根，无双亲；如果i>1，则其双亲是结点[i/2]向下取整。
②如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。
③如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1.
三、二叉树的遍历（重要）
前面都是铺垫，二叉树遍历才是主菜，重点肯定也是难点。
二叉树遍历原理：二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。注意概念中的访问和遍历两个关键词。
二叉树的遍历方式有很多，按从左到右遍历主要分为前序遍历、中序遍历、后序遍历和层序遍历。
-
前序遍历
前序遍历的规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树，如下图，遍历的顺序为：ABDGHCEIF
前序遍历 中序遍历
中序遍历是从根结点的左子树开始，然后访问根结点，最后中序遍历右子树，如下图，遍历的顺序为：GDHBAEICF
-
后序遍历
从左到右先叶子结点的方式遍历访问左右子树，最后访问根结点，如下图，遍历的顺序为：GHDBIEFCA
后序遍历 -
层序遍历
从树的第一层根结点，从上而下遍历，同层从左到右访问，如下图，遍历顺序为：ABCDEFGHI
层序遍历
四、实战
假设我们有如下这样一棵二叉树T。这树已经用二叉链表结构存储在内存当中。（之所以不使用原来的图，仅仅希望能多举一个例子，然后大家可以比较学习）
结点定义：
/*二叉链表结点结构定义*/
typedef int TElemType;
typedef struct BiTNode{//结点结构
TElemType date;//结点数据
struct BiTNode *lchild,*rchild;//左右孩子指针
} BiTNode,*BiTree;
- 前序遍历（递归算法）
void PreOrderTraverse(BiTree T){
if(T==null)
return;
printf("%c",T->data);/*显示结点数据，可以更改为其他对结点操作*/
PreOrderTraverse(T->lchild);/*遍历左子树*/
PreOrderTraverse(T->rchild);/*遍历右子树*/
}
看到这里也许你会和我一样失望，说好的前序遍历呢，为什么这么几行代码就把前序遍历解决了，不错你没看错，别小看这几行代码，其实这几行代码才是无穷无尽的，这就是递归算法！（网上说递归算法是神写的，迭代算法才是人写的=_=）。不了解递归算法的小伙伴赶快去看这篇文章《Java算法》。
分析：
①当调用PreOrderTraverse(T)，T的根结点不为null，所以执行printf，打印字母A。
②接下来调用PreOrderTravers(T->lchild);访问了A结点的左孩子，不为null，执行printf显示字母B。
③在这里可以很清楚的看到打印B之后，会继续执行PreOrderTravers(T->lchild);访问B结点的左孩子，执行printf显示字母D。
④再次递归调用PreOrderTravers(T->lchild),打印字母H。（一直到这里 PreOrderTraverse(T->rchild);方法从来没有执行过，只有当左孩子PreOrderTraverse(T->lchild);递归完成才会执行右孩子的递归）
⑤再次递归调用PreOrderTravers(T->lchild)；访问了H孩子的左孩子，此时因为H结点无左孩子，所以T==null，返回此函数。直到此时PreOrderTravers(T->lchild)；H这个结点的左孩子递归执行完毕 。此时递归调用PreOrderTravers(T->rchild)；访问了H结点的右孩子，打印显示字母K。
⑥再次递归调用PreOrderTravers(T->lchild)；访问K的左孩子，没有，则返回。调用PreOrderTravers(T->rchild)；访问K的右孩子也没有，则返回。于是此函数执行完毕，返回到上一级递归的函数（即打印H结点时的函数 ），也执行完毕，返回到打印结点D时的函数，访问了D的函数，发现D结点没有右孩子，继续返回上一层递归函数，打印E。
⑦由于E没有左右孩子，返回打印B时的递归函数，递归执行完毕，返回到最初的PreOrderTravers，调用PreOrderTravers(T->rchild)；访问结点A的右孩子，打印字母C。依次类推，前序遍历二叉树的结点顺序是：ABDHKECFIGJ。
如果还是不能理解，可以一边看代码一边画图。能用递归算法实现的遍历按照常理来说使用迭代算法也是可以实现的，并且在面试中容易被问到遍历迭代算法应注意什么。
迭代算法：
（迭代算法请看补充篇，链接在文章末尾。）
- 中序遍历（递归算法）
void InOrderTraverse(BiTree T){
if(T==null)
return;
InOrderTraverse(T->lchild);/*遍历左子树*/
printf("%c",T->data);/*显示结点数据，可以更改为其他对结点操作*/
InOrderTraverse(T->rchild);/*遍历右子树*/
}
分析：
①调用InOrderTraverse（T），T的根结点不为null，于是调用 InOrderTraverse(T->lchild);访问结点B。当前指针不为null，继续调用 InOrderTraverse(T->lchild)；一直继续调用；直到访问结点H的左孩子，发现当前指针为null，于是返回。打印当前结点H。
②然后调用 InOrderTraverse(T->rchild);访问结点H的右孩子K，因为结点K没有左孩子，所以打印K。
③因为结点K没有右孩子，所以返回。打印结点H函数执行完毕，返回。打印D。
④D无右孩子，此函数执行完毕，返回。打印B。
⑤后面都是相同的道理了，最终打印结点顺序是：HKDBEAIFCGJ
迭代算法：
（迭代算法请看补充篇，链接在文章末尾。）
- 后序遍历（递归算法）
如果前序遍历和中序遍历弄明白了，后序遍历很容易想到如何写，打印的结果是：KHDEBIFJGCA。
void PostOrderTraverse(BiTree T){
if(T==null)
return;
PostOrderTraverse(T->lchild);/*遍历左子树*/
PostOrderTraverse(T->rchild);/*遍历右子树*/
printf("%c",T->data);/*显示结点数据，可以更改为其他对结点操作*/
}
迭代算法：
（迭代算法请看补充篇，链接在文章末尾。）
五、总结：
树和二叉树的内容还有很多，想了解更多细节的同学建议买本书好好研究。我学习数据结构挺迟的，虽然走了很多弯路，但是相比于有些人说这么难的东西，工作中又用不到，干嘛学呢，自己能认识其重要性还是很幸运的。我承认以后参加工作，尤其是从事应用层开发的人员，几乎遇不到要求你来写数据结构和算法。但是有些事物不能因为你感受不到它带给你的直接好处就不去做，就像阅读，也许现在并不能给你带来直接的利益，但是却在潜移默化影响着你的思想。
每月更新两篇，质量保证，点击关注！
听说点喜欢的人运气会一直很好！！！
