Почему мои функции Preoder, Inorder и Postorder не работают

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

Создание узла

Эта структура создает тип данных struct node

 struct node
    {
        int data;
        struct node *left, *right;
    } * newnode;

Создать функцию

create() - Сначала он выделяет память, необходимую для узла. Когда пользователь вводит данные, он рекурсивно вызывает себя для создания своего дочернего узла, и этот процесс продолжается. Когда пользователь вводит -1, рекурсия завершается и возвращается из того места, где она была вызвана.

    struct node *create()
    {
        int x;
        newnode = (struct node *)malloc(sizeof(struct node));
        newnode->left = 0;
        newnode->right = 0;
        printf("Enter data(-1 for no node)\n");
        scanf("%d", &x);
        if (x == -1)
            return 0;
        newnode->data = x;
        printf("Enter left child of %d\n", x);
        newnode->left = create();
    
        printf("Enter right child of %d\n", x);
        newnode->right = create();
        return newnode;
    }

Предварительный заказ

preorder(struct node *root) - Эта функция отображает данные дерева в порядке предварительного заказа.

    void preorder(struct node *root)
    {
        if (root == 0)
            return;
    
        printf("%d\n", root->data);
        preorder(root->left);
        preorder(root->right);
    }

В целях

inorder(struct node *root) - Эта функция отображает данные дерева в неупорядоченном порядке

    void inorder(struct node *root)
    {
        if (root == 0)
            return;
    
        inorder(root->left);
        printf("%d\n", root->data);
        inorder(root->right);
    }

Почтовый заказ

Postorder(struct node *root) - Эта функция отображает данные дерева в обратном порядке.

    void postorder(struct node *root)
    {
        if (root == 0)
            return;
    
        postorder(root->left);
        postorder(root->right);
        printf("%d\n", root->data);
    }

Основная функция

Основная функция просит пользователя создать дерево, а затем пройти по нему в соответствии с выбором, введенным пользователем. Проблема в том, что preorder, inorder и postorder не дают требуемого результата и приводят к бесконечному циклу после выполнения.

 void main()
    {
        struct node *root;
        root = 0;
        int choice = 3, opt = 1;
    
        while (opt)
        {
            printf("Select\n 1-for creation\n 2-for preorder\n 3-for inorder\n 4-for postorder\n");
            scanf("%d", &choice);
            switch (choice)
            {
            case 1:
                root = create();
                break;
            case 2:
                printf("Preorder is: ");
                preorder(root);
                break;
            case 3:
                printf("Inorder is: ");
                inorder(root);
                break;
            case 4:
                printf("Postorder is: ");
                postorder(root);
                break;
    
            default:
                printf("Invalid choice");
                break;
            }
            printf("Wanna continue \n1-for yes\n0-for no\n");
            scanf("%d", &opt);
        }
    }

Kushagra Kukreti 13.05.2021 источник

Ответы (1)

arrow_upward
0
arrow_downward

Ни одна из предоставленных вами функций обхода не содержит ошибок. Также нет проблем с дизайном или реализацией функции create ().

Проблема заключается в глобальном struct node указателе newnode, объявленном с определением структуры.

Поскольку каждый рекурсивный вызов create () в основном использует один и тот же указатель newnode, дерево никогда не строится так, как мы хотим.

Давайте попробуем запустить функцию create () в пробном режиме.

Допустим, мы хотим такое дерево:

    1
   / \
  2   3

create () сначала вызывается из main.

Память выделяется с помощью функции malloc (), а адрес памяти сохраняется в newnode.
Установите его атрибуты, left и right.
Запросите data и поместите его в атрибут data, если data == -1 истинно, return 0.

До этого момента это состояние:

newnode -> 1
          / \
       Null  Null

create () рекурсивно вызывается для построения левого поддерева.

Память выделяется для newnode с помощью malloc (), а адрес памяти сохраняется в newnode. Обратите внимание, что эта операция фактически переписала адрес, ранее сохраненный в newnode (поскольку newnode является глобальной переменной).
Затем снова пользователю будет предложено ввести data, и будут установлены его атрибуты.

Поэтому дерево теперь стало:

newnode -> 2
          / \
       Null  Null

struct node, на который ранее указывал newnode, теперь потерян (из-за потери его адреса)

Точно так же при рекурсивном вызове правого поддерева будет наблюдаться следующее:

newnode -> 3
          / \
       Null  Null

Учитывая тот же сценарий для остальных сделанных рекурсивных вызовов, становится ясно, что в итоге дерево, которое мы ожидали, не было построено, и причина в глобальной переменной newnode, постоянном выделении память и перезапись адреса в newnode привели только к утечке памяти.

Причина, по которой была обнаружена бесконечная рекурсия, заключается в том, что во время нескольких рекурсивных вызовов указатель left или right newnode был сделан так, чтобы указывать на сам newnode, что приводило к циклу. Этот узел можно найти, внимательно отслеживая data из newnode во время рекурсивных вызовов.

Следовательно, удалите объявление указателя newnode из объявления структуры и измените следующий оператор в функции create ():

newnode = (struct node *)malloc(sizeof(struct node));

к этому:

struct node * newnode = (struct node *)malloc(sizeof(struct node));

А также

struct node
{
    int data;
    struct node *left, *right;
};

это все что нужно.

Таким образом, каждый рекурсивный вызов функции create () будет иметь свою собственную локальную переменную-указатель newnode, и не будет ни перезаписи, ни утечки, ни цикла, ни бесконечной рекурсии.

Sankalp Arora 16.05.2021