Baum pfadweise durchlaufen

[Esther.Greenwood]

Hallo,
ich kenne für Bäume die preorder-, postorder- und inorder-Traversierung. Nun möchte ich aber bei einem Binärbaum alle Pfade miteinander vergleichen, d. h. Pfad für Pfad von Wurzel bis Blatt durchgehen und dabei eine bestimmte Art von Knoten zählen. Mir fehlt hier der zündende Gedanke, wie ich anfangen könnte.

Vielen Dank für jede Hilfe.

 

[httpdigest]

Jede Traversierungsart besucht immer alle Knoten im Baum. Was genau meinst du jetzt mit "alle Pfade miteinander vergleichen" und "dabei eine bestimmte Art von Knoten zählen"? Am besten anhand eines Beispiels.

 

[Esther.Greenwood]

Ich möchte die vertikalen Pfade von der Wurzel zu den Blättern miteinander vergleichen. Ich habe einen rot-schwarz-Baum und möchte jeweils die Vorkommen der schwarzen Knoten zählen.

Als Beispiel würde ich bei diesem Baum:
https://images.app.goo.gl/TKyz7KS6rATZUvFP7
die folgenden Pfade ablaufen wollen: 3-2-1; 3-7-5-4; 3-7-5-6; 3-7-9-8; 3-7-9-10

 

[httpdigest]

Also, du willst die Invariante eines red-black Trees testen, die besagt, dass jeder Pfad von der Wurzel zu einem Blattknoten die gleiche Anzahl an schwarzen Knoten aufweisen muss.
Das heißt, du willst eine Methode, die einen Baum bekommt und boolean zurückliefert. Also ein Prädikat, welches genau diese Invariante evaluiert.

 

[Esther.Greenwood]

Genau! Die Frage ist eben nur, wie ich das erreichen kann. Ich muss ja zuerst alle schwarzen Knoten auf den verschiedenen Pfaden von einem Knoten zur Wurzel zählen, um dann zu überprüfen, ob die Anzahl überall gleich ist. Das Zählen bereitet mir jedoch schon die Probleme, weil mir nichts einfällt, wie ich die Pfade nachlaufen kann.

 

[httpdigest]

Rekursion. Baue dir einfach eine Methode, die die Anzahl der schwarzen Knoten pro Teilbaum/Knoten zurückliefert und die gleichzeitig prüft, ob die Anzahl in dem linken Teilbaum gleich der Anzahl in dem rechten Teilbaum ist. Fertig.

 

[httpdigest]

Hier ist eine mögliche Lösung für einen abstrakten RedBlack Tree mit den Operationen `isLeaf()`, `isBlack()`, `getLeft()`, `getRight()`:

import java.util.Optional;
...
public boolean isValid() {
    return countBlacksAndValidate().isPresent();
}
private Optional<Integer> countBlacksAndValidate() {
    return !isLeaf()
        ? getLeft().countBlacksAndValidate()
              .filter(getRight().countBlacksAndValidate().orElse(-1)::equals)
              .map(v -> v + (isBlack() ? 1 : 0))
        : Optional.of(isBlack() ? 1 : 0);
}

 

[Susi123]

Wenn ich folgenden Baum als Beispiel nehme:



Ist das dann richtig, dass die Ziffern in folgender Reihenfolge ausgegeben werden?
Ich bin mir da ziemlich unsicher, ob ich die Reihenfolge innerhalb eines Teilbaums richtig eingehalten habe.
Postorder: erst der linke, dann der rechte Teilbaum, danach die Wurzel
1, 8, 3, 5, 9, 0, 7, 4, 6

Preorder: Wurzel wird zuerst ausgegeben, dann linker, dann rechter Teilbaum.
6, 5, 1, 3, 8, 4, 9, 7, 0

Inorder: erst der linke Teilbaum, dann die Wurzel, danach rechter Teilbaum
1, 8, 3, 5, 6, 9, 0, 7, 4

 

[mihe7]

Inorder: erst der linke Teilbaum, dann die Wurzel, danach rechter Teilbaum

Wenn ich mich grad nicht vertue: 1,5,8,3,6,9,4,7,0

 

[Susi123]

Der Rest passt so?

 

[mihe7]

Jo.

 

[Xyz1]

Tree Traversal Techniques - Data Structure and Algorithm Tutorials - GeeksforGeeks

A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.

www.geeksforgeeks.org

Ich muss ja zuerst alle schwarzen Knoten auf den verschiedenen Pfaden von einem Knoten zur Wurzel zählen, um dann zu überprüfen, ob die Anzahl überall gleich ist

Aber das hat doch mit der Traversierungsreihenfolge nichts zu tun, denn die Anzahl ist immer gleich...