Вставка данных в двоичное дерево в C

Question

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node
{
    int data;
    struct node *right;
    struct node *left;
} NODE;
void *insert(int ins, NODE *start)
{
    NODE *newNode = malloc(sizeof(NODE));
    if (start == NULL )
    {
        newNode->data = ins;
        newNode->left = NULL;
        newNode->right = NULL;

    }
    if(ins<start->data)
    {
        insert(ins, start->left);
    }
    else if(ins>start->data)
    {
        insert(ins, start->right);
    }
}
int main()
{  
    int number;
    NODE *head;
    head=NULL;

    number = 15;
    head = insert(number, head);
    printf("prints the first element (head): %d", head->data);

    number = 12;
    insert(number, head);

    printf("should print the left branch : %d", head->left->data);  // <- THIS DOES NOT SHOW UP 

}

Answer 1

Похоже, что следующее близко к тому, что вы хотите.

Это рекурсивная функция insert(), которая берет адрес узла и проверяет, следует ли добавить новый узел вдерево или взять ветку, чтобы продолжить поиск места для вставки узла.

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

Я не особо разбираюсь в знаниях о дереве, поэтому я не уверен, что это за двоичное дерево или прохождение, и т. Д.Я оставлю это на ваше усмотрение.

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

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

void *insert(int ins, NODE **start)
{
    if (*start == NULL)
    {
        NODE *newNode = malloc(sizeof(NODE));

        newNode->data = ins;
        newNode->left = NULL;
        newNode->right = NULL;

        (*start) = newNode;

    }
    else if (ins < (*start)->data)
    {
        insert(ins, &((*start)->left));
    }
    else if (ins > (*start)->data)
    {
        insert(ins, &((*start)->right));
    }

    // if we already have this value in the tree then we will do nothing
    // and ignore it.
    return *start;
}

void printTree(NODE *start)
{
    // print tree
    if (start->left) printTree(start->left);
    printf("Element value %d\n", start->data);
    if (start->right) printTree(start->right);
}

int main ()
{
    int number;
    NODE *phead = NULL;

    number = 15;
    insert(number, &phead);
//  printf("prints the first element (head): %d", head.data);

    number = 12;
    insert(number, &phead);

//  printf("should print the left branch : %d", head.left->data);  // <- THIS DOES NOT SHOW UP 

    number = 22;
    insert(number, &phead);

    number = 48;
    insert(number, &phead);

    number = 33;
    insert(number, &phead);

    // try a duplicate node data.
    number = 48;
    insert(number, &phead);

    printTree(phead);
    return 0;
}

Сгенерированный вывод:

Element value 12
Element value 15
Element value 22
Element value 33
Element value 48

Answer 2

Параметр start передается по значению, поэтому он никогда не изменяется.Один из вариантов, который у вас есть, это передача указателя на указатель NODE, например:

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

int main()
{

    int number;
    NODE *head;
    head=NULL;

    number = 15;
    insert(number, &head); ///Doesn't need head=insert(...) anymore
    printf("prints the first element (head): %d", head->data);

    number = 12;
    insert(number, &head);

    printf("should print the left branch : %d", head->left->data);
}