Как вставить элементы в дерево бинарного поиска после ввода корневого элемента?

Question

Я писал C-программу для Binary Search Tree, в которой в качестве глобальной переменной использовался только root, а для вставки элементов использовалась рекурсия.

struct Node {
    int data;
    struct Node *left, *right;
} *root = NULL;
typedef struct Node *node;

void insert(node ptr, int value) {
    if (ptr == NULL) {
        ptr = (node)malloc(sizeof(node));
        ptr->data = value;
        ptr->left = NULL;
        ptr->right = NULL;
        if (root == NULL)
            root = ptr;
    }
    else if (value < ptr->data) {
        ptr = ptr->left;
        insert(ptr, value);
    }
    else {
        ptr = ptr->right;
        insert(ptr, value);
    }
}

И соответствующий ему блок главной функции:

case 1 :
    printf("\n\t\tEnter a number to insert into the tree : ");
    scanf("%d", &input);
    insert(root, input);
    break;

Функция дисплея:

void inOrderTraversal(node ptr) {
    if (ptr != NULL) {
        inOrderTraversal(ptr->left);
        printf("->%d\t", ptr->data);
        inOrderTraversal(ptr->right);
    }
}

Когда я вызываю функцию дисплея, используяпри любом обходе печатается только корневой элемент. Почему ссылки не создаются?

Answer 1

ptr = (node)malloc(sizeof(node)); не устанавливает аргумент callers ;он устанавливает локальную переменную. Кроме того, сокрытие типов указателей в псевдонимах typedef рекомендуется только в двух условиях (API дескриптора черного ящика и типы функций обратного вызова), ни один из которых не является вашим случаем. Этот псевдоним на самом деле делает ваш код труднее для чтения;не прощеПрограммисты C хотят видеть звездочки указателей, независимо от того, сколько уровней косвенности задействовано.

Предполагается, что структура вашего узла выглядит следующим образом:

typedef struct NODE {
    int data;
    struct NODE *left;
    struct NODE *right;
} NODE;

Правильная механика вставки для рекурсивногоРешение будет включать объявление входного указателя как входящего / выходного (и, следовательно, указателя на его тип). Поскольку его тип уже является указателем, это означает, что правильным входным аргументом будет указатель на указатель на NODE. Поэтому результирующая функция выглядит следующим образом (без проверки ошибок, которую я оставляю вам):

void insert(NODE **pp, int value)
{
    if (!*pp)
    {
        *pp = malloc(sizeof **pp);
        (*pp)->data = value;
        (*pp)->left = NULL;
        (*pp)->right = NULL;
    }
    else if (value < (*pp)->data) {
        insert(&(*pp)->left, value);
    }
    else {
        insert(&(*pp)->right, value);
    }
}

Это делает две вещи:

1. Исправляет неправильную передачу по значениюИспользование.
2. Исправляет недооцененное выделение, которое вы имели из-за путаницы с псевдонимом node.
3. Снимает требование обновления глобального root (оно больше не должно быть глобальным).

Где-то в main теперь вы можете сделать это:

int main()
{
    NODE *root = NULL;
    insert(&root, 42);
    insert(&root, 16);
    insert(&root, 91);
    // etc..
}

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

---

Итеративное решение

Используя вышеописанную технику, вы можете легко преобразовать эту функцию в итеративную, а не рекурсивную, и в конечном итоге вам будет поручено этозапрос. Это выглядело бы как код ниже (обратите внимание на тот же список аргументов, и снова, без проверки ошибок, которую я оставляю вам):

void insert(NODE **pp, int value)
{
    while (*pp)
    {
        if (value < (*pp)->data)
            pp = &(*pp)->left;
        else
            pp = &(*pp)->right;
    }

    *pp = malloc(sizeof **pp);
    (*pp)->data = value;
    (*pp)->left = NULL;
    (*pp)->right = NULL;
}

Код отличается, но установка и вызов из внешнегоАбонент идентичен.

Надеюсь, это поможет.