Вставка двоичного дерева не работает

Question

У меня есть следующий код для вставки узлов в дерево. Проблема в том, что код не работает, ошибки компиляции нет, но вывод не верный. Код выглядит следующим образом:

#include <stdio.h>

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

node * insertNode(node *root, int value) {
    if(root == NULL) {
        printf("%s\n", "root is null, making new node");
        node * new_node = new node;
        new_node->data = value;
        new_node->left = NULL;
        new_node->right = NULL;
        root = new_node;
        printf("%s\n", "root assigned to new node");
    }
    else {
        if(root->data < value) {
            printf("%s\n", "Right subtree");
            insertNode(root->right, value);
        } else {
            printf("%s\n", "Left subtree");
            insertNode(root->left, value);
        }
    }
    return root;
}

void printTree(node *root) {
    if(root != NULL) {
    if(root->left != NULL) {
        printTree(root->left);
    }
    printf("%d ", root->data);
    if(root->right != NULL) {
        printTree(root->right);
    }
    }
    else {
        printf("%s\n", "root is null");
        return;
    }
}

int main()
{
    node *root = new node;
    root->data = 1;
    root->left = NULL;
    root->right = NULL;
    root = insertNode(root, 2);
    printTree(root);
    return 0;
}

Куда я иду не так?

Answer 1

Вы забыли присвоить возвращаемое значение рекурсивной функции insertNode, + Изменить insertNode(root->right, value) в root->right = insertNode(root->right, value); а также insertNode(root->left, value) в root->left = insertNode(root->left, value);, Первый параметр вашей функции insertNode только входной параметр, выходное значение - ваше возвращаемое значение. Адаптируйте ваш код так:

node * insertNode(node *root, int value) {
    if( root == NULL ) {
        printf("%s\n", "root is null, making new node");
        node * new_node = new node;
        new_node->data  = value;
        new_node->left  = NULL;
        new_node->right = NULL;
        root = new_node;
        printf("%s\n", "root assigned to new node");
    }
    else {
        if( root->data < value ) {
            printf("%s\n", "Right subtree");
            root->right = insertNode( root->right, value );
          //            ^ assigne possibly new right node
        } else {
            printf("%s\n", "Left subtree");
            root->left = insertNode( root->left, value );
          //           ^ assigne possibly new left node
        }
    }
    return root;
}

Другое решение - изменить сигнатуру функции. insertNodeи передать параметр по указателю:

void insertNode(node **root, int value) {
                 //  ^^ in and output parameter
    if( *root == NULL ) {
        printf("%s\n", "root is null, making new node");
        node * new_node = new node;
        new_node->data  = value;
        new_node->left  = NULL;
        new_node->right = NULL;
        *root = new_node;
        printf("%s\n", "root assigned to new node");
    }
    else {
        if( (*root)->data < value ) {
            printf("%s\n", "Right subtree");
            insertNode( &((*root)->right), value );
        } else {
            printf("%s\n", "Left subtree");
            insertNode( &((*root)->left), value );
        }
    }
}

int main()
{
    node *root  = new node;
    root->data  = 1;
    root->left  = NULL;
    root->right = NULL;
    insertNode( &root, 2 );
             // ^
    printTree(root);
    return 0;
}

Обратите внимание, что вы никогда не удаляете выделенные узлы.