Обход дерева порядка уровней в C с использованием очередей

Question

Я пытаюсь реализовать алгоритм обхода порядка уровней в двоичном дереве с использованием очереди (очередь реализована с использованием связанных списков). Он должен распечатать все узлы в дереве, но по какой-то причине я не могу понять, на выходе - только данные root. Если бы вы могли мне помочь, я был бы очень признателен! Вот мой код: `

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

typedef struct BSTNode{
    int data;
    struct BSTNode* left;
    struct BSTNode* right;
} bstNode;

/* Queue */
typedef struct queueNode{
    bstNode* node;
    struct queueNode* next;
} qNode;

typedef struct Queue
{
    qNode* head;
    qNode* end;
} queue;



bstNode* getNewNode(int data){
    bstNode* newNode = (bstNode*)malloc(sizeof(bstNode));
    if(!newNode)
        return NULL;
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}

void insertBSTNode(bstNode** root, int data){
    if(*root == NULL){ // empty tree
        *root = getNewNode(data);}
    else if((*root)->data >= data)
        insertBSTNode(&((*root)->left), data);
    else insertBSTNode(&((*root)->right), data);
}


queue* initQ(){
    queue* q = (queue*)malloc(sizeof(queue));
    if(!q) return NULL;
    q->head = NULL;
    q->end = NULL;

    return q;
}

qNode* allocNewQNode(bstNode* root)
{
    qNode* newNode = (qNode*)malloc(sizeof(qNode));
    if (!newNode) return NULL;
    newNode->node = (bstNode*)malloc(sizeof(bstNode));
    if(!newNode->node){ 
        free(newNode);
        return NULL;
    }
    //memcpy(newNode->node, root, sizeof(bstNode));
    newNode->node->data = root->data;
    newNode->node->left = root->left;
    newNode->node->right = root->right;
    newNode->next = NULL;

    return newNode;
}

void enqueue(queue* q, bstNode* root)
{
    qNode* tmp = allocNewQNode(root);
    if(q->head == NULL && q->end == NULL){

        q->head = tmp;
        q->end = tmp;
        return;
    }
    else{
        q->end->next = tmp;
        q->end = tmp;
        return;
    }

}

qNode* dequeue(queue* q)
{   
    if(q->head == NULL) return NULL;
    qNode* tmp = allocNewQNode(q->head->node);
    qNode* aux = NULL;
    q->head->node = NULL;

    aux = q->head;
    q->head = q->head->next;
    free(aux);

    return tmp;

}

void levelOrder(bstNode* root)
{
    if(root == NULL) return;
    else
    {
        queue* q = initQ();
        enqueue(q, root);
        while(q->head != NULL){
            qNode* tmp = dequeue(q);
            printf("%d ", tmp->node->data);
            if (tmp->node->right != NULL){
                enqueue(q, tmp->node->right);
            }
            if(tmp->node->left != NULL){
                enqueue(q, tmp->node->left);
            }
        }
    }

}

int main(){

    bstNode* root = NULL;
        insertBSTNode(&root, 2);
        insertBSTNode(&root, 7);
        insertBSTNode(&root, 5);
        insertBSTNode(&root, 6);
        insertBSTNode(&root, 9);
        insertBSTNode(&root, 128);
        insertBSTNode(&root, 223);
        insertBSTNode(&root, 357);


    levelOrder(root);
    return 0;
}

`

Answer 1

Для вставленных данных у вас должно быть следующее двоичное дерево поиска

2
 \
  7
 / \
5   9
\    \
 6    128
       \
       223
        \
        357 

, а обход дерева в порядке уровней должен выглядеть так:

2 7 5 9 6 128 223 357 

Создавая очередь, вы должны не выделять динамически копии узлов двоичного дерева поиска.

В противном случае, например, функция dequeue вызывает многочисленные утечки памяти в таких операторах, как

q->head->node = NULL;

, или возвращает и создает еще один узел типа qNode не освобождается в функции levelOrder.

Также вы не устанавливаете член данных end на NULL после этого оператора

q->head = q->head->next; 

, когда очередь содержала только один узел.

И нет необходимости определять саму очередь динамически.

Вот демонстрационная программа, которая показывает, как функции могут быть определены с использованием вашего подхода.

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

typedef struct BSTNode
{
    int data;
    struct BSTNode *left;
    struct BSTNode *right;
} bstNode;

/* Queue */
typedef struct queueNode
{
    bstNode* node;
    struct queueNode *next;
} qNode;

typedef struct Queue
{
    qNode *head;
    qNode *end;
} queue;

bstNode * getNewNode( int data )
{
    bstNode* newNode = malloc( sizeof( bstNode ) );

    if ( newNode != NULL )
    {
        newNode->data  = data;
        newNode->left  = NULL;
        newNode->right = NULL;
    }

    return newNode;
}

int insertBSTNode( bstNode **root, int data )
{
    return *root == NULL 
           ? ( *root = getNewNode( data ) ) != NULL
           : ( data < ( *root )->data 
               ? insertBSTNode( &( *root )->left, data )
               : insertBSTNode( &( *root )->right, data ) );
}

void initQ( queue *q )
{
    q->head = NULL;
    q->end  = NULL;
}

qNode * allocNewQNode( bstNode *node )
{
    qNode *newNode = malloc( sizeof( qNode ) );

    if ( newNode != NULL )
    {
        newNode->node = node;
        newNode->next = NULL;
    }

    return newNode;
}

void enqueue( queue *q, bstNode *node )
{
    qNode *tmp = allocNewQNode( node );

    if ( q->head == NULL )
    {
        q->head = q->end = tmp;
    }
    else
    {
        q->end = q->end->next = tmp;
    }
}

bstNode * dequeue( queue *q )
{
    bstNode *node = q->head == NULL ? NULL : q->head->node;

    if ( q->head != NULL )
    {
        qNode *tmp = q->head;
        q->head = q->head->next;

        free( tmp );

        if ( q->head == NULL ) q->end = NULL;
    }

    return node;    
}

void levelOrder( bstNode *root )
{
    if ( root != NULL )
    {
        queue q;
        initQ( &q );

        enqueue( &q, root );

        while ( q.head != NULL )
        {
            bstNode *tmp = dequeue( &q );

            printf( "%d ", tmp->data );

            if ( tmp->left != NULL )
            {
                enqueue( &q, tmp->left );
            }

            if ( tmp->right != NULL )
            {
                enqueue( &q, tmp->right );
            }
        }
    }
}

int main(void) 
{
    bstNode *root = NULL;

    insertBSTNode( &root, 2 );
    insertBSTNode( &root, 7 );
    insertBSTNode( &root, 5 );
    insertBSTNode( &root, 6 );
    insertBSTNode( &root, 9 );
    insertBSTNode( &root, 128 );
    insertBSTNode( &root, 223 );
    insertBSTNode( &root, 357 );

    levelOrder( root );

    putchar( '\n' );

    return 0;
}

Вывод программы

2 7 5 9 6 128 223 357