Finden Preoder von Nur Inorder Traversal?

Lief ich in eine Mitte-Prüfung Frage, das dauerte 4 Tage her, dass ich couldent underestand!

Nehmen wir an, wir haben die Antwort gegeben, wenn wir eine inorder-Traversierung eines Baumes dann kommen wie wir finden die Lösung im Falle einer preorder-Traversierung. Ich habe Folgendes Beispiel bei mir : Bei der inorder-Traversierung eines Baumes führte E A C K F H D B G;

was wäre der preorder-Traversierung zurück?

a. FAEKCDBHG
b. FAEKCDHGB
c. EAFKHDCBG
d. FEAKDCHBG

Wer kann mir helfen, in einer Weise lernen?

BEARBEITEN:
Ich weiß, die Antwort ist : FAEKCDHGB. aber wie dieser berechnet?

InformationsquelleAutor Prof. Kosi Noura | 2015-03-14

5

Also die inorder lautet:
```
E A C K F H D B G
```
Und die preorder muss:
```
a. FAEKCDBHG
b. FAEKCDHGB
c. EAFKHDCBG
d. FEAKDCHBG
```
Sollten Sie gehen Sie durch die Zeichnung der Baum für jede dieser Optionen, während auch so dass es passt mit der inorder-Traversierung und sehen Sie die eine, die ist möglich.

Zu tun, dass für jedes Zeichen in der preorder-Traversierung, teilen Sie die inorder-Traversierung in zwei rund um diesen Charakter.

ein.

Wissen wir F muss der Stamm. Teilen Sie die inorder-Traversierung um F:
```
        | F | 
 E A C K     H D B G
```
Das nächste Zeichen in der preorder-Traversierung wird A. Split der Teilbaum mit A um A:
```
            | F | 
     | A |        H D B G
    E     C K
```
Nächsten E. Nichts zu trennen. Die nächste ist K:
```
            | F | 
     | A |        H D B G
    E     C
            K
```
Nächsten C. Nichts zu trennen.

Nächsten D:
```
            | F | 
     | A |        | D |
    E     C      H     B G
            K
```
Nächsten B:
```
            | F | 
     | A |        | D |
    E     C      H     B 
            K            G
```
Und wir sind fertig, es wird keine weitere Teilungen möglich. Führen Sie nun die preorder-Traversierung auf diesem Baum, erhalten Sie:
```
F A E C K D H B G
```
Was nicht, was wir mit dem begonnen, so erreichten wir einen Widerspruch. Es kann also nicht sein ein. Machen Sie dasselbe für die andere.

(b) korrekt ist? okey?
ja.
Wow ich habe es verstanden, nachdem ich das Häkchen bei der falschen Antwort heute... 🙂

InformationsquelleAutor IVlad
2

Die Antwort ist nicht definiert.

Haben Sie einen Blick auf diese zwei Bäume:
```
 E
  \
   A
    \
     C 
      \
       K
        \
         F 
          \
           H 
            \
             D 
              \
               B
                \
                 G
```
Und:
```
   A
 / \
E    C 
      \
       K
        \
         F 
          \
           H 
            \
             D 
              \
               B
                \
                 G
```
Diese beiden Bäume haben die gleiche in-order-traversal, aber die erste ist die pre-order-traversal von EACKFHDBG, während der zweite hat die in-order-traversal von AECKFHDBG

So, da eine in-order-traversal, es ist viel mehr als ein mit den binären Baum, der Sitz, - traversal. Dies ist aufgrund der Tatsache, dass es n! möglichen Permutationen (und damit der in-order traversal), während es gibt viel mehr binäre Bäume. Dies garantiert ( Schublade Prinzip ), dass es (mindestens eine) in-order-traversal passt, dass mehrere Bäume.

Dank von Ihr nützliche Antwort, aber ich denke, wir müssen es prüfen mit multiple-choice ! ich denke.
Eigentlich haben Sie den letzten Satz nach hinten. Die Anzahl der binären Bäume ist eine Catalan-Zahl, die wächst nur exponentiell (sehr ungefähr 4^n). n! Sie ist viel größer (in der Tat ist es nicht so schwer zu sehen, dass jede permutation Ergebnisse in nur einer binären Suche Baum, sondern mehrere Permutationen könnte passen die gleichen unmarkierten Baum).
Diese (Katalanisch) ist die Anzahl der binären Bäume mit identischen Knoten (d.h. Sie sorgen nur für die in der Topologie und nicht die Markierung jedes Knotens).
Ah, danke für die Klarstellung.

InformationsquelleAutor amit
0

Einer der b-Bäumen möglich ist :

So, die pre-order-traversal gibt:

H K A E C F B D G

Andere ist:

Für die preorder-Traversierung gibt:

H A E K C F B D G

Doch eine andere ist:

Für die preorder-Traversierung gibt:

K A E C H F B D G

,das ist keine der Optionen. Kommentare von jedermann sind willkommen, da komme ich nicht mit einem anderen binären Baum für die gegebenen inorder-Traversierung gegeben..

Ich hatte auch diese Frage in meinen Prüfungen, aber wir kamen zu wissen, dass b die Antwort von der google-Suche nach der Frage. Lolz.

InformationsquelleAutor vinaych

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.