C ++ Binärer Suchbaum Einsatz über Rekursion

Question

Mein Code ist also unten. Ich bekomme keine Fehler und es stellt alles in den Knoten gut. Basierend auf meinen Debug -Aussagen jedes Mal, wenn etwas eingefügt wird, findet es die Wurzel. Ich bin mir nicht sicher, ob das richtig ist. Laut Ausgabedatei für die Zuordnung sind meine Antworten jedoch unterschiedlich, wenn es um die Höhe des Baumes geht, die Traverals, und ich habe einfach immer noch Probleme mit meiner Blattzahlfunktion. Eine andere Geschichte.

Basierend auf den Debug -Aussagen sieht es so aus, als ob alles genau dort läuft, wo sie sollten. Aber ich denke, ich brauche vielleicht frische Augen. Ich sehe nicht, wie sich meine Traverals überhaupt ändern können, da es wirklich nur eine Frage ist, in der ich den Knoten bezeichne, der die Unordnung, Vorbestellung und Postorder beeinflussen sollte.

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;
               }
        }
 }

Meine Höhenfunktion lautet wie folgt, nur für den Fall, dass mein Einsatz tatsächlich in Ordnung ist.

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

Sie müssen den Wortlaut Ihrer Debug -Aussagen ändern

Wirklich sollte es lesen (nicht Rootknoten)

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

Es ist nur das Wurzel, wenn es zum ersten Mal danach aufgerufen wird, einen Aufruf mit Knoten-> links oder Knoten-> rechts macht es zu einem Zwischenknoten.

Zum Schreiben von Höhe () würde ich Folgendes tun:

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

Sie müssen mit Ihrer Wurzel initiert, um Null zu nutzen. Außerdem bestehen Sie *& node in; Es sollte *Knoten sein. Andernfalls übergeben Sie einen Zeiger an die Adresse (oder Referenz, ich bin mir nicht sicher, welche in diesem Zusammenhang, beide nicht richtig sein werden). Sie sollten einen Zeiger zum Knoten geben, nicht um eine Referenz.

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:
Es sollte ein Zeiger nach links/rechts/Root -Zeigern (dh ein Doppelzeiger) sein, sodass der veröffentlichte Code korrekt ist, obwohl es etwas unklar ist.

@Doug:
Erwägen Sie also, Ihre Einfügungsfunktion zu ändern:

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;
       }

Es macht Ihre Absicht klar, dass Sie den Zeiger als erster Parameter ändern werden (oder vielmehr der Zeiger, dessen Adresse als erster Parameter übergeben wird). Es hilft, Verwirrung wie die zu vermeiden, die gerade passiert ist.

Die Anrufe zu diesem Einfügen (), wie:

insert(&root, newNode);

wird auch Ihre Absicht widerspiegeln, den Wert des Zeigers zu ändern. Dies ist jedoch eine Frage des Stils, daher kann ich nicht argumentieren, ob Sie sich nicht ändern wollen.

---

Wenn Sie überprüfen, ob der Baum "richtig" ist, zeichnen Sie ihn nicht aus und überzeugen Sie sich selbst. Etwas in der Reihe:

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);
}

(Nicht getestetes Kodex)