在 C 中使用队列的二叉树级别顺序遍历

Question

我是 C 的新手。我开始学习数据结构，并且对链表、堆栈和队列还不错。现在我正在实施 BST，它们似乎非常复杂。在这里，我尝试为 Level Order Transversal 编写代码，但没有获得所需的输出。
请帮我修复它。

没有显示错误。在运行程序中，我得到无限 'G' 作为我的输出。我希望以某种顺序打印所有字符（我在主函数中输入的字符）。

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

struct Node
{
    char data;
    struct Node* right;
    struct Node* left;

    };

void enq(struct Node* temproot);
struct Node* deq();
struct Node* Insert(struct Node* ,char x);
struct Node* newNode (char data);
void LevelOrder(struct Node* root);

struct Node* front = NULL;
struct Node* rear = NULL;

int main()
{

    struct Node* root;
    root = NULL;
    root = Insert(root,'F');
    root = Insert(root,'B');
    root = Insert(root,'C');
    root = Insert(root,'D');
    root = Insert(root,'E');
    root = Insert(root,'G');
    root = Insert(root,'A');
    root = Insert(root,'H');
    root = Insert(root,'I');
    LevelOrder(root);

    return 0;

    }

struct Node* Insert(struct Node* root,char x)
{
     if (root == NULL)
     {
         root = newNode(x); 
         }
    else if (x <= root->data)
    {
        root->left = Insert(root->left, x);
        }

    else
    {
        root->right = Insert(root->right,x);
        }
    return root;
}

struct Node* newNode(char x)
{
    struct Node* temp1 = (struct Node*)malloc(sizeof(struct Node)); 
    temp1->data = x;
    temp1->right = NULL;
    temp1->left = NULL;
    return  temp1;
    }


void enq(struct Node* temproot)
{
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->data = temproot->data;
    temp->right = temp->left= NULL;

    if(front == NULL && rear == NULL)
    {
        front = rear = temp;
        return;
        }
    rear->right = temp;
    rear = temp;
    }

struct Node* deq()
{
    struct Node* temp = front;
    if (front == NULL)
    {
        printf("The queue is empty!");
        }
    else if (rear == front)
    {

        front = rear = NULL;
        }
    else
    {
        front = front->right;
        }
    return temp;
    }

void LevelOrder(struct Node* root)
{
    struct Node* temproot = root;

    while(temproot != NULL)
    {
        printf("%c ", temproot->data);
        if(temproot->left != NULL)
        {enq(temproot->left);
            }
        if (temproot->right !=NULL)
        {enq(temproot->right);
            }
        temproot = deq();
        }
    }

Answer 1

如评论中所述，您需要将指向树结构中节点的指针排入队列——而不是数据。您可以通过使用 left 元素指向节点并使用 right 元素指向队列中的下一个项目来完成此操作。

我在评论里说：

I've not tested it, but maybe (just maybe), you need to replace
temp->data = temproot->data;
temp->right = temp->left= NULL;
in enq() with
temp->left = temproot;
temp->right = NULL;
and then in deq() you should have
struct Node *next = temp->left;
free(temp);
return next;

这似乎是正确的处方。这段代码有一个函数 dump_BST 可以将数据转储到树中以供调试（还有一个辅助函数 dump_BST_node() 可以在打印时实现预序遍历。

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

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

void enq(struct Node *temproot);
struct Node *deq(void);
struct Node *Insert(struct Node *, char x);
struct Node *newNode(char data);
void LevelOrder(struct Node *root);
void dump_BST(const char *tag, const struct Node *node);

struct Node *front = NULL;
struct Node *rear = NULL;

int main(void)
{
    struct Node *root = NULL;
    dump_BST("Empty", root);
    root = Insert(root, 'F');
    dump_BST("Added F", root);
    root = Insert(root, 'B');
    dump_BST("Added B", root);
    root = Insert(root, 'C');
    //dump_BST("Added C", root);
    root = Insert(root, 'D');
    //dump_BST("Added D", root);
    root = Insert(root, 'E');
    //dump_BST("Added E", root);
    root = Insert(root, 'G');
    //dump_BST("Added G", root);
    root = Insert(root, 'A');
    //dump_BST("Added A", root);
    root = Insert(root, 'H');
    //dump_BST("Added H", root);
    root = Insert(root, 'I');
    dump_BST("Added I", root);
    LevelOrder(root);

    return 0;
}

struct Node *Insert(struct Node *root, char x)
{
    if (root == NULL)
    {
        root = newNode(x);
    }
    else if (x <= root->data)
    {
        root->left = Insert(root->left, x);
    }

    else
    {
        root->right = Insert(root->right, x);
    }
    return root;
}

struct Node *newNode(char x)
{
    struct Node *temp1 = (struct Node *)malloc(sizeof(struct Node));
    temp1->data = x;
    temp1->right = NULL;
    temp1->left = NULL;
    return temp1;
}

void enq(struct Node *temproot)
{
    struct Node *temp = (struct Node *)malloc(sizeof(struct Node));
    temp->right = NULL;
    temp->left = temproot;
    temp->data = 'Z';

    if (front == NULL && rear == NULL)
    {
        front = rear = temp;
    }
    else
    {
        rear->right = temp;
        rear = temp;
    }
}

struct Node *deq(void)
{
    struct Node *temp = front;
    if (front == NULL)
    {
        printf("The queue is empty!\n");
    }
    else if (rear == front)
    {
        front = rear = NULL;
    }
    else
    {
        front = front->right;
    }
    struct Node *next = (temp == NULL) ? NULL : temp->left;
    free(temp);
    return next;
}

void LevelOrder(struct Node *root)
{
    struct Node *temproot = root;

    while (temproot != NULL)
    {
        printf("%c ", temproot->data);
        if (temproot->left != NULL)
        {
            enq(temproot->left);
        }
        if (temproot->right != NULL)
        {
            enq(temproot->right);
        }
        temproot = deq();
    }
    putchar('\n');
}

static void dump_BST_nodes(const struct Node *node)
{
    if (node != NULL)
    {
        printf("Node: '%c' (ptr = %p, left = %p, right = %p)\n",
                node->data, (void *)node, (void *)node->left, (void *)node->right);
        dump_BST_nodes(node->left);
        dump_BST_nodes(node->right);
    }
}

void dump_BST(const char *tag, const struct Node *node)
{
    printf("%s:\n", tag);
    dump_BST_nodes(node);
    printf("%s: end\n", tag);
}

当运行时，会产生：

Empty:
Empty: end
Added F:
Node: 'F' (ptr = 0x7fc63fc02750, left = 0x0, right = 0x0)
Added F: end
Added B:
Node: 'F' (ptr = 0x7fc63fc02750, left = 0x7fc63fc02770, right = 0x0)
Node: 'B' (ptr = 0x7fc63fc02770, left = 0x0, right = 0x0)
Added B: end
Added I:
Node: 'F' (ptr = 0x7fc63fc02750, left = 0x7fc63fc02770, right = 0x7fc63fc027f0)
Node: 'B' (ptr = 0x7fc63fc02770, left = 0x7fc63fc02810, right = 0x7fc63fc02790)
Node: 'A' (ptr = 0x7fc63fc02810, left = 0x0, right = 0x0)
Node: 'C' (ptr = 0x7fc63fc02790, left = 0x0, right = 0x7fc63fc027b0)
Node: 'D' (ptr = 0x7fc63fc027b0, left = 0x0, right = 0x7fc63fc027d0)
Node: 'E' (ptr = 0x7fc63fc027d0, left = 0x0, right = 0x0)
Node: 'G' (ptr = 0x7fc63fc027f0, left = 0x0, right = 0x7fc63fc02830)
Node: 'H' (ptr = 0x7fc63fc02830, left = 0x0, right = 0x7fc63fc02850)
Node: 'I' (ptr = 0x7fc63fc02850, left = 0x0, right = 0x0)
Added I: end
F B G A C H D I E The queue is empty!

您需要清理代码 — 队列为空的消息很麻烦，您不需要调试打印。但这确实显示了我是如何着手检查代码的（事实上它第一次运行正常是一个意想不到但令人愉快的收获）。

在 C 中使用队列的二叉树级别顺序遍历

Binary Tree Level Order Traversal Using Queue in C

c

binary-tree

data-structures