Реализация бинарного дерева поиска.

Question

Я пытался реализовать двоичное дерево поиска, но мне кажется, что я допустил ошибку в своей функции вставки.Вот мой код

#include<iostream>
#include<memory.h>
#include <cstddef>
using namespace std;
struct bst_node
{
    int info;
    struct bst_node *left_node_ptr;
    struct bst_node *right_node_ptr;
};

struct bst_node* getnode(int x)
{

    struct bst_node* ret= new bst_node;
    ret->info=x;
    ret->left_node_ptr=NULL;
    ret->right_node_ptr=NULL;
    return ret;
}

void insert(struct bst_node **root, int var_info)
{
    struct bst_node *temp=(*root); // Links the temporary pointer to root of the BST
    while(temp!=NULL)              // Loop till I find a suitable position for inserting
    {
        if(temp->info > var_info)
        {
            temp=temp->left_node_ptr;
        }
        else
        {
            temp=temp->right_node_ptr;
        }

    }
    temp= getnode(var_info);
    return ;
}

/* Recursive In order Traversal */
void inorder_recursive( struct bst_node * L)
{
    if(L!= NULL)
    {
        inorder_recursive(L->left_node_ptr);
        cout<<L->info<<endl;
        inorder_recursive(L->right_node_ptr);
    }
    return;
}
int main()
{
    struct bst_node* my_root= getnode(5);
    insert(&my_root, 6);
    insert(&my_root, 3);
    /*
    int x=1;
    int arr[]= {};
    while(x)
    {
        cin>>x;
        insert(&my_root, x);
    }*/
    inorder_recursive(my_root);
    return 0;
}

Answer 1

На самом деле вы никогда не устанавливаете значения left_node_ptr или right_node_ptr для ваших узлов.Ваша функция вставки запускает дерево вниз, находя правильное место для размещения нового узла, затем выделяет узел, но фактически не присоединяет новый узел слева или справа от найденного вами родителя.

Answer 2

Ваш поиск идет на 1 уровень слишком далеко.Вы выбросили узел, к которому хотите привязать своего нового ребенка.Также temp = ... не будет ничего прикреплять к вашему дереву.Вы должны сделать некоторое время, пока не найдете дочерний узел, к которому хотите присоединиться, а затем выполните одно из следующих действий:

temp-> left_node_ptr = getnode (var_info);или temp-> right_node_ptr = getnode (var_info);

   while(temp!=NULL)              // Loop till I find a suitable position for inserting
        {
            if(temp->info > var_info)
            {
                temp=temp->left_node_ptr;
            }
            else
            {
                temp=temp->right_node_ptr;
            }

        }
        temp= getnode(var_info);