Binärbaum Traversal in doppelter Reihenfolge

Question

Kann mir jemand das Double Order Traversal erklären?

        A
      /   \
     B     E
   /  \   /  \
  C   D  F    G

Traversal-Ausgang doppelter Ordnung : ABCCBDDAEFFEGG

Ich bin eher an Erklärungen als an dem Code interessiert.

Danke

Answer 1

Angenommen, Sie sind an einer Erklärung interessiert, was ein Traversal doppelter Ordnung bewirkt:

Für jede Traversierung müssen Sie

• Knotenpunkt besuchen
• Traverse Linkes Kind
• Knotenpunkt besuchen
• Traverse Rechts Kind

Mehr gibt es nicht zu sagen. In Fällen, in denen Sie kein linkes Kind haben (wie z. B. C), finden die beiden "visit node"-Operationen nacheinander statt, weshalb Sie in Ihrer Ausgabe zwei Cs sehen.

Nur zur Veranschaulichung (mit fettgedruckter Ausgabe):

• Besuch A: A
• Traverse links Kind B
• • Besuch B: AB
• • Traverse links Kind C
• • • Besuch C: ABC
• • • Kein verlassenes Kind
• • • Besuch C: ABCC
• • • Kein rechtes Kind
• • Traverse rechts Kind D
• • • Besuch D: ABCCD
• • • Kein verlassenes Kind
• • • Besuch D: ABCCDD
• • • Kein rechtes Kind
• Besuch A: ABCCDDA
• Traverse rechts Kind E
• • Besuchen Sie E: ABCCDDAE

usw.

Answer 2

Stellen Sie sich vor, Sie gehen, beginnend an der Wurzel.

1. Sie befinden sich bei A;
2. Geh nach links Kind, du kommst zu B;
3. Gehe zum linken Kind, C;
4. Sackgasse, Sie kehren um, immer noch C;
5. Zurück bei B;
6. Gehe zum rechten Kind, zu D;
7. Sackgasse, umkehren noch D;

usw.

Dies ist nur eine Durchquerung, die sowohl Ein- als auch Ausgänge zählt.

Zwischen dem Besuch der linken und rechten Kinder in einem Preorder-Traversal besucht man die Wurzel (weil man zu ihr zurückkehren muss, um weiterzugehen), und man kann sich die Blätter als Wurzeln vorstellen, die keine Kinder haben, und null wird Sie dazu bringen, sofort wiederzukommen (daher die zwei aufeinander folgenden Besuche in den Blättern, und die Knotenpunkte haben nur richtige Kinder).

Answer 3

Rekursion durch:

1. Visit root of (sub)tree.
2. Visit left subtree.
3. Revisit root of (sub)tree.
4. Visit right subtree.

Aus dem Stegreif fällt mir keine Anwendung dafür ein, obwohl ich einige wirklich verrückte Dinge mit einem Stapel von Knoten gemacht habe, die sich in mehreren Bäumen (und verknüpften Listen) gleichzeitig befinden.

Answer 4

Im Wesentlichen handelt es sich um einen rekursiven Ansatz zur Durchquerung eines Baumes (hier handelt es sich um einen Binärbaum)

Hier ist ein Algorithmus für Double Order Traversal :

Algorithmus DoubleOrder(Wurzel)

1. if(Wurzel ist nicht NULL)

   1. print(Wurzel)
   2. DoubleOrder (leftSubtree) //rekursiver Aufruf
   3. print(Wurzel)
   4. DoubleOrder (rightSubtree) // rekursiver Aufruf

2. endif

3. Ende DoubleOrder

Erläuterung:

1. Besuchen Sie A & drucken Sie es aus Ausgang : A
2. A hat einen linken Teilbaum
   1. Besuchen Sie B & drucken Sie es aus Ausgang : AB
   2. B haben einen linken Teilbaum
      1. besuchen Sie C und drucken Sie es aus Ausgabe : ABC
      2. C keinen linken Teilbaum haben
      3. Besuchen Sie C erneut und drucken Sie es aus Ausgang : ABCC
      4. C haben keinen Teilbaum
      5. Rückkehr zu B (im Fall von C wurden alle 4 Anweisungen ausgeführt)
   3. Besuchen Sie B erneut und drucken Sie es aus Ausgang : ABCCB
   4. B haben einen rechten Teilbaum
      1. besuchen Sie D und drucken Sie es aus Ausgang : ABCCBD
      2. D keinen linken Teilbaum haben
      3. Besuchen Sie D erneut und drucken Sie es aus Ausgabe : ABCCBDD
      4. D keinen Teilbaum haben
      5. Rückkehr zu B (im Fall von D wurden alle 4 Anweisungen ausgeführt)
   5. Rückkehr zu A (im Fall von B wurden alle 4 Anweisungen ausgeführt)
3. Besuchen Sie A erneut und drucken Sie es aus Ausgang : ABCCBDDA
4. A hat einen rechten Teilbaum
   1. Besuchen Sie E & drucken Sie es Ausgang : ABCCBDDAE
   2. E haben einen linken Teilbaum
      1. besuchen Sie F und drucken Sie es aus Ausgang : ABCCBDDAEF
      2. F haben keinen linken Teilbaum
      3. Besuchen Sie F erneut und drucken Sie es aus Ausgang : ABCCBDDAEFF
      4. F haben keinen Teilbaum
      5. Rückkehr zu E (im Fall von F wurden alle 4 Anweisungen ausgeführt)
   3. Besuchen Sie E erneut und drucken Sie es aus Ausgang : ABCCBDDAEFFE
   4. E haben rechten Teilbaum
      1. besuchen Sie G und drucken Sie es aus Ausgang : ABCCBDDAEFFEG
      2. G keinen linken Teilbaum haben
      3. Besuchen Sie G erneut und drucken Sie es aus Ausgang : ABCCBDDAEFFEGG
      4. G keinen Teilbaum haben
      5. Rückkehr zu E (im Fall von G wurden alle 4 Anweisungen ausgeführt)
   5. Rückkehr zu A (im Fall von E wurden alle 4 Anweisungen ausgeführt)
5. Stoppen Sie die Ausführung, wenn wir zur Hauptwurzel des Baums zurückkehren (da alle 4 Anweisungen ausgeführt wurden). im Fall von A)

Endgültige Ausgabe : ABCCBDDAEFFEGG

Ich hoffe, es hilft Ihnen, das Gesamtkonzept zu verstehen! Ich freue mich sehr, zum ersten Mal auf Stack Overflow zu antworten :)