sss.cpp

这是一个用C++编写的二叉树的按层遍历程序

#include <iostream.h> 
typedef char elemtype; 
struct bitree 
{ 
elemtype data ; 
bitree *lchild,*rchild; 
}; 
bitree *create() //建立叉链表 
{ 
bitree *root; //二叉链表的根指针 
bitree *s; //二叉链表中的节点 
bitree *q[100]; //定义q数组作为队列存放二叉链表中的节点，100为最大容量 
int front=1,rear=0; //定义队列的头、尾指针 
char ch; //节点的data域值 
root=NULL; 
cout<<"请输入节点值，(','为虚节点,'#'结束)"<<endl; 
cin>>ch; 
while(ch!='#') //输入值为#，算法结束 
{ 
s=NULL; 
if(ch!=',') //输入数据不为逗号，表示不为虚节点，否则为虚节点 
{ 
s=new bitree; 
s->data=ch; 
s->lchild=NULL; 
s->rchild=NULL; 
} 
rear++; //新节点或虚节点进队 
q[rear]=s; 
if (rear==1) root=s; 
else 
{ 
if((s!=NULL)&&(q[front]!=NULL)) 
{ 
if(rear%2==0) 
q[front]->lchild=s; //real为偶数，s为双亲左孩子 
else q[front]->rchild=s; //real为偶数，s为双亲右孩子 
} 
if(rear%2==1) 
front++; //出队 
} 
cin>>ch; 
} 
return root; 
} 

void lorder(bitree *t) //按层次遍历二叉树 
{ 
bitree *q[100],*p; //q代表队列 
int f,r; //f，r类似队列头指针，尾指针 
q[1]=t; 
f=r=1; 
cout<<"按层次遍历二叉树的结果为："; 
while(f<=r) 
{ 
p=q[f]; 
f++; //出队 
cout<<p->data<<" "; 
if(p->lchild!=NULL) 
{ 
r++; //入队 
q[r]=p->lchild; 
} 
if(p->rchild!=NULL) 
{ 
r++; //入队 
q[r]=p->rchild; 
} 
} 
cout<<endl; 
} 

void perorderl(bitree *t) //先序遍历 
{ 
bitree *p,*s[100]; //s为堆栈 
int top=0; //top为栈顶指针 
p=t; 
cout<<"按先序遍历二叉树的结果为："; 
while((p!=NULL)||(top>0)) 
{ 
while(p!=NULL) 
{ 
cout<<p->data<<" "; 
s[++top]=p; //进栈 
p=p->lchild; 
} 
p=s[top--]; //退栈 
p=p->rchild; 
} 
} 

void main() 
{ 
bitree *t; 
t=create(); //建立二叉链表 
lorder(t);cout<<endl; //调用层次遍历函数 
perorderl(t); cout<<endl; //调用先序遍历函数
}