[C++] Inserimento in un albero binario

[gaten]

Salve ragazzi ho la seguente function per inserire un elemento in un bst

#include <iostream>


using namespace std;


// Creo il tipo di dato tree
typedef struct node {
    node *left;
    node *right;
    int info;
} tree;


// Prototipi delle functions
tree bst_insert(tree root, int elem);



int main()
{

    tree *root;
    int elemento;

    root=null;

    do {
        cout<<"Inserisci l'elemento da inserire:"<<endl;
        cin>>elemento;
        bst_insert(root, elemento);
        cout<<"Vuoi inserire un altro elemento?";
        cin>>scelta;
    } while (scelta == 's' or scelta == 'S');
}


/* Inserimento di un elemento nel bst */
tree bst_insert(tree root, int elem)
{
      if ( root == null ) {

           root = new tree;
           root.info = elem;
           root.left = null;
           root.right = null;

      }
      else {
           if ( elem < root.info ) {
                root = bst_insert(root.left, elem);
           }
           else if ( elem > root.info ) {
                root = bst_insert(root.right, elem);
           }
           else {
                cout<<"Dato duplicato\n";
           }
      }
      return (root);
}

Mi dà questi 6 errori:

Compiling: C:\Users\Gaten\Desktop\bst.cpp
C:\Users\Gaten\Desktop\bst.cpp: In function 'int main()':
C:\Users\Gaten\Desktop\bst.cpp:30: error: 'null' was not declared in this scope
C:\Users\Gaten\Desktop\bst.cpp:35: error: conversion from 'tree*' to non-scalar type 'tree' requested
C:\Users\Gaten\Desktop\bst.cpp: In function 'tree bst_insert(tree, int)':
C:\Users\Gaten\Desktop\bst.cpp:85: error: 'null' was not declared in this scope
C:\Users\Gaten\Desktop\bst.cpp:87: error: no match for 'operator=' in 'root = (tree*)operator new(12u)'
C:\Users\Gaten\Desktop\bst.cpp:8: note: candidates are: node& node::operator=(const node&)
C:\Users\Gaten\Desktop\bst.cpp:95: error: conversion from 'node*' to non-scalar type 'tree' requested
C:\Users\Gaten\Desktop\bst.cpp:98: error: conversion from 'node*' to non-scalar type 'tree' requested
Process terminated with status 1 (0 minutes, 0 seconds)
6 errors, 0 warnings

Qualcuno può aiutarmi?

[oregon]

Hai letto i messaggi d'errore?

Nel primo c'è scritto

C:\Users\Gaten\Desktop\bst.cpp:30: error: 'null' was not declared in this scope

quindi dovresti dare un'occhiata a questo

null

di cui parla il messaggio.

Per il secondo, ti consiglio di prestare attenzione al fatto che root è un puntatore a tree mentre il primo parametro della bst_insert non prevede (a torto) un puntatore a tree ...

[gaten]

Stò usando CodeBlocks ed ho sempre utilizzato null, ho provato anche a scrivere NULL, ma dà sempre lo stesso errore.

[oregon]

Originariamente inviato da gaten
Stò usando CodeBlocks ed ho sempre utilizzato null,

Allora hai sempre avuto un errore ...

ho provato anche a scrivere NULL, ma dà sempre lo stesso errore.

Non mi sembra proprio possibile ...

[gaten]

#include <iostream>


using namespace std;


// Creo il tipo di dato
typedef struct node {
    node *left;
    node *right;
    int info;
} tree;


// Prototipi delle functions
tree bst_insert(tree *root, int elem);
tree symmetric_order(tree *root);



int main()
{

    tree *root;
    char scelta;
    int elemento;

    root=NULL;

    do {
        cout<<"Inserisci l'elemento da inserire:"<<endl;
        cin>>elemento;
        bst_insert(root, elemento);
        cout<<"Vuoi inserire un altro elemento?";
        cin>>scelta;
    } while (scelta == 's' or scelta == 'S');

    symmetric_order(root);
}


/* symmetric order */
tree symmetric_order(tree *root)
{
    if( root != NULL ){
        symmetric_order(root->left);
        cout<<root->info;
        symmetric_order(root->right);
    }
}


/* Inserimento di un elemento nel bst */
tree bst_insert(tree *root, int elem)
{
    tree *new_node;

      if ( root == NULL ) {

           new_node = new tree;
           new_node->info = elem;
           new_node->left = NULL;
           new_node->right = NULL;
           root = new_node;
      }
      else {
           if ( elem < root->info ) {
                bst_insert(root->left, elem);
           } else if ( elem > root->info ) {
                bst_insert(root->right, elem);
                } else {
                    cout<<"Dato duplicato\n";
           }
      }
      return *root;
}

L'unica modifica l'avevo dimenticata nel main, (root=NULL), oregon, adesso ho provato ad inserire degli elementi nell'albero, dopodichè dopo ho provato a richiamare la function "symmetric_order" per stampare l'albero simmetricamente, ma non stampa nulla. Forse perchè una volta inserito, io restituisco il puntatore all'ultimo elemento inserito?

[oregon]

Ma davvero tu compili senza errore codice come

while (scelta == 's' or scelta == 'S');

o anche una funzione

tree symmetric_order(tree *root)

che non restituisce nulla ?

Non capisco che prove tu possa fare con un codice non compilabile ...

[gaten]

Ho modificato la function così:

/* symmetric order */
void symmetric_order(tree *root)
{
    if( root != NULL ){
        symmetric_order(root->left);
        cout<<root->info<<" ";
        symmetric_order(root->right);
    }
}

Non mi dà nessun errore dal punto di vista della compilazione.

Quando ho finito di inserire elementi nell'albero, io richiamo symmetric_corder(root), ma non stampa nulla. Non riesco a capire qual'è il problema

[gaten]

Comunque ho notato che l'errore è qui:

/* Inserimento di un elemento nel bst */
tree bst_insert(tree *root, int elem)
{
    tree *new_node;

      if ( root == NULL ) {

           new_node = new tree;
           new_node->info = elem;
           new_node->left = NULL;
           new_node->right = NULL;
           root = new_node;
      }
      else {
           if ( elem < root->info ) {
                bst_insert(root->left, elem);
           } else if ( elem > root->info ) {
                bst_insert(root->right, elem);
                } else {
                    cout<<"Dato duplicato\n";
           }
      }
      return *root;
}

Quando richiamo symmetric_order, alla function viene passata la root vuota cioè uguale a NULL...

[oregon]

Non hai risposto su

Originariamente inviato da oregon
Ma davvero tu compili senza errore codice come

while (scelta == 's' or scelta == 'S');

E poi la

tree bst_insert(tree *root, int elem)

dovrebbe restituire un puntatore a tree e non tree e questo puntatore restituito dovresti utilizzarlo, altrimenti perché restituirlo?

[gaten]

Riguardo a:

while (scelta == 's' or scelta == 'S');

Non vedo nessun problema alla fine lo utilizzo semplicemente per chiedere ad ogni inserimento se inseririe o meno un altro elemento.

Riguardo a:

dovrebbe restituire un puntatore a tree e non tree e questo puntatore restituito dovresti utilizzarlo, altrimenti perché restituirlo?

Non riesco a capire.