Wie funktioniert die Suche im Baum?

Die Suche in einem Baum hängt von seiner Struktur und dem Suchziel ab.

Hauptsächliche Suchmethoden:

1. Tiefensuche (DFS - Depth-First Search): Geht so tief wie möglich in einen Zweig, bevor er zum nächsten wechselt. Wird mit einem Stack (explizit oder implizit durch Rekursion) implementiert.

   • Pre-Order (Vorzugsdurchlauf): Besuch des Wurzelknotens, dann des linken Teilbaums, dann des rechten Teilbaums.
   • In-Order (In-Order Traversierung): Besuch des linken Teilbaums, dann des Wurzelknotens, dann des rechten Teilbaums. Wird bei binären Suchbäumen verwendet, um eine sortierte Liste der Elemente zu erhalten.
   • Post-Order (Post-Order Traversierung): Besuch des linken Teilbaums, dann des rechten, dann des Wurzelknotens.

2. Breitensuche (BFS - Breadth-First Search): Erkundet alle Nachbarn des aktuellen Knotens auf einer Ebene, bevor es zur nächsten Ebene geht. Wird mit einer Warteschlange implementiert.

Beispiel DFS (In-Order) für einen binären Baum:

// TreeNode repräsentiert einen Knoten eines binären Baumes
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// InOrderTraversal führt eine In-Order-Traversierung durch
func InOrderTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Rekursive Aufrufe für den linken Teilbaum
	result = append(result, InOrderTraversal(root.Left)...)
	// Besuch des aktuellen Knotens
	result = append(result, root.Val)
	// Rekursive Aufrufe für den rechten Teilbaum
	result = append(result, InOrderTraversal(root.Right)...)

	return result
}

Beispiel BFS:

// TreeNode repräsentiert einen Knoten eines binären Baumes
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// BFSTraversal führt eine BFS-Traversierung durch
func BFSTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Warteschlange zur Speicherung der Knoten auf der aktuellen Ebene
	queue := []*TreeNode{root}

	for len(queue) > 0 {
		// Erstes Element aus der Warteschlange entfernen
		node := queue[0]
		queue = queue[1:]

		// Wert des Knotens zum Ergebnis hinzufügen
		result = append(result, node.Val)

		// Linkes Kind hinzufügen, falls vorhanden
		if node.Left != nil {
			queue = append(queue, node.Left)
		}
		// Rechtes Kind hinzufügen, falls vorhanden
		if node.Right != nil {
			queue = append(queue, node.Right)
		}
	}
	return result
}

Für binäre Suchbäume (BST), bei denen das linke Teilbaum kleiner und das rechte größer ist:

3. Binäre Suche: Beim Suchen eines bestimmten Wertes wird dieser mit der Wurzel verglichen. Ist der Wert kleiner, wird im linken Teilbaum gesucht; ist er größer, im rechten. Dies ist die effizienteste Suchstrategie in BST.

// TreeNode repräsentiert einen Knoten eines binären Suchbaumes
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// SearchBST führt eine binäre Suche im BST durch
func SearchBST(root *TreeNode, target int) *TreeNode {
	if root == nil || root.Val == target {
		return root // Knoten gefunden oder Baum ist leer
	}

	if target < root.Val {
		// Suche im linken Teilbaum
		return SearchBST(root.Left, target)
	}
	// Suche im rechten Teilbaum
	return SearchBST(root.Right, target)
}

Die Wahl des Suchalgorithmus hängt von der Aufgabe und den Eigenschaften des Baumes ab. DFS eignet sich für Aufgaben, bei denen tief in eine Zweig gegangen werden muss oder ein Pfad zum Ziel gesucht wird. BFS ist geeignet, um den kürzesten Weg zu finden oder nach Ebenen zu traversieren. Binäre Suche ist effizient, um einen bestimmten Wert in sortierten Strukturen wie BST zu finden.