一、概念：
二叉树遍历：按指定的某条搜索路径访问树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。
根节点N，按照先遍历左子树L再遍历右子树R的原则，常见的有三种：先序(NLR)、中序(LNR)、后序(LRN)。其中，序是指根节点什么时候被访问。
有时还有提到层序(按层遍历访问)
例如：下图
显然 深度为 4
求先序遍历： A(以A为根的左子树)(以A为根的右子树)——A(B)(以C为根的先序遍历)——ABC（E、F、G）——A B C D E F G
同理中序：中间访问根节点：B A D C F E G
后序遍历：B D F G E C A
二、算法实现
先序遍历操作过程：（递归）
如果二叉树为空，什么也不做。
否则：
（1）访问根节点
（2）先序遍历左子树
（3）先序遍历右子树
递归注意结束条件
//先序遍历递归
int PreOrder(BiTree T){
if(T!=NULL){
Visit(T);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
return 0;
}
中序遍历操作过程：（递归）
如果二叉树为空，什么也不做。
否则：
（1）中序遍历左子树
（2）访问根节点
（3）中序遍历右子树
递归注意结束条件
//中序遍历递归
int InOrder(BiTree T){
if(T!=NULL){
InOrder(T->lchild);
Visit(T);
InOrder(T->rchild);
}
return 0;
}
后序遍历操作过程：（递归）
如果二叉树为空，什么也不做。
否则：
（1）后序遍历左子树
（2）后序遍历右子树
（3）访问根节点
递归注意结束条件
//后序遍历递归
int PostOrder(BiTree T){
if(T!=NULL){
PostOrder(T->lchild);
PostOrder(T->rchild);
Visit(T);
}
return 0;
}
三种时间复杂度O（n）
最坏情况下，n个结点深度为n的斜树
层序遍历（ 使用队列）
完整代码：
#include<stdio.h>
#include<stdlib.h>
typedef char ElemType;//结点数据类型
//二叉树结点
typedef struct BiTNode{
ElemType data;//数据
struct BiTNode *lchild; //左子树指针
struct BiTNode *rchild; //右子树指针
}BiTNode,*BiTree;
//先序输入创建二叉树
int CreatBiTre(BiTree &T){
ElemType x;//输入结点值
scanf("%c",&x);
if(x=='#') T=NULL;//空结点输入空格
else{
T=(BiTree)malloc(sizeof(BiTNode));
if(T==NULL){
printf("OVERFLOW!\n");
exit(1);
}
T->data=x;
CreatBiTre(T->lchild);
CreatBiTre(T->rchild);
}
return 0;
}
void Visit(BiTree T){
if(T->data!='#')
printf("%c ",T->data);
}
//先序遍历递归
int PreOrder(BiTree T){
if(T!=NULL){
Visit(T);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
return 0;
}
//中序遍历递归
int InOrder(BiTree T){
if(T!=NULL){
InOrder(T->lchild);
Visit(T);
InOrder(T->rchild);
}
return 0;
}
//后序遍历递归
int PostOrder(BiTree T){
if(T!=NULL){
PostOrder(T->lchild);
PostOrder(T->rchild);
Visit(T);
}
return 0;
}
//树的深度递归
int TreeHeight(BiTree T){
int height,left,right;
if(T==NULL)
return 0;
left=TreeHeight(T->lchild);
right=TreeHeight(T->rchild);
height=(left>right)?left:right;
return height+1;//算上根结点一层
}
void main(){
BiTree T=NULL;
CreatBiTre(T);
int height;
height=TreeHeight(T);
printf("树的深度： %d\n",height);
printf("先序遍历： ");
PreOrder(T);
printf("\n");
printf("中序遍历： ");
InOrder(T);
printf("\n");
printf("后序遍历： ");
PostOrder(T);
printf("\n");
}
截图：
