树：使用队列进行层序遍历

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 循环的条件是：

while (tmp != NULL) {

所以它只会在 dequeue returns NULL 这里终止：

    tmp = dequeue();

但这不可能发生，当查看 dequeue 的实现时：

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

在这里，p 被取消引用：

    head = p->next;

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

在这里，p 是 returned:

    return p;
}

到 return 一个 NULL 指针并离开你的 while 循环，p 必须在这里 NULL。但是，NULL 指针之前会被 head = p->next; 取消引用，这将导致分段错误（C 语言中的 UB）。

如果 head 是 NULL 指针并且在这种情况下 return NULL：

，您应该在 dequeue-function 的开头检查

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

...

树：使用队列进行层序遍历

Tree: Level order Traversal using queue

c

tree