バイナリツリーレベルオーダーキューを使用したトラバーサル？

Question

私のコードで間違いを見つけるのを手伝ってください。 このプログラムでは、私はバイナリツリーを作成し、私は、キューを使用して、レベル順に移動したいと思います。

私の出力は最初の親ルートを印刷した後にスタックされています。私はキューの機能でいくつか間違いがあると思います。私は間違いを見つけることができません。ここ

は、以下の私のコードです：

---

   #include<stdio.h> 
       #include<stdlib.h> 
       struct node 
       { 
        int data; 
        struct node *left,*right; 
       }; 
       struct node* create_root(int data) 
       { 
       struct node *root=(struct node*)malloc(sizeof(struct node)); 
        root->data=data; 
        root->left=root->right=NULL; 
        return root; 
       } 
       struct node* create_tree(int data,struct node *root) 
       { 
        char ch; 
       if(root==NULL) 
         return create_root(data); 

        printf("\nEnter R/L of %d ? ",root->data); 
        fflush(stdin); 
        scanf("%c",&ch); 
        if(ch=='R' || ch=='r') 
         root->right=create_tree(data,root->right); 
        else 
         root->left=create_tree(data,root->left); 

       return root; 
       } 
       struct queue 
       { 
        struct node *info; 
        struct queue *next; 
       }; 
       struct queue *start=NULL; 
       struct queue* enQueue(struct node *root) 
       { 
        struct queue *new_node,*ptr; 
        new_node=(struct queue*)malloc(sizeof(struct queue)); 
        if(start==NULL) 
         start=new_node; 
        else 
        { 
         ptr=start; 
         while(ptr!=NULL) 
         { 
           if(ptr->next==NULL) 
           { 
            ptr->next=new_node; 
            new_node->next=NULL; 
           } 
         } 
        } 
        new_node->info=root; 
        return start; 
       } 
       struct queue* deQueue() 
       { 
       struct queue *temp; 
         if(start==NULL) 
         { 
          printf("\nEmpty!!!!!"); 
          return; 
         } 
         temp=start; 
         if(start->next==NULL) start=NULL; 
         else start=start->next; 
         return temp; 

       } 
       int isEmpty() 
       { 
        if(start==NULL) 
         return 1; 
        else 
         return 0; 
       } 
       void level_order(struct node *root) 
       { 
        struct queue *ptr; 
        if(root==NULL) 
        { 
         printf("\nEmpty!!!!!"); 
         return ; 
        } 
        start=enQueue(root); 
        while(!isEmpty()) 
        { 
         ptr=deQueue(); 
         printf("%d ",ptr->info->data); 

         if(ptr->info->left) 
          enQueue(ptr->info->left); 
         else if(ptr->info->right) 
          enQueue(ptr->info->right); 

        } 
       } 
       int main() 
       { 
        int n=0,num; 
        struct node *root=NULL; 
        printf("\nEnter data:"); 
        scanf("%d",&num); 
        root=create_tree(num,root); 
        while(n<5) 
        { 
        printf("\nEnter data:"); 
        scanf("%d",&num); 
        create_tree(num,root); 
        n++; 
        } 
        level_order(root); 
        return 0; 
       } 

Answer 1

エンキュー機能が壊れています：ptrがNULLになるまでループを続けますが、ループ内ではptrはまったく変更されません。

while(ptr!=NULL) 
    { 
      if(ptr->next==NULL) 
      { 
       ptr->next=new_node; 
       new_node->next=NULL; 
      } 
    } 

代わりに、あなたはその終わりに到達するまで反復ごとに一覧に進出する必要があります。

while(ptr!=NULL) 
    { 
      if(ptr->next==NULL) 
      { 
       ptr->next=new_node; 
       new_node->next=NULL; 
       break; 
      } 
      ptr = ptr->next; 
    } 

これは無限ループを修正する必要があります。

さらに、あなたはそれがstart == NULLの場合にも初期化持って、直接malloc()後new_node->nextへの初期化を移動する必要があります：

new_node=(struct queue*)malloc(sizeof(struct queue)); 
new_node->next = NULL; 
if(start==NULL) 
     start=new_node; 

Answer 2

level_orderは）（、それ自身への再帰呼び出しを行う必要がありエンキューしません。