写在前面
二叉树（Binary Tree）的知识点是程序员面试的常考点，所以平时更应该注重这方面知识的积累。这篇文章主要涉及二叉树的基础知识和基础操作，对初学者相当于是一个引导。若想进一步
理解二叉树相关的知识，可以找找相关的技术书籍参考学习。
什么是二叉树
定义：二叉树是有限元素的集合，该集合或者为空（空二叉树），或者是由一个被称为根的元素及两个互不相交、被分别称为左子树和右子树的二叉树组成。
定义总喜欢绕来绕去以此体现其深奥难懂。。。其实放张图片就一目了然了。
二叉链表存储结构
其中 data 是数据域，lchild 和 rchild 都是指针域，分别存放指向左孩子和右孩子的指针。
完全二叉树
对一颗具有 n 个结点的二叉树按层序编号，如果编号为i（1<=i<=n）的结点与同样深度的满二叉树中编号为 **i **的结点在二叉树中位置完全相同，则这颗二叉树称为完全二叉树。
找了一张满二叉树与完全二叉树的对比图，应该比较容易理解完全二叉树。
接下来才是本文的重点——二叉树遍历。
二叉树遍历
前序遍历
规则是若二叉树为空，则空操作返回，否则先返回根结点，然后前序遍历左子树，再前序遍历右子树。遍历顺序为：ABDGHCEIF。
中序遍历
规则是若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点左子树，然后是访问根结点，最后中序遍历右子树。遍历顺序为：GDHBAEICF。
后序遍历
规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。遍历顺序为：GHDBIEFCA。
层序遍历
规则是若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。遍历顺序为：ABCDEFGHI。
二叉树基本代码
二叉链表结点结构
typedef char ElemType;
typedef struct node
{
ElemType data;
struct node *lchild, *rchild;
}BiTree;
二叉树的创建
由于前序、中序、后序遍历序列中的任何一个都不能确定一个二叉树，因此不能直接使用、三种序列之一不能唯一确定二叉树的原因是：不能确定其左右子树的情况。针对以上问题，按如下处理：将每个结点的空指针引出一个虚结点其值为特定值，如 #，以标识其为空，把这样处理后的二叉树称为原二叉树的扩展二叉树。扩展二叉树就可以做到一个遍历顺序确定一棵二叉树了。比如前序遍历为AB#D##C##，效果如下图所示。
/*创建二叉树*/
BiTree *CreateBiTree()
{
BiTree *t;
char ch;
scanf("%c", &ch);
if (ch != '#')
{
t = (BiTree*)malloc(sizeof(BiTree));
t->data = ch;
t->lchild = CreateBiTree();
t->rchild = CreateBiTree();
}
else
{
t = NULL;
}
return t;
}
输入字符串ABD#G###CE##F##，则二叉树创建递归过程如下图：
二叉树遍历
前序递归遍历
/*前序遍历*/
void PreOrder(BiTree *t)
{
if (t != NULL)
{
printf("%c", t->data);
PreOrder(t->lchild);
PreOrder(t->rchild);
}
}
中序递归遍历
/*中序遍历*/
void InOrder(BiTree *t)
{
if (t != NULL)
{
InOrder(t->lchild);
printf("%c", t->data);
InOrder(t->rchild);
}
}
后序递归遍历
/*后次遍历*/
void PostOrder(BiTree *t)
{
if (t != NULL)
{
PostOrder(t->lchild);
PostOrder(t->rchild);
printf("%c", t->data);
}
}
层次遍历
二叉树的层次遍历过程可描述如下：遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从队头取出一个元素，每取一个元素，执行下面两个操作：①访问该结点的数据元素；②若该结点的左右孩子非空，则将该结点的左孩子指针和右孩子指针顺序入队。此过程不断进行，当队列为空时，二叉树的层次遍历结束。
/*层次遍历*/
void LevelOrder(BiTree *t)
{
BiTree *p;
BiTree *queue[M];
int front, rear;
if (t == NULL)
return;
front = rear = 0;
queue[rear] = t;
rear = (rear + 1) % M;
while (front != rear)
{
p = queue[front];
front = (front + 1) % M;
printf("%c", p->data);
if (p->lchild != NULL)
{
queue[rear] = p->lchild;
rear = (rear + 1) % M;
}
if (p->rchild != NULL)
{
queue[rear] = p->rchild;
rear = (rear + 1) % M;
}
}
}
