Csu——计算机上机实验 YJQ
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
目：层次遍历
算法思想：
1.建立一个二叉树。以广义表的形式表示法的字符串str[]去生成对应的链式二叉树存储结构。使用一个栈stack保存当前二叉树的根节点，top为其栈指针，k指定其后处理的节点是双亲节点（保存在栈中），左（k=1）还是右孩子（k=2），ch为当前处理的str中的字符。如果ch=’(’，
则将创建的节点作为双亲节点进栈，并置k=1，其后创建的节点作为做孩子；如果ch=’，’，表示其后创建的节点为其右孩子，并置k=2；如果ch=’）’，则表示左右节点处理完毕，退栈；其他情况表示要创建一个节点，并根据k的值建立它与栈中节点之间的联系。如此循环，直到str处理完毕。
2.层次遍历。使用一个循环队列qu[ ],先将二叉树的根节点入队。当队列不为空时循环（队空条件：rear= =front），从队列中取出一个节点，访问并打印这个节点，，将其不空的左儿子和右儿子入队。
代码如下：
#include
#include
#define maxsize 20
typedef struct node{
char data;
struct node *lchild;
struct node *rchild;
}Btree; //定义二叉树结点
Btree * creatree(Btree * root,char * str);//创建二叉树
void level(Btree *root);//层次遍历
void main(){
Btree * root=NULL;
char * str="(0(3(4,2),1))";
root = creatree(root,str);
cout<<"层次遍历结果：";
level(root);
}
Btree * creatree(Btree * root,char * str){
Btree * stack[maxsize];
Btree *p=NULL;
int top=-1,k,j=0;
char ch;
ch=str[j];
while(ch!='\0'){
switch(ch){
case'(':top++;stack[top]=p;k=1;break; //为左节点
case',':k=2;break; //为右节点
case')':top--;break;
default:p=(Btree *)malloc(sizeof(Btree)); //为节点分配空间
p->data=ch;
p->lchild=NULL;
p->rchild=NULL;
if(root==NULL) root=p; //根节点
else {
switch(k){
case 1:stack[top]->lchild=p;break;
case 2:stack[top]->rchild=p;break;
}
}
}
j++;ch=str[j];
}
return root;
}
void level(Btree * root){
Btree *qu[maxsize]; //构造一个循环队列
Btree *p;
int rear=0,front=0;
rear++;qu[rear]=root; //根节点入队
while(front!=rear){ //队列不为空时循环
front=(front+1)%maxsize;
p=qu[front]; //出对一个节点
cout<<"V"<data<<"\t";
if(p->lchild!=NULL){ //左节点入队
rear=(rear+1)%maxsize;
qu[rear]=p->lchild;
}
if(p->rchild!=NULL){ //右节点入队
rear=(rear+1)%maxsize;
qu[rear]=p->rchild;
}
}
}
运行结果：
浙公网安备 33021202002483