Twitter und Facebook-Anbindung
X
Tweet Follow @twitterapi
!!! Anbindung an twitter und facebook öffnen !!!

Wenn Ihnen mein Online-Buch gefällt,
dann bedanken Sie sich doch mit einer kleinen Spende...

10.3 Bäume

10.3 Bäume

Ein Baum besteht aus einer "Wurzel", welche auf andere Bäume werweist. Die Liste ist ein Spezialfall des Baumes. Man hat wieder ein Wurzelelement mit mehreren Zeigern, welche auf unterschiedliche Elemente verweisen. Dieses Prinzip lässt sich an einem Stammbaum gut veranschaulichen.

Grundschema eines Binärbaumes

Das erste Element heißt wie gesagt "Wurzel" oder auch "Vaterelement". Die Zeiger sind "Zweige" und verweisen auf die "Tochterelemente" oder auch "Knotenpunkt" genannt. Jene können ihrerseits Wurzelelemente von Unterbäumen, also "Ästen" sein. Die letzten Elemente an einem Baum, nennt man "Blätter". Die zwei Zeiger in den Blattelementen, zeigen auf "NULL".

Zum Anlegen und Löschen von Elementen in einem Baum, ist es zwingend notwendig zu wissen, wie man erst einmal ein Element findet, an welches man ein weiteren Baum anhängen oder löschen will. Hierfür gibt es drei Methoden, mit denen man wirklich jedes Element in einem Baum findet.

Alle drei Methoden funktionieren ähnlich und sind Rekursiv. Man geht immer nach links, bis man "NULL" erreicht. Danach schaut man, ob es nach rechts geht. Ist dies der Fall, tut man dies einmal und geht wieder immer nach links, bis man letztendlich ein Blatt erreicht, also eines der letzten Elemente. Danach geht man wieder einen Schritt zurück, also zum Vaterelement des Blattes. Dort wieder angelangt, geht man nach rechts, es sei denn, man war dort schon. In diesem Fall geht man wieder ein Schritt zurück und so weiter. Der Unterschied zwischen diesen drei Verfahren, ist der Zeitpunkt der Ausgabe der Werte. Ich werde dies nun an einem Beispiel verdeutlichen:

Ausgeglichener Binärbaum mit sortierten numerischen Elementen

Zum Seitenanfang
Zum Inhaltsverzeichnis

10.3.2 Inorder

10.3.2 Inorder

Inorder heißt, die Ausgabe erfolgt mittendrin, also erst das nach links gehen, dann die Ausgabe und schließlich das nach rechts Gehen.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
					
// ...

// Erst links, dann Ausgabe, dann rechts //////////////////////////////////////
void InorderPrint(PIntegerTreeItem pHelpItem) {
	// Rekursionsbedingung
	if (pHelpItem != NULL)  {
		// Selbstaufruf der Funktion (nach links gehen)
		InorderPrint(pHelpItem->pLeftItem);

		printf("%i ", pHelpItem->iValue);

		// Selbstaufruf der Funktion (nach rechts gehen)
		InorderPrint(pHelpItem->pRightItem);
	} // end of if
} // InorderPrint /////////////////////////////////////////////////////////////

// ...

InorderPrint(pRootItem);

// ...
					

Ausgabe:

25 50 75 100 125 150 175
		

Dieses Verfahren ist das am häufigsten verwendetest. Wenn der Computer z.B. ein Verzeichnis mit allen Unterverzeichnissen und seinen Dateien auf ein Schlüsselwort durchsucht, geht er so vor.

Zum Seitenanfang
Zum Inhaltsverzeichnis

10.3.1 Preorder

10.3.1 Preorder

Preorder heißt, es erfolgt erst die Ausgabe, dann das nach links Gehen und schließlich das nach rechts Gehen.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
					
// ...

// Erst Ausgabe, dann links, dann rechts //////////////////////////////////////
void PreorderPrint(PIntegerTreeItem pHelpItem) {
	// Rekursionsbedingung
	if (pHelpItem != NULL)  {
		printf("%i ", pHelpItem->iValue);
		
		// Selbstaufruf der Funktion (nach links gehen)
		PreorderPrint(pHelpItem->pLeftItem);
		// Selbstaufruf der Funktion (nach rechts gehen)
		PreorderPrint(pHelpItem->pRightItem);
	} // end of if
} // PreorderPrint ////////////////////////////////////////////////////////////

// ...

PreorderPrint(pRootItem);

// ...
					

Ausgabe:

100 50 25 75 150 125 175
		

Erklärung

Wird die Funktion aufgerufen, wird zunächst einmal der Zeiger übergeben, welcher auf das Wurzelelement verweist. Die Variable "pHelpItem" erhält nun diese Adresse/Referenz. Nun beginnt die Suche, es sei denn, der Baum ist leer. Als erstes wird der erste Wert ausgegeben, die "100". Jetzt ruft sich die Funktion erneut auf und übergibt den Zeiger, welcher auf den linken Baum zeigt. Die Variable "pHelpItem" zeigt nun auf das linke Tochterelement. Da hier noch nicht Schluss ist, wird die "50" ausgegeben und der Zeiger nach links wird wieder, im Selbstaufruf der Funktion, übergeben. Das Laufelement verweist wiederum auf die nächste linke Tochter (Enkelin). Auch hier ist noch nicht Schluss, also das Hilfselement ist nicht "NULL". Die "25" wird ausgegeben. Auch jetzt findet wieder der Selbstaufruf statt. Da aber nun "NULL" übergeben wird, läuft die Funktion normal durch, überspringt aber die if Anweisung. Die Funktion ist beendet. Aber nun sind ja noch Aufgaben offen. Der Computer springt zurück an die Stelle, wo er das letzte Mal nach links gegangen ist und setzt dort gleich wieder mit dem nächsten Befehl ein. In diesem Fall wäre dies jetzt der Selbstaufruf nach Rechts. Auch hier wird "NULL" übergeben. Dieser Unterast ist nun abgearbeitet. Der Computer springt ein weiteres Mal zurück, weil immer noch Aufgaben ausstehen. Wiederum steht als nächstes der Selbstaufruf an und ein Zeiger nach rechts wird wieder übergeben. Das Hilfselement verweist nun auf das rechte Tochterelement, des linken Tochterelementes des Wurzelelementes. Nun wird die "75" ausgegeben und es findet wieder ein Selbstaufruf nach links statt.
...

Hat der Computer alle Aufgaben erledigt, so ist die Rekursion beendet und man hat alle Werte.

Zum Seitenanfang
Zum Inhaltsverzeichnis

10.3.4 Löschen von Elementen

10.3.4 Löschen von Elementen

Das Erstellen von Bäumen kann man nicht verallgemeinern, da die Kriterien für die Ordnung im Baum je nach Aufgabenstellung unterschiedlich sein können. Oftmals ist der Baum auch nicht sortiert und oder ausgeglichen, also der linke Ast ist beispielsweise viel größer als der rechte.

Das Löschen eines kompletten Baumes ist jedoch einfach. Um alle Elemente zu löschen, muss man erst einmal alle finden. Wie dies funktioniert, habe ich eben beschrieben. Man nimmt hierfür immer die Postorder. Anstatt der Ausgabe steht nun ein "delete" (bzw. ein "free", wenn man mit "malloc" arbeitet).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
					
// ...

// Löscht ein Element/Ast aus dem Baum ////////////////////////////////////////
void DeleteTree(PIntegerTreeItem pHelpItem) {
	// Rekursionsbedingung
	if (pHelpItem != NULL) {
		DeleteTree(pHelpItem->pLeftItem);
		DeleteTree(pHelpItem->pRightItem);

		delete pHelpItem;
	} // end of if
} // DeleteTree ///////////////////////////////////////////////////////////////

// ...

DeleteTree(pRootItem);

// ...
					

Andere Verfahren würden die Knotenpunkte frühzeitig löschen und man könnte alle Unterbäume an ihnen nicht mehr freigeben. Mit Preorder würde beispielsweise gleich das Wurzelelement gelöscht werden, jedoch nicht seine Äste. Was dies zur Folge hat, wurde von mir bereits erwähnt.

Wenn man ein einzelnes Element aus dem Baum löschen will, so bedarf es ein wenig Denkarbeit. Zunächst muss man das entsprechende Element suchen (wie, ist egal) und dann muss man prüfen, um was es sich für ein Element handelt. Hierbei können vier Fälle auftreten.

Abschließend möchte ich zu diesem Thema noch sagen, dass das Sortieren von Bäumen mindestens genauso spaßig ist, wie das Löschen. Im Endeffekt läuft es aber darauf hinaus, dass man so lange Element sucht, welche nicht an der richtigen Stelle stehen, bis alles ok ist. Die falsch positionierten Elemente löscht man aus dem Baum (also nur abhängen und nicht freigeben) und sortiert sie anschließend neu ein (man lässt sie durch rieseln). Alternativ kann man auch einen komplett neuen Baum aufbauen, was aber nicht unbedingt schneller sein muss (auch wenn man es im ersten Moment vermuten könnte). Allerdings sortiert man nicht im Nachhinein Bäume, sondern sorgt gleich beim aufbauen, dass eine Sortierung vorliegt. Dafür gibt es auch verschiedene Konzepte, wie z.B. s.g. AVL-Bäume, Rot-Schwarz-Bäume oder die s.g. B bzw. B* Bäume. Für die entsprechenden Konzepte gibt es dann auch spezielle Regeln, wie Elemente gelöscht werden. Da dies aber eher in die theoretische Informatik geht und ich mich mehr auf C bzw. C++ konzentrieren möchte, belasse ich es hiermit dabei. Notfalls wissen Sie jetzt aber, über welche Themen Sie sich noch informieren müssten.

Zum Seitenanfang
Zum Inhaltsverzeichnis

10.3.3 Postorder

10.3.3 Postorder

Postorder heißt, die Ausgabe erfolgt als letztes, also erst das nach links gehen, dann das nach rechts gehen und erst danach die Ausgabe.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
					
// ...

// Erst links, dann rechts, dann Ausgabe //////////////////////////////////////
void PreorderPrint(PIntegerTreeItem pHelpItem) {
	// Rekursionsbedingung
	if (pHelpItem != NULL)  {
		// Selbstaufruf der Funktion (nach links gehen)
		PostorderPrint(pHelpItem->pLeftItem);
		// Selbstaufruf der Funktion (nach rechts gehen)
		PostorderPrint(pHelpItem->pRightItem);

		printf("%i ", pHelpItem->iValue);
	} // end of if
} // PreorderPrint ////////////////////////////////////////////////////////////

// ...

PostorderPrint(pRootItem);

// ...
					

Ausgabe:

25 75 50 125 175 150 100
		
Zum Seitenanfang
Zum Inhaltsverzeichnis

© Copyright by Thomas Weiß, 2009 - 2012