-1
#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 15

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

typedef struct {
    int data[MAX_QUEUE_SIZE];
    int front, rear;
}queue;

void init_q(queue* q)
{
    q->front = 0;
    q->rear = 0;
}

int is_empty(queue* q)
{
    return (q->front == q->rear);
}

int is_full(queue* q)
{
    return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}

void enqueue(queue* q, int data)
{
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    q->data[q->rear] = data;
}

int dequeue(queue* q)
{
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    return q->data[q->front];
}

Node* insertBST(Node* root, int data) {
    Node* p = root;
    Node* parent = NULL;
    while (p != NULL) {
        parent = p;
        if (p->data < data) {
            p = p->right;
        }
        else {
            p = p->left;
        }
    }
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode != NULL)
    {
        newNode->data = data;
    }
    
    newNode->left = newNode->right = NULL;

    if (parent != NULL) {
        if (parent->data < newNode->data) {
            parent->right = newNode;
        }
        else {
            parent->left = newNode;
        }
    }
    return newNode;
};

void Inorder(Node* root, queue* q) {
    if (root == NULL) {
        return;
    }
    else
    {
        Inorder(root->left, q);
        enqueue(q, root->data);
        //printf("%d", root->data);
        Inorder(root->right, q);
    }

    printf("Inorder Traversal : ");
    while (!is_empty(q))
    {
        printf("%d ", dequeue(q));
    }
    printf("\n");    
}

int main()
{
    queue* q;
    init_q(&q);
    Node* root = NULL;
    root = insertBST(NULL, 6);
    insertBST(root, 2);
    insertBST(root, 7);
    insertBST(root, 1);
    insertBST(root, 4);
    insertBST(root, 3);
    insertBST(root, 5);
    Inorder(root, &q);
    return 0;
}

Structure of Binary Search Tree what I made :

             6
          2     7
        1   4 
           3 5

So the result what I expected is : Inorder Traversal : 1 2 3 4 5 6 7

But the result seems broken as below : Inorder Traversal : -858993460 -858993460 -858993460 -858993460 -858993460 -858993460 -24257920 390 -858993460 -858993460 -858993460 -858993460 -858993460 1 Inorder Traversal : -858993460 -858993460 -858993460 -858993460 -858993460 -24257920 390 -858993460 -858993460 -858993460 -858993460 -858993460 3 Inorder Traversal : -858993460 -858993460 -858993460 -858993460 -858993460 -24257920 390 -858993460 -858993460 -858993460 -858993460 -858993460 5 Inorder Traversal : Inorder Traversal : Inorder Traversal : -858993460 -858993460 -858993460 -858993460 -858993460 -24257920 390 -858993460 -858993460 -858993460 -858993460 -858993460 7 Inorder Traversal :

It seems I made a mistake in inorder function (a recursive doesn't work well I guess)

and the pointer issue maybe I guess.

What did I wrong and how should I modify my code? (I will try to implement postorder and preorder after modify this code.)

Thanks for your help.

bFur4list
  • 133
  • 3

1 Answers1

0

There are these issues:

  • The declaration of q in main should be queue q instead of queue *q. The insertBST expects as second argument a queue* not a queue**. Most IDE's will give a warning about that mistake.

  • The implementation of enqueue is moving the wrong index. It should move rear instead of front.

Not a major problem, but:

  • It seems likely you want to print the queue after having called Inorder, not during. I would suggest creating a separate function for printing the queue.

  • When calling malloc don't cast. Do as follows

    Node* newNode = malloc(sizeof(*newNode)); // Don't cast

  • When malloc fails, your code protects the assignment to root->data, but then let's the execution continue to set root->left, ...etc. Instead, you could exit:

    if (newNode == NULL) exit(1); // When malloc fails
trincot
  • 317,000
  • 35
  • 244
  • 286