二叉树遍历
遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。
设L、D、R分别表示遍历左子树、访问根结点和遍历右子树， 则对一棵二叉树的遍历有三种情况：DLR（称为先根次序遍历，即先序遍历），LDR（称为中根次序遍历，即中序遍历），LRD （称为后根次序遍历，即后序遍历）。这里的先序，中序和后序都是以根为标准。
5.5.1 先序遍历
先序遍历的方法：
访问根；按先序遍历左子树；按先序遍历右子树。
上图在先序遍历下的序列是：7,3,1,4,6,8,5,2
先序遍历的递归算法：
void preorder(btree *t)
{
if(t == NULL)
return;
printf(“%d”,
t->data);
preorder(t->left);
preorder(t->right);
}
5.5.2 中序遍历
中序遍历的方法：
按中序遍历左子树；访问根；按中序遍历右子树。
上图在中序遍历下的结点序列：1,3,6,4,7,5,8,2
中序遍历的递归算法：
void inorder(btree *t)
{
if(t==NULL)
return;
inorder(t->left);
printf(“%d”, t->data);
inorder(t->right);
}
5.5.3 后序遍历
后序遍历的方法：
按后序遍历左子树；按后序遍历右子树；访问根。
上图在后续遍历下的结点序列：1,6,4,3,5,2,8,7
void postorder(btree *t)
{
if(t==NULL)
return;
postorder(t->left);
postorder(t->right);
printf(“%d”, t->data);
}
注意：前序（后序）、中序确定一颗树；前序、后序无法确定一颗树
比如有一棵树，它的
前序遍历结点顺序: abefcgh
中序遍历结点顺序: ebfaghc
试画出这棵树。
分析：主要思路就是利用前序遍历中的头结点在中序中的位置，将中序遍历分成左右2个子树。然后依次递归。
在前序遍历中，第一个节点a为树根,则在中序中找到a，将中序序列一分为二：ebf，ghc。ebf显然为左子树的中序遍历，ghc为右子树的中遍历。而在前序遍历可以知道中序遍历的ebf的前序遍历是bef，中序遍历的ghc的前序遍历是cgh。依次类推，b把中序遍历中的ebf分成了左右子树e,f。c将中序遍历中的ghc分成了左子树gh，右子树NULL。而中序遍历的gh，在前序遍历中是gh，因此g将gh分成了左子树NULL，右子树h。
于是整个图为：
知道一棵树的前序和中序，或者后序和中序，可以确定一棵树，但是如果只知道前序和后序，是无法确定一棵树的。比如下面的例子：
前序：a,b；后序：b,a，可以画出下面2种形态的树：
