Eigenschaften von Baeumen

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 (vgl. Skript S. 89):
(Hier ist beschrieben was ein Teilbaum ist!)
Was ist ein Teilbaum: Betrachte z.B. Knoten x3
Dann ist der Baum mit Wurzelknoten x3 und den Knoten x4, x5 ein Teilbaum

Definition 13 (vgl. Skript S. 89):
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 ist ein geordneter 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)!