Дерево: порядок уровней Обход с использованием очереди

Question

Я написал коды, которые пересекают дерево, используя очередь, но функция dequeue ниже генерирует ошибку. Есть ли проблемы с head = p->next? Я не могу понять, почему эта часть неверна.

void Levelorder(void) { 
node *tmp, *p; 


if (root == NULL) return; 

tmp = root; 
printf("The level order is :\n"); 

while (tmp != NULL) { 

    printf("%d, ", tmp->data); 
    if (tmp->left) { 
     enqueue(tmp->left); 
    } 
    if (tmp->right) { 
     enqueue(tmp->right); 
    } 
    tmp = dequeue(); 
} 

return; 
} 

void enqueue(node *p) { 
if (head == NULL) { 
    head = p; 
} 
else { 
    tail->next = p; 
} 
tail = p; 
p->next = NULL; 
tail->next = NULL; 

return; 
} 

node* dequeue(void) { 
node *p; 
p = head; 
head = p->next; 


if (head == NULL) { 
    tail == NULL; 
} 

return p; 
} 

Answer 1

Состояние вашего время цикла является:

while (tmp != NULL) { 

Так закончится только тогда, когда dequeue возвращается NULL здесь:

tmp = dequeue(); 

Но это не может произойти, если смотреть на реализацию dequeue:

node* dequeue(void) { 
    node *p; 
    p = head; 

Здесь p разыменовывается:

head = p->next; 

    if (head == NULL) { 
     tail == NULL; 
    } 

И здесь, p возвращается:

return p; 
} 

Чтобы вернуть NULL указатель и оставить свой While-цикл, p должен был быть NULL здесь. Но тогда указатель NULL будет разыменован head = p->next;, что приведет к ошибке сегментации (UB с точки зрения языка C).

Вы должны проверить в начале вашего DEQUEUE-функции, если head является указателем NULL и возвращать NULL в этом случае:

node* dequeue(void) { 
    node *p; 
    if (!head) 
     return NULL; 

...