二叉树级别的顺序使用队列遍历？

Question

请帮我找到我的代码中的错误。 在这个程序中，我创建了一个二叉树，我想使用队列按层次顺序遍历。

我的输出在打印第一个父根后停滞不前。我认为在Queue函数中有一些错误，但我无法找到任何错误。

这里是我下面的代码：

---

   #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; 
    } 

这应该可以解决的死循环。

此外，你应该malloc()后直接将初始化new_node->next来，有它在start == NULL的情况下也被初始化：

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

Answer 2

level_order应该递归调用本身，而不是排队（）。