Обход порядка двоичного дерева с использованием очереди в C - PullRequest
Новая
       44

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

0 голосов
/ 12 июня 2018

Я довольно новичок в C. Я начал изучать структуры данных и был в порядке со связанными списками, стеками и очередями.Сейчас я внедряю BST, и они кажутся довольно сложными.Здесь я попытался написать код для Transverseal Level Order, и я не получаю требуемый вывод. Пожалуйста, помогите мне исправить это. Это не показало ошибок.Запустив программу, я получаю бесконечный «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();
        }
    }

1 Ответ

0 голосов
/ 12 июня 2018

Как отмечено в комментариях, вам нужно ставить указатели на узлы в древовидных структурах, а не на данные.Вы можете сделать это, используя элемент left для указания на узел и элемент right для указания на следующий элемент в очереди.

В комментариях я сказал:

Я не проверял это, но, может быть (просто возможно), вам нужно заменить 

temp->data = temproot->data;
temp->right = temp->left= NULL;

в enq() на 

temp->left = temproot;
temp->right = NULL;

, а затем в deq() у вас должно быть 

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!

Вам нужно будет очистить код - сообщение о том, что очередь пуста, является неудобством, и вам не понадобится отладочная печать. Но это показывает, как я поступилпроверка кода (тот факт, что он работал нормально с первого раза был неожиданным, но приятным бонусом).

...