一.常见的二叉树的遍历
①先序遍历：先访问根节点，再访问左右子树（根左右）
③中序遍历：先访问左子树，再访问根节点，最后访问右子树（左根右）
③后序遍历：先访问左右子树，再访问根节点（左右根）
先定义二叉树的数据结构：
typedef char ElemType;
typedef struct BTNode {
ElemType data; //数据域
struct BTNode* lchild; //左孩子指针
struct BTNode* rchild; //右孩子指针
}BTNode,*BTree;
二.二叉树的遍历
1.先序遍历
算法的实现：
①先访问根节点
②再先序遍历左子树
③最后先序遍历右子树
代码的实现：
//先序遍历
void PreOrder(BTree bt)
{
if (bt!= NULL)
{
printf("%c", bt->data);
PreOrder(bt->lchild);
PreOrder(bt->rchild);
}
}
递归函数实际上隐式的利用了栈，虽然没有实际上显示出来，但是在二叉树的遍历中可以清晰地表现出来。
二叉树先序遍历的整体过程为：根节点入栈并访问，再遍历左子树，出栈遍历右子树。
用图示的方法来对先序遍历的递归算法进行解释：
先序遍历：ABDFGCEH
因此根据以上图解也能够写出先序遍历的非递归算法，就是利用栈来实现遍历，具体流程也是如上图。
2.中序遍历
算法的实现：
①先中序遍历左子树
②再访问根节点
③最后中序遍历右子树
代码的实现：
//中序遍历
void InOrder(BTree bt)
{
if (bt != NULL)
{
InOrder(bt->lchild);
printf("%c", bt->data);
InOrder(bt->rchild);
}
}
递归函数实际上隐式的利用了栈，虽然没有实际上显示出来，但是在二叉树的遍历中可以清晰地表现出来。
其中二叉树的先序遍历和中序遍历的思路是一致的，唯一的差距就是访问根节点的时间不同。
二叉树中序遍历的整体过程为：根节点入栈遍历左子树，出栈访问根节点遍历右子树。
用图示的方法来对先序遍历的递归算法进行解释：
中序遍历：BFDGACEH
因此根据以上图解也能够写出中序遍历的非递归算法，就是利用栈来实现遍历，具体流程也是如上图。
3.后序遍历
算法的实现：
①先后序遍历左子树
②再后序遍历右子树
③最后访问根节点
代码的实现：
//后序遍历
void PostOrder(BTree bt)
{
if (bt != NULL)
{
PostOrder(bt->lchild);
PostOrder(bt->rchild);
printf("%c", bt->data);
}
}
递归函数实际上隐式的利用了栈，虽然没有实际上显示出来，但是在二叉树的遍历中可以清晰地表现出来。
其中二叉树的先序遍历和中序遍历的思路是一致的，唯一的差距就是访问根节点的时间不同，而后序遍历就存在一些差异，在根节点出栈后还需要再次入栈，为的是实现根节点最后的访问。
二叉树后序遍历的整体过程为：根节点入栈遍历左子树，出栈遍历右子树，紧接着入栈准备最后出栈的访问。
用图示的方法来对先序遍历的递归算法进行解释：
后序遍历：FGDBHECA
因此根据以上图解也能够写出后序遍历的非递归算法，就是利用栈来实现遍历，具体流程也是如上图。
三.完整代码及结果
这里输入二叉树：AB.DF…G…C.E.H…（‘.’表示为空）
可等到遍历结果：
先序遍历：ABDFGCEH
中序遍历：BFDGACEH
后序遍历：FGDBHECA
#include<stdio.h>
#include<stdlib.h>
typedef char ElemType;
typedef struct BTNode {
ElemType data;
struct BTNode* lchild;
struct BTNode* rchild;
}BTNode,*BTree;
//创建二叉树
void CreateBTree(BTNode*& bt)
{
ElemType data;
scanf("%c", &data);
//getchar();
if (data == '.')
{
bt = NULL;
}
else
{
bt = (BTree)malloc(sizeof(BTNode));
bt->data = data;
CreateBTree(bt->lchild);
CreateBTree(bt->rchild);
}
}
//先序遍历
void PreOrder(BTree bt)
{
if (bt!= NULL)
{
printf("%c", bt->data);
PreOrder(bt->lchild);
PreOrder(bt->rchild);
}
}
//中序遍历
void InOrder(BTree bt)
{
if (bt != NULL)
{
InOrder(bt->lchild);
printf("%c", bt->data);
InOrder(bt->rchild);
}
}
//后序遍历
void PostOrder(BTree bt)
{
if (bt != NULL)
{
PostOrder(bt->lchild);
PostOrder(bt->rchild);
printf("%c", bt->data);
}
}
int main()
{
BTNode* bt;
printf("输入二叉树：\n");
CreateBTree(bt);
printf("先序遍历：\n");
PreOrder(bt);
printf("\n");
printf("中序遍历：\n");
InOrder(bt);
printf("\n");
printf("后序遍历：\n");
PostOrder(bt);
printf("\n");
return 0;
}
