试完成二叉树按层次（同一层自左至右）遍历的算法。

#include "iostreamh"
#include "stdlibh"
#include "stdioh"
typedef char ElemType;//定义二叉树结点值的类型为字符型
const int MaxLength=10;//结点个数不超过10个
typedef struct BTNode{
ElemType data;
struct BTNode lchild,rchild;
}BTNode, BiTree;
void CreateBiTree(BiTree &T){//按先序次序输入，构造二叉链表表示的二叉树T，空格表示空树
// if(T) return;
char ch;
ch=getchar(); //不能用cin来输入，在cin中不能识别空格。
if(ch==' ') T=NULL;
else{
if(!(T=(BTNode )malloc(sizeof(BTNode)))) cout<<"malloc fail!";
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
void PreOrderTraverse(BiTree T){//先序遍历
if(T){
cout<<T->data<<' ';
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
void InOrderTraverse(BiTree T){//中序遍历
if(T){
InOrderTraverse(T->lchild);
cout<<T->data<<' ';
InOrderTraverse(T->rchild);
}
}
void PostOrderTraverse(BiTree T){//后序遍历
if(T){
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout<<T->data<<' ';
}
}
void LevelOrderTraverse(BiTree T){//层序遍历
BiTree Q[MaxLength];
int front=0,rear=0;
BiTree p;
if(T){ //根结点入队
Q[rear]=T;
rear=(rear+1)%MaxLength;
}
while(front!=rear){
p=Q[front]; //队头元素出队
front=(front+1)%MaxLength;
cout<<p->data<<' ';
if(p->lchild){ //左孩子不为空，入队
Q[rear]=p->lchild;
rear=(rear+1)%MaxLength;
}
if(p->rchild){ //右孩子不为空，入队
Q[rear]=p->rchild;
rear=(rear+1)%MaxLength;
}
}
}
//非递归的先序遍历算法
void NRPreOrder(BiTree bt)
{ BiTree stack[MaxLength],p;
int top;
if (bt!=NULL){
top=0;p=bt;
while(p!=NULL||top>0)
{ while(p!=NULL)
{
cout<<p->data;
stack[top]=p;
top++;
p=p->lchild;
}
if (top>0)
{ top--; p=stack[top]; p=p->rchild; }
}
}
}
//非递归的中序遍历算法
void NRInOrder(BiTree bt)
{ BiTree stack[MaxLength],p;
int top;
if (bt!=NULL){
top=0;p=bt;
while(p!=NULL||top>0)
{ while(p!=NULL)
{
stack[top]=p;
top++;
p=p->lchild;
}
if (top>0)
{ top--; p=stack[top];cout<<p->data; p=p->rchild; }
}
}
}
//非递归的后序遍历算法
/bt是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。
需要判断根结点的左右子树是否均遍历过。
可采用标记法，结点入栈时，配一个标志tag一同入栈
(1：遍历左子树前的现场保护，2：遍历右子树前的现场保护)。
首先将bt和tag(为1)入栈，遍历左子树；
返回后，修改栈顶tag为2，遍历右子树；最后访问根结点。/
typedef struct
{
BiTree ptr;
int tag;
}stacknode;
void NRPostOrder(BiTree bt)
{
stacknode s[MaxLength],x;
BiTree p=bt;
int top;
if(bt!=NULL){
top=0;p=bt;
do
{
while (p!=NULL) //遍历左子树
{
s[top]ptr = p;
s[top]tag = 1; //标记为左子树
top++;
p=p->lchild;
}
while (top>0 && s[top-1]tag==2)
{
x = s[--top];
p = xptr;
cout<<p->data; //tag为R，表示右子树访问完毕，故访问根结点
}
if (top>0)
{
s[top-1]tag =2; //遍历右子树
p=s[top-1]ptr->rchild;
}
}while (top>0);}
}//PostOrderUnrec
int BTDepth(BiTree T){//求二叉树的深度
if(!T) return 0;
else{
int h1=BTDepth(T->lchild);
int h2=BTDepth(T->rchild);
if(h1>h2) return h1+1;
else return h2+1;
}
}
int Leaf(BiTree T){//求二叉树的叶子数
if(!T) return 0;
else if(!T->lchild&&!T->rchild) return 1;
else return(Leaf(T->lchild)+Leaf(T->rchild));
}
int NodeCount(BiTree T){//求二叉树的结点总数
if(!T) return 0;
else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}
void main(){
BiTree T;
T=NULL;
int select;
//cout<<"请按先序次序输入各结点的值，以空格表示空树(输入时可连续输入):"<<endl;
// CreateBiTree(T);
while(1){
cout<<"\n\n请选择要执行的 *** 作:\n";
cout<<"1创建二叉树\n";
cout<<"2二叉树的递归遍历算法（前、中、后）\n";
cout<<"3二叉树的层次遍历算法\n";
cout<<"4求二叉树的深度\n";
cout<<"5求二叉树的叶子结点\n";
cout<<"6求二叉树的结点总数\n";
cout<<"7二叉树的非递归遍历算法（前、中、后）\n"; //此项可选做
cout<<"0退出\n";
cin>>select;
switch(select){
case 0:return;
case 1:
cout<<"请按先序次序输入各结点的值，以空格表示空树(输入时可连续输入):"<<endl;
CreateBiTree(T);
break;
case 2:
if(!T) cout<<"未建立树，请先建树！";
else{
cout<<"\n先序遍历:\n";
PreOrderTraverse(T);
cout<<"\n中序遍历:\n";
InOrderTraverse(T);
cout<<"\n后序遍历:\n";
PostOrderTraverse(T);
}
break;
case 3:
cout<<"\n层序遍历:\n";
LevelOrderTraverse(T);
break;
case 4:
cout<<"二叉树的深度为:\n";
cout<<BTDepth(T);
break;
case 5:
cout<<"\n叶子节点数:\n";
cout<<Leaf(T);
break;
case 6:
cout<<"总节点数:\n";
cout<<NodeCount(T);
break;
case 7:
if(!T) cout<<"未建立树，请先建树！";
else{
cout<<"\n先序遍历:\n";
NRPreOrder(T);
cout<<"\n中序遍历:\n";
NRInOrder(T);
cout<<"\n后序遍历:\n";
NRPostOrder(T);
}
break;
default:
cout<<"请确认选择项:\n";
}//end switch
}//end while
}

参考资料：

找来的，你看看吧！

这是小地刚编完的，能运行
#include"stdioh"
#include"malloch"
typedef struct bitnode
{
char data;
struct bitnode lchild,rchild;
}bitree;
bitree T;
typedef struct qnode
{
bitree deta;
struct qnode next;
}queueptr;
typedef struct
{
queueptr front;
queueptr rear;
}linkqueue;
linkqueue Q;
void layerorder(bitree t);
void enqueue(bitree t2);
bitree dequeue();
void main()
{
bitree t;
T=t=(bitnode)malloc(sizeof(bitnode));
t->data='a';
t=t->lchild;
t=(bitnode)malloc(sizeof(bitnode));
t->data='b';
t->lchild=NULL;
t->rchild=NULL;
t=T;
t=t->rchild;
t=(bitnode)malloc(sizeof(bitnode));
t->data='c';
t->lchild=NULL;
t->rchild=NULL;
layerorder(T);
}
void layerorder(bitree t1)
{
bitree p;
Qfront=Qrear=(queueptr)malloc(sizeof(qnode));
enqueue(t1);
while(Qfront!=Qrear)
{
p=dequeue();
if(p->lchild)
enqueue(p->lchild);
if(p->rchild)
enqueue(p->rchild);
}
}
void enqueue(bitree t2)
{
queueptr q;
q=(queueptr)malloc(sizeof(qnode));
q->deta=t2;
q->next=NULL;
Qrear->next=q;
Qrear=q;
}
bitree dequeue()
{
queueptr q1;
bitree p2;
q1=Qfront->next;
p2=q1->deta;
Qfront->next=q1->next;
printf("%c",p2->data);
return(p2);
}

层次遍历 EAFBHDGICKJ

后序遍历 CDBAGJKIHFE

画法：根E，E左A右F，A右B，B右D，D左C，F右H，H左G右I，I右K，K左J

先看先序，其第一个为树的根，先序遍历是先根再左子树最后右子树，第一个肯定是树的根，先画A，A再中序遍历中左右都有，说明A有左子树也有右子树。

先看左孩子一边，先序下一个为B,故它为根的左孩子，且中序中A在B的前边，所以A为B的左孩子，再看先序中的D，它就是B的右孩子，且中序中C在D的前面，所以C为D的左孩子，根的左枝完事。右边同理。

扩展资料：

除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

参考资料来源：百度百科-二叉树遍历

后续遍历为 ：bfgdeca
层序遍历二叉树（同一层从左到右访问）
中序遍历也叫做中根遍历，可记做左根右。
中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。
根据层次遍历 首先确定根节点 a，左孩子：b，右孩子 c；
然后，由中序 遍历 去掉ba（如果左孩子有 孩子的话 b就不是 第一个啦） 后 是 fdgce ，以c为 根节点 分左孩子 ：fdg ，右孩子：e
当然 因为是 中序遍历 所以 左孩子 fdg 根节点为 d， 左孩子：f ，右孩子：g
a
b c
d e
f g

#include "iostreamh"
#include "stdlibh"
#include "stdioh"
typedef char ElemType;//定义二叉树结点值的类型为字符型
const int MaxLength=10;//结点个数不超过10个
typedef struct BTNode{
ElemType data;
struct BTNode lchild,rchild;
}BTNode, BiTree;
void CreateBiTree(BiTree &T){//按先序次序输入，构造二叉链表表示的二叉树T，空格表示空树
// if(T) return;
char ch;
ch=getchar(); //不能用cin来输入，在cin中不能识别空格。
if(ch==' ') T=NULL;
else{
if(!(T=(BTNode )malloc(sizeof(BTNode)))) cout<<"malloc fail!";
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
void PreOrderTraverse(BiTree T){//先序遍历
if(T){
cout<<T->data<<' ';
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
void InOrderTraverse(BiTree T){//中序遍历
if(T){
InOrderTraverse(T->lchild);
cout<<T->data<<' ';
InOrderTraverse(T->rchild);
}
}
void PostOrderTraverse(BiTree T){//后序遍历
if(T){
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout<<T->data<<' ';
}
}
void LevelOrderTraverse(BiTree T){//层序遍历
BiTree Q[MaxLength];
int front=0,rear=0;
BiTree p;
if(T){ //根结点入队
Q[rear]=T;
rear=(rear+1)%MaxLength;
}
while(front!=rear){
p=Q[front]; //队头元素出队
front=(front+1)%MaxLength;
cout<<p->data<<' ';
if(p->lchild){ //左孩子不为空，入队
Q[rear]=p->lchild;
rear=(rear+1)%MaxLength;
}
if(p->rchild){ //右孩子不为空，入队
Q[rear]=p->rchild;
rear=(rear+1)%MaxLength;
}
}
}
//非递归的先序遍历算法
void NRPreOrder(BiTree bt)
{ BiTree stack[MaxLength],p;
int top;
if (bt!=NULL){
top=0;p=bt;
while(p!=NULL||top>0)
{ while(p!=NULL)
{
cout<<p->data;
stack[top]=p;
top++;
p=p->lchild;
}
if (top>0)
{ top--; p=stack[top]; p=p->rchild; }
}
}
}
//非递归的中序遍历算法
void NRInOrder(BiTree bt)
{ BiTree stack[MaxLength],p;
int top;
if (bt!=NULL){
top=0;p=bt;
while(p!=NULL||top>0)
{ while(p!=NULL)
{

stack[top]=p;
top++;
p=p->lchild;
}
if (top>0)
{ top--; p=stack[top];cout<<p->data; p=p->rchild; }
}
}
}
//非递归的后序遍历算法
/bt是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。
需要判断根结点的左右子树是否均遍历过。
可采用标记法，结点入栈时，配一个标志tag一同入栈
(1：遍历左子树前的现场保护，2：遍历右子树前的现场保护)。
首先将bt和tag(为1)入栈，遍历左子树；
返回后，修改栈顶tag为2，遍历右子树；最后访问根结点。/
typedef struct
{
BiTree ptr;
int tag;
}stacknode;
void NRPostOrder(BiTree bt)
{
stacknode s[MaxLength],x;
BiTree p=bt;
int top;
if(bt!=NULL){
top=0;p=bt;
do
{
while (p!=NULL) //遍历左子树
{
s[top]ptr = p;
s[top]tag = 1; //标记为左子树
top++;
p=p->lchild;
}

while (top>0 && s[top-1]tag==2)
{
x = s[--top];
p = xptr;
cout<<p->data; //tag为R，表示右子树访问完毕，故访问根结点
}

if (top>0)
{
s[top-1]tag =2; //遍历右子树
p=s[top-1]ptr->rchild;
}
}while (top>0);}
}//PostOrderUnrec
int BTDepth(BiTree T){//求二叉树的深度
if(!T) return 0;
else{
int h1=BTDepth(T->lchild);
int h2=BTDepth(T->rchild);
if(h1>h2) return h1+1;
else return h2+1;
}
}
int Leaf(BiTree T){//求二叉树的叶子数
if(!T) return 0;
else if(!T->lchild&&!T->rchild) return 1;
else return(Leaf(T->lchild)+Leaf(T->rchild));
}
int NodeCount(BiTree T){//求二叉树的结点总数
if(!T) return 0;
else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}
void main(){
BiTree T;
T=NULL;
int select;
//cout<<"请按先序次序输入各结点的值，以空格表示空树(输入时可连续输入):"<<endl;
// CreateBiTree(T);
while(1){
cout<<"\n\n请选择要执行的 *** 作:\n";
cout<<"1创建二叉树\n";
cout<<"2二叉树的递归遍历算法（前、中、后）\n";
cout<<"3二叉树的层次遍历算法\n";
cout<<"4求二叉树的深度\n";
cout<<"5求二叉树的叶子结点\n";
cout<<"6求二叉树的结点总数\n";
cout<<"7二叉树的非递归遍历算法（前、中、后）\n"; //此项可选做
cout<<"0退出\n";
cin>>select;
switch(select){
case 0:return;
case 1:
cout<<"请按先序次序输入各结点的值，以空格表示空树(输入时可连续输入):"<<endl;
CreateBiTree(T);
break;
case 2:
if(!T) cout<<"未建立树，请先建树！";
else{
cout<<"\n先序遍历:\n";
PreOrderTraverse(T);
cout<<"\n中序遍历:\n";
InOrderTraverse(T);
cout<<"\n后序遍历:\n";
PostOrderTraverse(T);
}
break;
case 3:
cout<<"\n层序遍历:\n";
LevelOrderTraverse(T);
break;
case 4:
cout<<"二叉树的深度为:\n";
cout<<BTDepth(T);
break;
case 5:
cout<<"\n叶子节点数:\n";
cout<<Leaf(T);
break;
case 6:
cout<<"总节点数:\n";
cout<<NodeCount(T);
break;
case 7:
if(!T) cout<<"未建立树，请先建树！";
else{
cout<<"\n先序遍历:\n";
NRPreOrder(T);
cout<<"\n中序遍历:\n";
NRInOrder(T);
cout<<"\n后序遍历:\n";
NRPostOrder(T);
}
break;
default:
cout<<"请确认选择项:\n";
}//end switch
}//end while

}

---