PDA

Visualizza la versione completa : [C++]Cancellazione nodo in un albero binario(BST)


gaten
27-06-2011, 12:33
Salve ragazzi stò creando delle functions per cancellare un elemento in un BST.

Io ho creato queste functions:


/* MAIN */
case 5:
node=root;
cout<<"Qual'è l'elemento che vuoi cancellare?"<<endl;
cin>>elemento;
// Ricerco il nodo da cancellare, restituendo il puntatore al
// nodo da cancellare e il puntatore al padre del nodo da cancellare
bst_node_search(root, elemento, node, parent);
// Cancello il nodo
bst_delete(root, elemento);
break;
/* END MAIN */

/* Ricerca di un node di elem x */
tree bst_node_search(tree *root, int elem, tree *node, tree *parent)
{
/* Fin quando il node è diverso da NULL e l'informazione
* del node è diverso dall'elemento da cancellare */
while ( node != NULL && node->info != elem ){
parent=node;

if ( node->info > elem )
node=node->left;
else
node=node->right;
}
}


/* Cancellazione di un elemento nel bst */
tree bst_delete(tree *&root, int elem)
{
if ( node == NULL ) {
cout<<"Nessuna cancellazione può essere fatta!";
} else if ( parent == NULL ) {
delete_right_subtree(node, parent, root);
} else if ( elem < parent->info ) {
delete_left_subtree(node, parent, root);
} else{
delete_right_subtree(node, parent, root);
}
}


/* Cancellazione del sottoalbero destro */
tree delete_right_subtree(tree *node, tree *parent, tree *root)
{
tree *new_parent=parent;
tree *new_node=node->right;

if ( parent != NULL )
parent->right=node->right;
else
root=node->right;

while ( new_node != NULL ){
new_parent=new_node;
new_node=new_node->left;
}

if ( node->right != NULL ){
if ( new_parent != NULL )
new_parent->left=node->left;
else
root=node->left;
}
else if ( parent != NULL )
{
parent->right=node->left;
} else
{
root=node->left;
}
}


/* Cancellazione del sottoalbero sinistro */
tree delete_left_subtree(tree *node, tree *parent, tree *root)
{
tree *new_parent=parent;
tree *new_node=node->left;

if ( parent != NULL )
parent->left=node->left;
else
root=node->left;

while ( new_node != NULL ){
new_parent=new_node;
new_node=new_node->right;
}

if ( node->right != NULL ){
if ( new_parent != NULL )
new_parent->right=node->right;
else
root=node->right;
}
else if ( parent != NULL )
{
parent->left=node->right;
} else
{
root=node->right;
}
}

Il compilatore, mi restituisce 5 errori, giustamente, che sono i seguenti:


Compiling: C:\Users\Gaten\Desktop\bst.cpp
C:\Users\Gaten\Desktop\bst.cpp: In function 'tree bst_delete(tree*&, int)':
C:\Users\Gaten\Desktop\bst.cpp:230: error: expected primary-expression before '==' token
C:\Users\Gaten\Desktop\bst.cpp:232: error: 'parent' was not declared in this scope
C:\Users\Gaten\Desktop\bst.cpp:233: error: expected primary-expression before ',' token
C:\Users\Gaten\Desktop\bst.cpp:235: error: expected primary-expression before ',' token
C:\Users\Gaten\Desktop\bst.cpp:237: error: expected primary-expression before ',' token
Process terminated with status 1 (0 minutes, 0 seconds)
5 errors, 0 warnings


Dovrei passare alla function "bst_delete", le variabili "parent" e "node" che ho nella function "bst_node_search"(Teoricamente questa funzione, cerca il nodo che dev'essere cancellato e il rispettivo padre, dopodichè queste info devo passarle alla function bst_delete, che talvolta elimina il nodo), qualcuno può aiutarmi a completare?

Loading