C语言按层次遍历二叉树算法详解编程语言

#define MaxSize 1000 
typedef char ElemType; 
typedef struct node 
{ 
    ElemType data; 
    struct node *lchild; 
    struct node *rchild; 
} BTNode; 
//创建二叉树 
void CreateBTNode(BTNode *&b,char *str) 
{ 
    BTNode *St[MaxSize],*p=NULL; 
    int top=-1,k,j=0; 
    char ch; 
    b=NULL; 
    ch=str[j]; 
    while(ch!='/0') 
    { 
        switch(ch) 
        { 
        case '(':top++;St[top]=p;k=1;break; 
        case ')':top--;break; 
        case ',':k=2;break; 
        default:p=(BTNode *)malloc(sizeof(BTNode)); 
            p->data=ch;p->lchild=p->rchild=NULL; 
            if(b==NULL) b=p; 
            else 
            { 
                switch(k) 
                { 
                case 1:St[top]->lchild=p;break; 
                case 2:St[top]->rchild=p;break; 
                }    
            }    
        }    
        j++; 
        ch=str[j]; 
    }    
} 
//层次遍历算法 
void LevelOrder(BTNode *b) 
{ 
    BTNode *p; 
    BTNode *qu[MaxSize]; 
    int front,rear; 
    front=rear=-1; 
    rear++; 
    qu[rear]=b; 
    while(front != rear) 
    { 
        front=(front+1)%MaxSize; 
        p=qu[front]; 
        printf("%c ",p->data); 
  
        if(p->lchild!=NULL) 
        { 
            rear=(rear+1)%MaxSize; 
            qu[rear]=p->lchild; 
        } 
  
        if(p->rchild!=NULL) 
        { 
            rear=(rear+1)%MaxSize; 
            qu[rear]=p->rchild; 
        } 
    } 
} 
  
//主函数 
int main() 
{ 
    BTNode *b,*h; 
    char s[MaxSize] = "A(B(D(,G)),C(E,F))"; 
  
    CreateBTNode(b,s); 
    printf("层次遍历算法的访问次序为："); 
    LevelOrder(b); 
    printf("/n请输入二叉树括号表示法字符串：/n"); 
    return 0; 
}