二叉树的遍历(递归遍历)

1. 先序遍历

在先序遍历中，对节点的访问工作是在它的左右儿子被访问之前进行的。换言之，先序遍历访问节点的顺序是根节点-左儿子-右儿子。由于树可以通过递归来定义，所以树的常见操作用递归实现常常是方便清晰的。

void xian(BiTree T){//先序遍历 if(T==NULL)return;visit(T);xian(T->lchild);xian(T->rchild); 
}

2中序遍历

.中序遍历的遍历路径与先序遍历完全一样。其实现的思路也与先序遍历非常相似。其主要的不同点是访问节点顺序不同：中序遍历是访问完所有左儿子后再访问根节点，最后访问右儿子，即为左儿子-根节点-右儿子。

void center(BiTree T){//中序遍历 if(T==NULL)return;	center(T->lchild);visit(T);center(T->rchild); 
} 

3. 后序遍历

后序遍历与中序遍历，先序遍历的路径也完全一样。主要的不同点是后序遍历访问节点的顺序是先访问左儿子和右儿子，最后访问节点，即左儿子-右儿子-根节点。

void LAST(BiTree T){//后序遍历 if(T==NULL)return;	LAST(T->lchild);LAST(T->rchild);visit(T);
}

4. 层序遍历

二叉树遍历的核心问题是二维结构的线性化。我们通过节点访问其左右儿子时，存在的问题是访问左儿子后，右儿子怎么访问。因此我们需要一个存储结构保存暂时不访问的节点。前面三种遍历方式的非递归实现，我们是通过堆栈来保存。事实上也可以通过队列来保存。
队列实现的基本思路：遍历从根节点开始，首先将根节点入队，然后执行循环：节点出队，访问（访问）根节点，将左儿子入队，将右儿子入队，直到队列为空停止。这种遍历方式的结果是将二叉树从上到下，从左至右一层一层的遍历，即层序遍历

cenxu(BiTree T){//层序遍历 queueq;BiTree p;q.push(T);while(!q.empty()){cout<data;p=q.front();q.pop();if(p->lchild!=NULL){q.push(p->lchild);}if(p->rchild!=NULL){q.push(p->rchild);}}
}  

具体代码：

#include
#include
#include 
using namespace std;
typedef struct BiNode{char data;BiNode *lchild ,*rchild;
}BTree,*BiTree; 
BiTree creat(){//建立二叉树 char ch;BiTree T;cin>>ch;if(ch=='#'){T=NULL;}else {T=new BTree;T->data=ch;T->lchild=creat();T->rchild=creat(); }
return T; 
}void visit(BiTree T){//遍历输出 
cout<data;}
void xian(BiTree T){//先序遍历 if(T==NULL)return;visit(T);xian(T->lchild);xian(T->rchild); 
}
void center(BiTree T){//中序遍历 if(T==NULL)return;	center(T->lchild);visit(T);center(T->rchild); 
} 
void LAST(BiTree T){//后序遍历 if(T==NULL)return;	LAST(T->lchild);LAST(T->rchild);visit(T);
}cenxu(BiTree T){//层序遍历 queueq;BiTree p;q.push(T);while(!q.empty()){cout<data;p=q.front();q.pop();if(p->lchild!=NULL){q.push(p->lchild);}if(p->rchild!=NULL){q.push(p->rchild);}}
}  int  main(){BiTree T=(BiTree)malloc(sizeof(BTree));T=creat();xian(T);cenxu(T); 
}