Hoe werkt de zoekfunctie in de boom?

Zoektocht in een boom hangt af van de structuur en het doel van de zoektocht.

Belangrijkste zoekmethoden:

Diepte-eerst zoeken (DFS - Depth-First Search): Gaat zo diep mogelijk in een tak voordat hij naar de volgende gaat. Wordt geïmplementeerd met een stack (expliciet of impliciet via recursie).
- Pre-order: Bezoek de wortel, dan de linker subboom, dan de rechter subboom.
- In-order: Bezoek de linker subboom, dan de wortel, dan de rechter subboom. Gebruikt in binaire zoekbomen om een gesorteerde lijst van elementen te verkrijgen.
- Post-order: Bezoek de linker subboom, dan de rechter, dan de wortel.
Breadth-first zoeken (BFS - Breadth-First Search): Verken alle buren van de huidige knoop op één niveau voordat je naar het volgende niveau gaat. Wordt geïmplementeerd met een wachtrij.

Voorbeeld van DFS (In-order) voor een binaire boom:

// TreeNode vertegenwoordigt een knoop van een binaire boom
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// InOrderTraversal voert een inorder doorloop uit
func InOrderTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Recursieve oproep voor de linker subboom
	result = append(result, InOrderTraversal(root.Left)...)
	// Bezoek de huidige knoop
	result = append(result, root.Val)
	// Recursieve oproep voor de rechter subboom
	result = append(result, InOrderTraversal(root.Right)...)

	return result
}

Voorbeeld van BFS:

// TreeNode vertegenwoordigt een knoop van een binaire boom
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// BFSTraversal voert een BFS door
func BFSTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Wachtrij voor het opslaan van knopen op het huidige niveau
	queue := []*TreeNode{root}

	for len(queue) > 0 {
		// Verwijder het eerste element uit de wachtrij
		node := queue[0]
		queue = queue[1:]

		// Voeg de waarde van de knoop toe aan het resultaat
		result = append(result, node.Val)

		// Voeg het linker kind toe aan de wachtrij als het bestaat
		if node.Left != nil {
			queue = append(queue, node.Left)
		}
		// Voeg het rechter kind toe aan de wachtrij als het bestaat
		if node.Right != nil {
			queue = append(queue, node.Right)
		}
	}
	return result
}

Voor binaire zoekbomen (BST), waar het linker subboom kleiner is dan de wortel en het rechter groter:

Binaire zoekopdracht: Bij het zoeken naar een specifieke waarde wordt deze vergeleken met de wortel. Als de waarde kleiner is, zoeken we in het linker subboom; als groter, in het rechter. Dit is de meest efficiënte strategie voor zoeken in BST.

// TreeNode vertegenwoordigt een knoop van een binaire zoekboom
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// SearchBST voert een binaire zoekopdracht uit in een BST
func SearchBST(root *TreeNode, target int) *TreeNode {
	if root == nil || root.Val == target {
		return root // Knoop gevonden of boom leeg
	}

	if target < root.Val {
		// Zoeken in het linker subboom
		return SearchBST(root.Left, target)
	}
	// Zoeken in het rechter subboom
	return SearchBST(root.Right, target)
}

De keuze van het zoekalgoritme hangt af van de taak en de kenmerken van de boom. DFS is geschikt voor taken waarbij je diep in een tak moet gaan of een pad naar een doel moet vinden. BFS is geschikt voor het vinden van de kortste weg of het doorlopen op niveaus. Binaire zoekopdracht is efficiënt voor het zoeken naar een specifieke waarde in gesorteerde structuren zoals BST.