Inserimento dell'albero di ricerca binaria C ++ tramite ricorsione

Question

Quindi il mio codice è sotto. Non ricevo alcun errore e posiziona tutto nel nodo bene. Ma in base alle mie dichiarazioni di debug Ogni volta che qualcosa viene inserito trova la radice. Non sono sicuro che sia giusto. Ma in base al file di output per il compito, le mie risposte sono diverse quando si tratta dell'altezza dell'albero, degli attraversamenti e io sto semplicemente avendo problemi con la mia funzione di conteggio delle foglie. Un'altra storia però.

Sulla base delle dichiarazioni di debug sembra che tutto vada esattamente dove dovrebbe. Ma immagino che potrei aver bisogno di occhi nuovi. Non vedo come i miei traversals possano cambiare affatto dato che in realtà è solo una questione di dove sto promuovendo il nodo che dovrebbe influenzare Inorder, preorder e postorder.

template <class T>
void BT<T>::insert(const T& item)
 {
    Node<T>* newNode;
    newNode = new Node<T>(item);
    insert(root, newNode);
 }


template <class T>
void BT<T>::insert(struct Node<T> *&root, struct Node<T> *newNode)
 {
    if (root == NULL)
       {
          cout << "Root Found" << newNode->data << endl;
          root = newNode;
       }
    else
        {
           if (newNode->data < root->data)
              {
              insert(root->left, newNode);
              cout << "Inserting Left" << newNode-> data << endl;
              }
           else
               {
               insert(root->right, newNode);
               cout << "Inserting Right" << newNode->data << endl;
               }
        }
 }

La mia funzione di altezza è la seguente nel caso in cui il mio inserimento sia effettivamente a posto.

template <class T>
int BT<T>::height() const
{
   return height(root);
}


  template <class T>
  int BT<T>::height(Node<T>* root) const
   {
   if (root == NULL)
      return 0;
   else 
      {
      if (height(root->right) > height(root->left))
         return 1 + height(root-> right);
      return 1 + height(root->left);
      }
   }

Answer 1

Devi modificare la formulazione delle tue dichiarazioni di debug

Dovrebbe davvero leggere (non nodo radice)

 cout << "Leaf Node Found" << newNode->data << endl;

È solo il root quando viene chiamato per la prima volta dopo che qualsiasi chiamata con node- > left o node- > right lo rende un nodo intermedio.

Per scrivere height () farei questo:

template <class T>
int BT<T>::height(Node<T>* root) const
{
    if (root == NULL) {return 0;}

    return 1 + max(height(root->left),height(root->right));
}

Answer 2

Devi iniziare con il tuo root inizializzato su null. Inoltre, stai passando * & amp; node in; dovrebbe essere * nodo. Altrimenti stai passando un puntatore all'indirizzo (o riferimento, non sono sicuro quale in questo contesto, ma entrambi non avranno ragione). Dovresti passare un puntatore a Nodo in, non un riferimento.

template <class T>
void BT<T>::BT() 
{ root = 0;}

template <class T>
void BT<T>::insert(const T& item)
 {
    Node<T>* newNode;
    newNode = new Node<T>(item);
    insert(root, newNode);
 }

template <class T>
void BT<T>::insert(struct Node<T> *root, struct Node<T> *newNode)
{
 /*stuff*/
}

Answer 3

@Vlion:
Dovrebbe essere un puntatore ai puntatori sinistra / destra / radice (cioè un doppio puntatore), quindi il codice pubblicato è corretto, anche se in qualche modo poco chiaro.

@Doug:
Valuta di modificare la tua funzione di inserimento in questo modo:

template <class T>
void BT<T>::insert(struct Node<T>** root, struct Node<T>* newNode)
 {
    if (*root == NULL)
       {
          cout << "Root Found" << newNode->data << endl;
          *root = newNode;
       }

Illustra la tua intenzione di modificare il puntatore passato come primo parametro (o meglio, il puntatore il cui indirizzo verrà passato come primo parametro). Aiuterà a evitare confusione come quello appena accaduto .

Le chiamate a questo insert (), come ad esempio:

insert(&root, newNode);

rifletterà anche la tua intenzione di cambiare il valore del puntatore. Questa è una questione di stile, quindi non posso discutere se non vuoi cambiare.

---

Come per verificare se l'albero è "corretto", perché non tirarlo fuori e vedere di persona? Qualcosa del genere:

template class<T>
void printTree(struct Node<T>* node, int level=0)
{
    if (!node) {
        for (int i=0; i<level; ++i)
            cout << "  ";
        cout << "NULL" << endl;

        return;
    }

    printTree(node->left, level+1);

    for (int i=0; i<level; ++i)
        cout << "  ";
    cout << node->data << endl;

    printTree(node->right, level+1);
}

(Codice non testato)