Binario Di Ricerca Albero Di Attuazione(C++)

La maggior parte del codice è da Weiss’ “strutture di Dati e analisi algoritmo in C++”, dopo che ho digitato il codice in blocchi di codice(gnu gcc), compilatore segnalato nessun errore, ma poi ho cercato di creare un’istanza di test e di alcune funzioni è andata male. Sembra che ci sia qualcosa di sbagliato con BST() o su inserisci() perchè il programma si bloccava immediatamente poiché in esecuzione.
Qualcuno mi aiuta a scoprire come risolvere questo problema? Grande grazie!!!

#include <iostream>
using namespace std;
struct TreeNode
{
    int element;
    TreeNode*left,*right;
    TreeNode(const int&e,TreeNode*le=NULL,TreeNode*rt=NULL):element(e),left(le),right(rt){};
};

class BST
{
public:
    BST(){root=NULL;};
    ~BST(){ makeEmpty(root); };
//use public member function to call private member functions.
    void insert(const int & x){ insert(x, root); }
    void remove(const int & x){ remove(x, root); }
    TreeNode*findMin() const{ return findMin(root); }
    bool contain(const int & x) const{ return contain(x,root); }
    void printNodes() const{ printNodes(root); }

private:
    TreeNode*root;

    void makeEmpty(TreeNode*&);
    TreeNode* findMin(TreeNode*) const;
    void insert(const int &, TreeNode*) const;
    void remove(const int &, TreeNode*) const;
    bool contain(const int &, TreeNode*) const;
    void printNodes(TreeNode*) const;
};

void BST::makeEmpty(TreeNode*&t)
{
    if(t!=NULL)
    {
        makeEmpty(t->left);
        makeEmpty(t->right);
        delete t;
    }
    t=NULL;
}
TreeNode* BST::findMin(TreeNode*t) const
{
    if(t->left==NULL)    return t;
    return findMin(t->left);
}
void BST::insert(const int & x, TreeNode* t) const
{
    if(t==NULL) t=new TreeNode(x,NULL,NULL);
    else if(x < t->element)    insert(x,t->left);
    else if(x > t->element)    insert(x,t->right);
    else;   ///duplicate, do nothing
}
void BST::remove(const int & x, TreeNode* t) const
{
    if(t==NULL) return;
    if(t->element > x)    remove(x, t->left);
    else if(t->element < x)  remove(x, t->right);
    else if(t->left!=NULL && t->right!=NULL)
    {
        t->element=findMin(t->right)->element;
        remove(t->element,t->right);
    }
    else
    {
        TreeNode*oldNode=t;
        t=(t->left==NULL)?t->right:t->left;
        delete oldNode;
    }
}
bool BST::contain(const int & x, TreeNode*t) const
{
    if(t==NULL)    return false;
    else if(x<t->element)    return contain(x,t->left);
    else if(x>t->element)    return contain(x,t->right);
    else    return true;
}
void BST::printNodes(TreeNode*t) const
{
    if(t==NULL) return;
    cout<<t->element<<" ";
    printNodes(t->left);
    printNodes(t->right);
    cout<<endl;
};

Ecco il codice che ho scritto per la classe di test BST:

int main()
{
    BST BinarySearchTree;
    int element,node;
    for(int i=0; i<5; i++)
    {
        cin>>element;
        BinarySearchTree.insert(element);
    }
    BinarySearchTree.printNodes();

    cout<<BinarySearchTree.findMin()->element<<endl;

    cin>>node;
    if(BinarySearchTree.contain(node)){ cout<<"item "<<node<<" is in BST."<<endl; }

    BinarySearchTree.remove(node);
    BinarySearchTree.printNodes();
    return 0;
}
Non sono sicuro di come insert, o remove dovrebbero essere const funzioni. Si sarà certamente cambiare l’oggetto a un certo punto. Vuoi che il tuo TreeNode definiti come è sotto makeEmpty.
Puoi postare il codice spirito che si prova questo BST? Che mi aiuterà a eseguire e vedere che cosa è il problema..
Il codice ha poco senso. Io non credo che possa essere risolto, ha bisogno di essere riscritto, e lentamente. Digitando un sacco di codice di un libro, quando non correttamente capire cosa si sta facendo è molto improbabile che sia una cosa utile da fare. Lavorare più lentamente. Iniziare ad imparare qualcosa di più facile.
Ho cambiato il parametro di Treenode* in privato insert() e remove() per Treenode* & e ha funzionato bene. Grazie a voi ragazzi~

OriginaleL’autore Sol | 2013-04-25

4 Replies
  1. 4

    Classe BST è solo una variabile membro. TreeNode*root. (Non c’è alcun problema)

    Tuo insert e remove funzioni presumibilmente modificare il BST, quindi avrai bisogno di modificare qualcosa relativi a root.

    (E il compilatore rapidamente sottolineare che tali funzioni non dovrebbe essere const per lo stesso motivo.)

    OriginaleL’autore Drew Dormann

  2. 2
    void BST::makeEmpty(TreeNode*&t)
    {
        if(t==NULL)
        {
            makeEmpty(t->left);
            makeEmpty(t->right);
            delete t;
        }
        t=NULL;
    }

    Questo codice è sbagliato, se t è NULL, quindi ti do t->a sinistra e t->a destra. Che chiama dereferenziazione di un puntatore NULL ed è probabile che per rendere il vostro crash del programma immediatamente.

    Questo dovrebbe essere

    void BST::makeEmpty(TreeNode*&t)
    {
        if (t!=NULL)
        {
            makeEmpty(t->left);
            makeEmpty(t->right);
            delete t;
        }
        t=NULL;
    }
    Beh…questo è un errore di battitura, scusate non ho notato.

    OriginaleL’autore john

  3. 1

    Non hai fatto niente con radice in insert(), quindi non fa nulla (fatta eccezione per le perdite di memoria).

    Ho fatto uso di un membro pubblico la funzione inserisci() per chiamare la funzione privata insert(x, radice)
    ma root è passato per valore, quindi il fatto che si sta cambiando t in funzione privata non hanno alcun effetto al di fuori di essa.
    Bene, io ho cambiato il parametro di Treenode* in privato insert() per Treenode* &, immagino che questo ha funzionato, allora?
    Penso che sarà. Sarà super-brutto però. (implicita) si passa riferimento può facilmente rendere il codice chiamante illeggibile. BTW, non prendere const int& parametri. non c’è alcun bisogno di esso. semplice int è molto meglio.

    OriginaleL’autore Elazar

Lascia un commento