Traversierungen

[super_junior]

Hallo liebes java-forum!
Ich verstehe einfach das Prinzip nicht wie man aus 2 traversierungen einen baum erstellt

wie z.b diese beiden folgenden traversierungen:

Preorder: 16 19 13 42 21 23 18 25 11
Inorder: 19 13 16 23 18 21 42 25 11

bei preorder ist die reihenfolge:vater,links,rechts
und inorder: links,vater,rechts

ich weiß,dass bei preoder die wurzel die 16 ist,weil sie am anfang steht
und dann muss man bei inorder nach der 16 suchen und alles was vor der 16 steht ist der linke teilbaum und alles was nach der 16 steht kommt in den rechten teilbaum
weiter weiß ich leider auch nit


so soll am ende der baum aussehen:

                                    16
                                   /   \
                                19      12
                                  \         \
                                   13       25
                                             /  \
                                           21   11
                                           /
                                          23
                                           \
                                            18

ich verstehe diesen baum nicht ich hoffe ihr könnt mir helfen

der baum sieht ein bisschen grausig aus die formatierung ist irgendwie so komisch
25,21,11,23 und 18 hängen unter der 12 und bilden den rechten Teilbaum


wie sieht denn der baum für die folgenden traversierungen(3 traversierungen) aus?

Postorder: r x p m s c f
Inoder: x r f p c m s
Preorder: f x r c p s m

 

[Marco13]

Hab mal kurz geguckt:
1. Sicher dass man aus pre+in ALLEINE den Baum rekonstruieren kann? (Kann sein, wills nur grad nicht selbst prüfen)
2. Sollte bei inorder die Ausgabe nicht mit 13 anfangen?

 

[Mizar]

Bist du dir ganz sicher das dein geposteter Baum stimmt super_junior? Denn wenn ich kurz das Internet durchforste, dann stoße ich unter anderem auf diese beiden Beiträge aus anderen Foren:
inorder vs. preorder vs. postorder (oder: zu blöd für wikipedia) - Forum Fachinformatiker.de
und
Forum "Algorithmen und Datenstrukturen" - Baum aus geg. pre- und inorder - Vorhilfe.de - Vorhilfe
Und nach deren Anleitung, müsste der Baum dann so aussehen, falls ich keinen Fehler gemacht habe:

      16
     /  \
    /    \
   /      \
  /        \
 19        42
   \      /  \
    13   21   25
        /       \
       23        11
         \
          18

EDIT: Und der andere Baum müsste dann ja so aussehen (auch wieder ohne Gewähr ):

     f
    / \
   /   \
  /     \
 /       \
x         c
 \       / \
  \     /   \
   r   p     s
            /
           m

 

[Ezra]

1. Sicher dass man aus pre+in ALLEINE den Baum rekonstruieren kann?

Ja.

2. Sollte bei inorder die Ausgabe nicht mit 13 anfangen?

Nein, die 13 ist rechts von der 19, darum muss die 19 vor der 13 stehen.
Inorder-Reihenfolge ist links - wurzel - rechts.

ich weiß,dass bei preoder die wurzel die 16 ist,weil sie am anfang steht
und dann muss man bei inorder nach der 16 suchen und alles was vor der 16 steht ist der linke teilbaum und alles was nach der 16 steht kommt in den rechten teilbaum
weiter weiß ich leider auch nit

Das Prinzip hast Du doch dann. Jetzt baust Du den linken Teilbaum auf. Entferne dazu alles aus Preorder, was nicht reingehört:
19 13
Ebenso aus Inorder:
19 13
Demnach ist das Preorder für den linken Teilbaum. Wurzel ist 19. Über Inorder weißt Du, dass die 13 rechts stehen muss (sonst wäre Inorder hier: 13 19).

Hast Du den linken Teilbaum, kletterst Du wieder hoch und machst das gleiche für den rechten Teilbaum.
Preorder rechts: 42 21 23 18 25 11
Inorder rechts: 23 18 21 42 25 11
Die 42 ist wieder Wurzel. Nun teilst Du anhand von Inorder wieder rechten und linken Teilbaum auf. Und so weiter.

Edit: Der Ergebnisbaum ist falsch, ja.

 

[Marco13]

Ja.

Nein, die 13 ist rechts von der 19, darum muss die 19 vor der 13 stehen.
Inorder-Reihenfolge ist links - wurzel - rechts.
...

Edit: Der Ergebnisbaum ist falsch, ja.

OK, vielleicht hätte ich die Frage anders formulieren müssen: Bist du sicher, dass man aus DIESER Preorder und DIESER Inorder DIESEN Baum rekonstruieren kann (und DA wäre die Antwort: Nein). Zumindest hatte mich die fehlende Übereinstimmung zum geposteten Baum dazu veranlasst, das hier nach einer Weile "debugging" erstmal so halbfertig aufzugeben

import java.util.*;

class Node
{
    Object value;
    Node left;
    Node right;

    public String toString()
    {
        return String.valueOf(value);
    }
}

class OrderTest
{
    public static void main(String args[])
    {
        List<Object> pre = new ArrayList<Object>();
        List<Object> in = new ArrayList<Object>();

        pre.add(16);
        pre.add(19);
        pre.add(13);
        pre.add(12);
        pre.add(21);
        pre.add(23);
        pre.add(18);
        pre.add(25);
        pre.add(11);

        in.add(19);
        in.add(13);
        in.add(16);
        in.add(23);
        in.add(18);
        in.add(21);
        in.add(12);
        in.add(25);
        in.add(11);

        Node n = build(pre, in, "");
        print(n, "");
    }

    private static void print(Node node, String indent)
    {
        if (node == null)
        {
            System.out.println(indent+"-");
            return;
        }
        System.out.println(indent+node.value);
        print(node.left, indent+"    ");
        print(node.right, indent+"    ");
    }

    private static Node build(List<Object> pre, List<Object> in, String indent)
    {
        if (pre.size() == 0)
        {
            return null;
        }
        if (in.size() == 0)
        {
            return null;
        }
        Object current = pre.remove(0);
        Node n = new Node();
        n.value = current;

        System.out.println(indent+"Build from");
        System.out.println(indent+"pre     "+pre);
        System.out.println(indent+"in      "+in);
        System.out.println(indent+"value "+current);

        int index = in.indexOf(current);
        List<Object> inNextL = Collections.emptyList();
        List<Object> inNextR = Collections.emptyList();
        if (index != -1)
        {
            inNextL = in.subList(0, index);
            inNextR = in.subList(index+1, in.size());
        }


        System.out.println(indent+"preNext "+pre);
        System.out.println(indent+"inNextL "+ inNextL);
        System.out.println(indent+"inNextR "+ inNextR);

        n.left = build(pre, inNextL, indent+"    ");
        n.right = build(pre, inNextR, indent+"    ");

        System.out.println(indent+"left  of "+n+" is "+n.left);
        System.out.println(indent+"right of "+n+" is "+n.right);

        return n;
    }

}

 

[super_junior]

Ja.


Nein, die 13 ist rechts von der 19, darum muss die 19 vor der 13 stehen.
Inorder-Reihenfolge ist links - wurzel - rechts.


Das Prinzip hast Du doch dann. Jetzt baust Du den linken Teilbaum auf. Entferne dazu alles aus Preorder, was nicht reingehört:
19 13
Ebenso aus Inorder:
19 13
Demnach ist das Preorder für den linken Teilbaum. Wurzel ist 19. Über Inorder weißt Du, dass die 13 rechts stehen muss (sonst wäre Inorder hier: 13 19).

Hast Du den linken Teilbaum, kletterst Du wieder hoch und machst das gleiche für den rechten Teilbaum.
Preorder rechts: 42 21 23 18 25 11
Inorder rechts: 23 18 21 42 25 11
Die 42 ist wieder Wurzel. Nun teilst Du anhand von Inorder wieder rechten und linken Teilbaum auf. Und so weiter.

Edit: Der Ergebnisbaum ist falsch, ja.

"Preorder rechts: 42 21 23 18 25 11
Inorder rechts: 23 18 21 42 25 11
Die 42 ist wieder Wurzel. Nun teilst Du anhand von Inorder wieder rechten und linken Teilbaum auf. Und so weiter."

dankeschöön
ich weiß nur nit ob ich es jetzt richtig verstanden habe

also 42 ist jetzt dann wieder die neue wurzel

21,23,18 kommen jetzt in den linken teilbaum und 25 und 11 in den rechten teilbaum

21 ist wieder die neue wurzel
da sie links von der 42 steht bei inorder kommt sie links von der 42
und 23 ist nun die neue wurzel sie kommt dann links von der 21,weil sie bei inorder links von der 21 steht
und dann ist 18 die neue wurzel bei inorder steht sie rechts von 23(der neuen wurzel) wird sie rechts drangehängt

und bei 25 steht rechts von42 deshalb kommt sie rechts hin usw

ist der ansatz so richtig??

 

[super_junior]

ich hätte da noch eine frage

wäre es auch möglich nur mit post und preorder einen baum zu basteln?
das finde ich irgendwie ziemlich tricky,denn man kann dann nit genau identifizieren welche elemente in den linken und welche in den rechten teilbaum gehören

vielen dank

 

[Landei]

Wenn man die In-Order- und Post-Order-Liste umdreht, was hat man da? Denk mal drüber nach, dann findest du die Antwort auf deine Frage selber.

 

[Marco13]

Wenn man die In-Order- und Post-Order-Liste umdreht, was hat man da? Denk mal drüber nach, dann findest du die Antwort auf deine Frage selber.

Zugegeben: Drüber nachgedacht habe ich nicht, aber es würde mich auch interessieren, worauf du raus willst. Du brauchst es nicht zu sagen, nur folgendes zu bestätigen oder verneinen: Du willst NICHT andeuten, dass man durch Umdrehen der In- oder Post-Order-Liste die Pre-Order-Liste bekommt.

 

[Landei]

Nicht ganz, aber fast. Wenn ich richtig gedacht habe, kannst du nach dem Umdrehen der beiden Listen den gleichen Algorithmus wie für pre-order und in-order nehmen, nur das die entstehenden Bäume "gespiegelt" sind (und am Ende sozusagen wieder "zurückgedreht" werden müssen)

 

[Marco13]

Das kann sein, soweit hatte ich jetzt nicht überlegt, wollte nur verhindern dass er etwas versucht, was vielleicht nicht geht

 

[Landei]

pre-order ist W-L-R, in-order ist L-W-R

post-order ist L-R-W, gespiegelt W-R-L, in-order gespiegelt ist R-W-L

Also hat man W-R-L und R-W-L. Wenn man den gleichen Algorithmus wie bei (W-L-R, L-W-R) verwendet, und einfach beim Aufbau des Baums R und L vertauscht, sollte es passen.