Inserción recursiva de BST

Question

He hecho una función para inserción en BST utilizando bucles y está funcionando perfectamente bien. Ahora, cuando iam escribo para hacerlo utilizando la recursividad, no sé por qué no funciona correctamente, sin embargo, la lógica es correcta según yo. Parece que no se está agregando ningún nodo nuevo al árbol BST y que el encabezado del árbol después de salir de la función de inserción vuelve a ser NULO.

#include <iostream> 
using namespace std; 

class node{ 
public: 
    int data; 
    node *right; 
    node *left; 
    node(){ 
     data=0; 
     right=NULL; 
     left=NULL; 
    } 
}; 

class tree{ 
    node *head; 
    int maxheight; 
    void delete_tree(node *root); 
public: 
    tree(){head=0;maxheight=-1;} 
    void pre_display(node* root); 
    node* get_head(){return head;} 
    void insert(int key,node* current); 
}; 

void tree::insert(int key,node *current){ 
    if(current==NULL) 
    { 
     node *newnode=new node; 
     newnode->data=key; 
     current=newnode; 
    } 
    else{ 
     if(key<current->data) 
     insert(key,current->left); 
     else 
     insert(key,current->right); 
    } 
    return; 
} 

void tree::pre_display(node *root){ 
    if(root!=NULL) 
    { 
     cout<<root->data<<" "; 
     pre_display(root->left); 
     pre_display(root->right); 
    } 
} 

int main(){ 
    tree BST; 
    int arr[9]={17,9,23,5,11,21,27,20,22},i=0; 

    for(i=0;i<9;i++) 
    BST.insert(arr[i],BST.get_head()); 

    BST.pre_display(BST.get_head()); 
    cout<<endl; 

    system("pause"); 
    return 0; 
} 

Por favor dime qué debería cambiar en el algoritmo para que funcione.

Answer 1

En su inserción función

void tree::insert(int key,node *current){ 
    if(current==NULL) 
    { 
     node *newnode=new node; 
     newnode->data=key; 
     current=newnode; 
    } 
    else{ 
     if(key<current->data) 
      insert(key,current->left); 
     else 
      insert(key,current->right); 
    } 
    return; 
} 

asignar un nuevo nodo, pero nunca puso BST :: cabeza a cabeza recién asignada. Entonces BST :: get_head siempre devolverá null.

Una forma de solucionar esto sería que la inserción devuelva un nodo. Este sería el nodo raíz en su caso y establecerá BST :: head en este valor.

Answer 2

Su recursividad se ve bien, pero en realidad no agrega el nodo en cualquier lugar! Usted simplemente recurse a través del árbol.

Editar Puede cambiar el método de insert tomar un puntero a un puntero, así:

void tree::insert(int key, node **current) 
{ 
    if(*current == NULL) 
    { 
     node *newnode = new node; 
     newnode->data = key; 
     *current = newnode; 
    } 
    else 
    { 
     if(key < (*current)->data) 
      insert(key, &(*current)->left); 
     else 
      insert(key, &(*current)->right); 
    } 
} 

Y en el principal llamarlo así:

BST.insert(arr[i], &BST.get_head()); // Note the ampersand (&) 

Answer 3

deberías probar este

   node tree:: insert (int key , node * current) { 

        if (! current) { 
          node * newnode = new node ; 
          newnode -> key = key; 
          current = newnode ; 
         } 
        else if (key < current -> key) { 
         current -> left = insert (key , current ->left 
         } 
        else 
         current -> right = insert (key , current->right) 
       return current ; 
       } 

funciona bien .... jsut actualice el nodo principal cada vez que se inserte un nuevo nodo y devolverá el nodo actual actualizado.

Answer 4

acaba de cambiar su función como

void tree::insert(int key,node*& current){ 
    if(current==NULL) 
    { 
    node *newnode=new node; 
    newnode->data=key; 
    current=newnode; 
    } 
    else{ 
    if(key<current->data) 
     insert(key,current->left); 
    else 
     insert(key,current->right); 
    } 
    return; 
} 

hacer que el puntero de entrada como parámetro de referencia.

Answer 5

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

node* root=NULL; 

node* create(node* head,int val){ 
    if(head==NULL){ 
     node* nn=new node; 
     nn->data=val; 
     nn->left=NULL; 
     nn->right=NULL; 
     head=nn; 
    } 
    else if(val<head->data) 
     head->left=create(head->left,val); 
    else if(val>head->data) 
     head->right=create(head->right,val); 
    return head; 
} 

int main(){ 
    int num=0; 
    cout<<"Enter value in tree or press -1 to Exit\n"; 
    while(num!=-1){ 
     cin>>num; 
     if(num==-1){ 
      cout<<"\nTree Created\n"; 
      break; 
     } 
     else{ 
      root=create(root,num); 
     } 
    } 
} 

esperanza este código resuelve su problema