1 前言
今天我们来介绍一下二叉树，包括定义，数据结构定义，遍历，和二叉树的推倒。
转载请注明出处：http://blog.csdn.net/developer_zhang
2 详述
2.1 二叉树定义
二叉树（Binary Tree）是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的，分别称为根结点的左子树和右子树的二叉树组成。
2.1.1 二叉树五种基本形态
·空二叉树
·只有一个根结点
·根结点只有左子树
·根结点只有右子树
·根结点既有左子树又有右子树
2.1.2 特殊二叉树
·斜树：所有的结点都只有左子树的二叉树叫做左斜树。 所有的结点都只有右子树的二叉树叫做右斜树。这两者统称为斜树。
·满二叉树：在一棵二叉树中，如果所有的分支结点都存在左子树和右子树，并且所有的叶子都在同一层上，这样的二叉树称为满二叉树。
·完全二叉树：对一棵具有n个结点的二叉树按层序编号，如果编号i(1<i=<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这可二叉树称为完全二叉树。
2.2 二叉树的存储结构
2.2.1 顺序结构
该结构只适合与完全二叉树。将每个结点存放与数组之中。
2.2.2 二叉链表
二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域，我们称这样的链表叫做二叉链表。
其中data是数据域，lchild和rchild都是指针域，分别存放指向左孩子和右孩子的指针。
结构定义代码：
/*二叉树的二叉链表结点结构定义*/
typedef struct BiTNode /*结点结构*/
{
TElemType data; /*结点数据*/
struct BiTNode *lchild,*rchild; /*左右孩子指针*/
}BiTNode,*BiTree;
如图：
2.3 遍历二叉树
二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序一次访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。
二叉树的遍历方法主要有：前序，中序，后续，层级四种方法。
2.3.1 前序遍历
若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。如图，遍历的顺序为：ABDGHCEIF。
算法代码：
/*二叉树的前序遍历递归算法*/
void PreOrderTraverse(BiTree T)
{
if(T==NILL)
return;
printf("%c",T->data); /*显示结点数据，可以更改为其他对结点的操作*/
PreOrderTraverse(T->lchild); /*再先序遍历左子树*/
PreOrderTraverse(T->rchild); /*再先序遍历右子树*/
}
2.3.2 中序遍历
若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后访问根结点，最后中序遍历右子树。如图,遍历的顺序为：GDHBAEICF。
算法代码：
/*二叉树的中序遍历递归算法*/
void InOrderTraverse()
{
if(T==NULL)
return;
InOrderTraverse(T->lchild); /*中序遍历左子树*/
printf("%c",T->data); /*显示结点数据，可以更改为其他对结点的操作*/
InOrderTraverse(T->rchild); /*最后中序遍历右子树*/
}
2.3.3 后序遍历
若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。如图：遍历顺序为：GHDBIEFCA。
算法代码：
/*二叉树的后续遍历递归算法*/
void PostOrderTraverse(BiTree T)
{
if(T==NULL)
return;
PostOrderTraverse(T->lchilid); /*先后续遍历左子树*/
PostOrderTraverse(T->rchilid); /*再后序遍历右子树*/
printf("%c",T->data); /*显示结点数据，可以更改为其他对结点的操作*/
}
综上所述：我个人认为这个遍历的前中后序的方法都是相对于结点来说的。
2.4 推倒遍历结果
-例：一直一棵二叉树的前序遍历序列为ABCDEF，中序遍历序列为CBAEDF，请问这棵二叉树的后续遍历结果是多少？
解答：·前序遍历是先打印再递归左和右，所以第一个字母A被打印出来，说明A是根结点数据。
·再由中序遍历CBAEDF，可以知道C和B是A的左子树的结点，EDF是A的右子树的结点。
·前序ABCDEF，先打印B后打C，所以B是A的左孩子，C是B的孩子，但是不确定左还是右。再看中序遍历CBAEDF，C是在B的前面打印，所以C是B的左孩子。
·再看EDF，它的顺序是ABCDEF，那就意味着D是A的右孩子，E和F是D的子孙，不一定是孩子，还有可能是孙子。再看中序CBAEDF，由于E在D的左侧，而F在右侧，所以E是D的左孩子，F是D的右孩子。由此得到次二叉树：
·由此得到后续遍历为：CBEFDA。
-例：二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，求前序序列。
解答：·由后序BDCAFGE =》E为根结点。
·于是由中序ABCDEFG =》分为两个树，左树ABCD，右树FG。A为E的左孩子。
·再由中序ABCDEFG，知道BCD为A的右子孙。再由后续BDCAFGE得知C为A的右孩子。
·由中序ABCDEFG，得知B是C的左孩子，D是C的右孩子。
·由后续BDCAFGE，得到G是E的右孩子，F就是G的孩子。根据中序ABCDEFG =》F是G的左孩子。
·由此得出前序遍历：EACBDGF。
由此可知：
·已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
·已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
也就是说已知中序遍历序列和另一种遍历序列，就能唯一确定一棵二叉树。
2.5 二叉树的建立
为了能让每个结点确认是否有左右孩子，我们对他进行扩展，也就是将二叉树中的每个结点的空指针引出一个虚结点，其值为一特定值，比如“#”。我们称这种处理后的二叉树为原二叉树的扩展二叉树。扩展二叉树就可以做到一个遍历序列确定一个二叉树了。比如下图前序遍历序列就为AB#D##C##。
我们把前序序列AB#D##C##用键盘挨个输入。实现的算法如下：
/*按前序插入二叉树中结点的值（一个字符）*/
/*#表示空树，构造二叉链表表示二叉树T*/
void CreatBiTree(BiTree *T)
{
TElemType ch;
scanf("%c",&ch);
if(ch=='#')
*T = NULL;
else{
*T = (BiTree)malloc(sizeof(BiTNode));
if(!*T)
exit(OVERFLOW);
(*T)->data = ch; /*生成根结点*/
CreateBiTree(&(*T)->lchild); /*构造左子树*/
CreateBiTree(&(*T)->rchild); /*构造右子树*/
}
}
其实建立二叉树，也是利用了递归原理。只不过把原来应该打印结点的地方，改成了生成结点，给结点赋值的操作而已。
3 结语
以上是所有内容，希望对大家有所帮助。