BST 的层序遍历

Question

我的程序没有给出所需的输出。请检查。我正在做的是，我首先构建队列，然后按照队列中提到的顺序打印每个节点。

期望的输出应该是 F D J B E G K A C I H。我得到的输出是 F D J B A C。

#include <stdio.h>
#include <stdlib.h>

struct node
{
    char data;
    struct node *left;
    struct node *right;
};

struct queue
{
    struct node *root;
    struct queue *next;
};

struct queue *head;

struct node* newnode(char c)
{
    struct node *n = (struct node*)malloc(sizeof(struct node));
    n->data = c;
    n->left = NULL;
    n->right = NULL;
    return n;
}

void enqueue(struct node *tree)
{
     if(head == NULL)
     {
        struct queue *n = (struct queue*)malloc(sizeof(struct queue));
        n->root = tree;
        n->next = NULL;
        head = n; 
     }
     else
     {
         struct queue *p = head;
         while(p->next != NULL)
         {
             p = p->next;
         }
         struct queue *n = (struct queue*)malloc(sizeof(struct queue));
         n->root = tree;
         n->next = NULL;
         p->next = n;
     }
}

void traverse(struct node *tree)
{
    if(tree != NULL)
    {
        enqueue(tree->left);
        enqueue(tree->right);
        traverse(tree->left);
        traverse(tree->right);
    }
}

void display()
{
    struct queue *p = head;
    while(p->next != NULL)
    {
        printf("%c ",p->root->data);
        p = p->next;
    }
    printf("%c \n",p->root->data);
}

int main()
{
    struct node *root = newnode('F');
    root->left = newnode('D');
    root->right = newnode('J');
    root->left->left = newnode('B');
    root->left->right = newnode('E');
    root->right->left = newnode('G');
    root->right->right = newnode('K');
    root->left->left->left = newnode('A');
    root->left->left->right = newnode('C');
    root->right->left->left = newnode('I');
    root->right->left->left->right = newnode('H');
    enqueue(root);
    traverse(root);
    display();
    return 0;
}

Answer 1

traverse函数中的几个问题：

enqueue(tree->left) 最终会将 NULL 添加到队列中，这将导致 display 函数出现问题，预计所有 p 有一个非 NULL p->root 成员。
它不执行逐级遍历。它更像是深度优先遍历（在遍历直接兄弟之后）。在层序遍历中，没有递归。您应该迭代队列（随着队列的增长而落后），以获取 tree.
的值

这是对 traverse 的更正：

void traverse(struct node *tree)
{
    struct queue *current = head;
    while (current != NULL)
    {
        tree = current->root;
        if (tree->left != NULL) enqueue(tree->left);
        if (tree->right != NULL) enqueue(tree->right);
        current = current->next; // Walk along the queue while it is being built
    }
}

BST 的层序遍历

Level Order Traversal of BST

c

tree