c - 二叉搜索树 - C 中的层序遍历

Question

我正在尝试使用队列在二叉搜索树中进行级别顺序遍历的代码，但我不知道为什么当我尝试打印级别顺序时没有得到任何输出。请有人帮忙!

Link to my code.

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

typedef struct 
{
    int data;
    struct Node *right, *left;
}Node;

typedef struct
{
    int front, rear, size;
    unsigned capacity;
    Node* arr[100];
}Queue;

Queue* createQ()
{
    Queue* q = (Queue*) malloc(sizeof(Queue));
    q->capacity = 100;
    q->front = q->size = 0; 
    q->rear = q->capacity - 1;
    return q;
}

int isEmpty(Queue* q)
{  
    return (q->size == 0); 
}
int isFull(Queue* q)
{  
    return (q->size == q->capacity);  
}
void enqueue(Queue* q, Node* item)
{
    if (isFull(q))
        return;
    q->rear = (q->rear + 1)%q->capacity;
    q->arr[q->rear] = item;
    q->size = q->size + 1;
 }


Node* dequeue(Queue* q)
{
    if (isEmpty(q))
        return NULL;
    Node* item = q->arr[q->front];
    q->front = (q->front + 1)%q->capacity;
    q->size = q->size - 1;
    return item;
}

Node* create(Node* root, int data)
{
    if(root==NULL)
    {
        root = (Node*)malloc(sizeof(Node));
        root->data = data;
        root->left = root->right = NULL;
        return root;
    }
    else
    {
        if(data>root->data)
        {
            root->right = create(root->right,data);
        }
        else
        {
            root->left = create(root->left,data);
        }
        return root;
    }
}
void levelorder(Node* root)
{
    if(root==NULL) return;
    else
    {
        Queue* q = createQ();
        enqueue(q,root);
        while(isEmpty(q))
        {
            Node* temp = dequeue(q);
            printf("%d ",temp->data);
            if(temp->right)
                enqueue(q,temp->right);
            else if(temp->left);
                enqueue(q,temp->left);
        }
    }
}

void main()
{
    int data;
    Node *root = NULL;
    for(;;)
    {
        printf("\nEnter the elements (-1 to stop) : ");
        scanf("%d",&data);
        if(data==-1) break;
        root = create(root,data);
    }
    printf("\nPrinting the elemtents in level order : ");
    levelorder(root);
}

Answer 1

您的 levelorder 函数中有几个错误。请检查下面的更正。我已将您的错误行保留在旁注中。

void levelorder(Node* root)
{
    if(root==NULL) return;
    else
    {
        Queue* q = createQ();
        enqueue(q,root);
        while(!isEmpty(q)) // not while(isEmpty(q)) you have to check untill Queue is non-empty
        {
            Node* temp = dequeue(q);
            printf("%d ",temp->data);
            if(temp->right)
                enqueue(q,temp->right);
            if(temp->left)  // not else if(temp->left); there can be right node and left node as well.. no semicolon
                enqueue(q,temp->left);
        }
    }
}

其余代码没问题。您应该使用一些知名的 IDE 自行练习调试。