按层次遍历二叉树算法

[html] view plaincopy

1. #define MaxSize 1000  
2. typedef char ElemType;   
3. typedef struct node   
4. {  
5.     ElemType data;  
6.     struct node *lchild;  
7.     struct node *rchild;  
8. } BTNode;  
9. //创建二叉树  
10. void CreateBTNode(BTNode *&b,char *str)  
11. {  
12.     BTNode *St[MaxSize],*p=NULL;  
13.     int top=-1,k,j=0;  
14.     char ch;  
15.     b=NULL;  
16.     ch=str[j];  
17.     while(ch!='\0')  
18.     {  
19.         switch(ch)  
20.         {  
21.         case '(':top++;St[top]=p;k=1;break;  
22.         case ')':top--;break;  
23.         case ',':k=2;break;  
24.         default:p=(BTNode *)malloc(sizeof(BTNode));  
25.             p->data=ch;p->lchild=p->rchild=NULL;  
26.             if(b==NULL) b=p;  
27.             else  
28.             {  
29.                 switch(k)  
30.                 {  
31.                 case 1:St[top]->lchild=p;break;  
32.                 case 2:St[top]->rchild=p;break;  
33.                 }      
34.             }      
35.         }      
36.         j++;  
37.         ch=str[j];  
38.     }      
39. }  
40. //层次遍历算法   
41. void LevelOrder(BTNode *b)  
42. {  
43.     BTNode *p;  
44.     BTNode *qu[MaxSize];  
45.     int front,rear;  
46.     front=rear=-1;  
47.     rear++;  
48.     qu[rear]=b;  
49.     while(front != rear)  
50.     {  
51.         front=(front+1)%MaxSize;  
52.         p=qu[front];  
53.         printf("%c ",p->data);  
54.   
55.         if(p->lchild!=NULL)  
56.         {  
57.             rear=(rear+1)%MaxSize;  
58.             qu[rear]=p->lchild;  
59.         }  
60.   
61.         if(p->rchild!=NULL)  
62.         {  
63.             rear=(rear+1)%MaxSize;  
64.             qu[rear]=p->rchild;  
65.         }  
66.     }  
67. }  
68.   
69. //主函数  
70. int main()  
71. {  
72.     BTNode *b,*h;  
73.     char s[MaxSize] = "A(B(D(,G)),C(E,F))";  
74.   
75.     CreateBTNode(b,s);  
76.     printf("层次遍历算法的访问次序为：");  
77.     LevelOrder(b);  
78.     printf("\n请输入二叉树括号表示法字符串：\n");  
79.     return 0;  
80. }