PDA

Visualizza la versione completa : [C++] Inserimento in un albero binario


gaten
25-06-2011, 12:32
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
25-06-2011, 12:53
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
25-06-2011, 13:09
Stò usando CodeBlocks ed ho sempre utilizzato null, ho provato anche a scrivere NULL, ma dà sempre lo stesso errore.

oregon
25-06-2011, 13:17
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
25-06-2011, 13:24
#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
25-06-2011, 13:34
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
25-06-2011, 13:38
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 :dhò:

gaten
25-06-2011, 13:48
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
25-06-2011, 13:59
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
25-06-2011, 14:16
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.

Loading