Merkt Euch:
Auch dieser Text ist eine Hilfestellung fuer Euch und wahrscheinlich
nicht fehlerfrei. Deshalb gilt auch hier: Alle Angaben ohne Gewaehr!
Letztlich gilt als Referenz (bzw. letzte Instanz) immer das Skript
bzw. Herr Schweiggert!
Entdeckt Ihr irgendwelche Fehler, dann bitte ne EMail direkt an mich 
senden oder das anonyme Feedback verwenden!!!

Eigenschaften von Baeumen - Kurz und Knapp

Baum B mit Knoten:                        Baum B mit Werten:
                xo          Ebene 0                 6
               /  \                                / \
              /    \                              /   \
             /      \                            /     \
            x1      x6      Ebene 1             2       7
           /  \                                / \
          /    \                              /   \  
         /      \                            /     \
        x2      x3          Ebene 2         1       4
               /  \                                / \
              /    \                              /   \
             /      \                            /     \
            x4      x5      Ebene 3             3       5


Knotenmenge: { x0, x1, x2, x3, x4, x5, x6 }
Kantenmenge: { (x0,x1), (x1,x2), (x1,x3), (x3,x4), (x3,x5), (x0,x6) }
Wertmenge: { 6, 3, 1, 4, 3, 5, 7 }

Wurzelknoten: x0

Vorgaenger von x3: x1
Vorgaenger von x1: x0
Vorgaenger von x0: ex. nicht
(Jeder Knoten hat genau 1 Vorgaenger, ausser der Wurzel)

Nachfolger von x3: x4, x5
Nachfolger von x1: x2, x3
Nachfolger von x2: ex. nicht
(Blattknoten haben keine Nachfolger)

Grad von x3: 2
Grad von x1: 2
Grad von x2: 0

Blattknoten: x2, x4, x5, x6

Weglaenge x1 - x5: 2
Weglaenge x1 - x2: 1
Weglaenge x0 - x4: 3
(Anzahl der Kanten zwischen den Knoten)

Hoehe von x0: 0
Hoehe von x1: 1
Hoehe von x5: 3
(Anzahl Kanten von der Wurzel bis zu diesem Knoten)

Hoehe von B (Baum): 4
(Anzahl Knoten einschl. der Wurzel bis zum "weit entferntesten" Blatt bwz. 
Max(aller Knotenhoehen) + 1)

Nachkommen von x1: x2, x3, x4, x5
Nachkommen von x2: ex. nicht
Nachkommen von x3: x4, x5

Definition 11:
Was ist ein Teilbaum: Betrachte z.B. Knoten x3
Dann ist der Baum mit Wurzelknoten x3 und den Knoten x4, x5 ein Teilbaum
(Hier ist beschrieben was ein Teilbaum ist)

Definition 13:
Linker Teilbaum von x3: x4 (Hoehe = 1)
Rechter Teilbaum von x3: x5 (Hoehe = 1)
Linker Teilbaum von x1: x2 (Hoehe = 1)
Rechter Teilbaum von x1: x3, x4, x5 (Hoehe = 2)
Linker Teilbaum von x2: ex. nicht (Hoehe = 0)
Rechter Teilbaum von x2: ex. nicht (Hoehe = 0)
(Hier ist beschrieben was ein (linker bzw. rechter) Teilbaum BEZUEGLICH
eines Knotens ist)

Der Baum B mit Werten ist geordnet.

Beim Baum B handelt es sich um einen Binaerbaum

B ist nicht nach Hoehe ausgeglichen, da 
Hoehe Rechter Teilbaum von x0 = 3 und
Hoehe Linker Teilbaum von x0 = 1 ist!
(Achtung: Die Hoehe aller Teilbaeume muss verglichen werden, d.h. also
man nehme Knoten x0 vergleiche linken TB und rechten TB, dann lTB und rTB 
von Knoten x1 vergleichen, dann weiter mit Knoten x2 usw. bis Knoten x6!)

B ist auch nicht Gewichtsausgeglichen, da 
der Baum nicht Hoehenausgeglichen ist.
(Achtung: Auch hier gilt: Ihr musst alle Teilbaume jedes Knotens betrachten,
und dann die Gewichte von linken bzw. rechten Teilbaum vergleichen)!