C++ - print aus einem binären Suchbaum

Habe nichts besseres zu tun dieses Weihnachten Urlaub, so dass ich beschloss zu versuchen, machen einen binären Suchbaum. Ich bin stecken, mit der print-Funktion. Wie soll die Logik dahinter funktioniert? Da der Baum bereits einsetzen, es in einem einigermaßen sortiert, und ich will zu drucken, die die Struktur von kleinsten Werten die größte.

Also muss ich Reisen, um an der am weitesten linken Zweig des Baumes zu drucken den ersten Wert. Richtig, so nach der dass wie ich erinnere mich an den Weg zurück, den brauche ich zum speichern der vorherigen Knoten? Eine Suche in der wikipedia gab mir eine Lösung, die Sie verwendet, stack. Und andere Lösungen, die ich konnte nicht ganz verstehen, wie Sie es geschafft hat, so Frage ich hier, anstatt in der Hoffnung, jemand kann enlight mich.

Ich Frage mich auch, mein insert-Funktion ist OK. Ich habe gesehen, andere die Lösung wird kleiner.

void treenode::insert(int i)
{

   if(root == 0)
   {
      cout << "root" << endl;
      root = new node(i,root);
   }
   else
   {
      node* travel = root;
      node* prev;
      while(travel)
      {
         if(travel->value > i)
         {
            cout << "travel left" << endl;
            prev = travel;
            travel = travel->left;
         }
         else
         {
            cout << "travel right" << endl;
            prev = travel;
            travel = travel->right;
         }
      }
      //insert
      if(prev->value > i)
      {
         cout << "left" << endl;
         prev->left = new node(i);
      }
      else
      {
         cout << "right" << endl;
         prev->right = new node(i);
      }
   }

}

void treenode::print()
{

   node* travel = root;
   while(travel)
   {
      cout << travel->value << endl;
      travel = travel->left;
   }

}

InformationsquelleAutor starcorn | 2010-12-27

binary-tree c++traversal

1

Können Sie die Rekursion (pseudocode):
```
prin-tree(node):
   print-tree(left-subnode) if exists
   print(node-value)
   print-tree(right-subnode) if exists
...
print(root-of-tree)
```
lustige Sache, es funktioniert. Nicht so lustig ist, ich verstehe es nicht... ich hasse Rekursion...
Wenn Sie das Gefühl, dass Art und Weise über Rekursion wäre mein Vorschlag legen Sie dieses Projekt und nehmen Sie das schreiben von Programmen in Lisp für eine Weile, bis Sie sind komfortabel mit. Gibt es Gründe, um zu vermeiden, es bei Gelegenheit zu sein, sondern eine wirklich erfahrene Entwickler Rekursion werden muss, um in Ihren Werkzeugkasten.
für die Uneingeweihten Rekursion kann entmutigend sein - die meisten von uns gehen durch! Hier ist eine einfache Methode, um zu verstehen, Rekursion - die "crux" einer rekursiven Aufruf wird nicht in die Rekursion selbst, vielmehr liegt es in der "end-Fällen", viz., die Teile des Codes, der ausgeführt wird, wenn Sie nicht gehen, um ein rekursiver Aufruf. Starten Sie, indem Sie versuchen zu verstehen, die print-Funktionen - der Unterschied version postorder, preorder und inorder. Eine schnelle Suche zeigte sich diese web-Seite cs.umd.edu/class/spring2002/cmsc214/Tutorial/recursion.html

InformationsquelleAutor crazylammer
0

Den traditionellen CS101 Weg zum traversieren eines binären Baums, etwas zu tun (drucken, durchsuchen, einfügen, etc.) ist die Verwendung von Rekursion. Haben die (was auch immer) routine-check Ihrer aktuellen Knotens, dann ist das nicht die, die Sie suchen, rufen Sie sich mit der linken und/oder rechten Teilbaum (falls vorhanden).

Für eine nette Diskussion, mit psedocode, check-out der Wikipedia-Artikel über tree traversal. Es zeigt auch, wie es zu tun ohne Rekursion, die passen würden, wie Sie einfügen.

InformationsquelleAutor T.E.D.
0

Es hängt alles von der definition des Baumes. Wenn der Knoten nicht enthalten Zeiger zurück zu den Eltern, dann müssen Sie einen Stapel zum drucken der in-order-Transversale. Der einfachste Weg wäre zu schreiben Sie eine rekursive Funktion verwenden, um die Anwendung Stapel. Der Algorithmus wurde bereits zuvor dargestellt, aber im Grunde:
```
in-order(node):
   in-order(node.left) if node.left not null
   process(node)
   in-order(node.right) if node.right not null
```
Wenn Knoten halten Zeiger wieder an die Eltern, Sie könnten dann schreiben Sie eine iterative version, aber es ist wahrscheinlich nicht Wert, der Aufwand (für nichts, aber für die Denkanstöße)

InformationsquelleAutor David Rodríguez - dribeas

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.