Как работи търсенето в дървото?

Търсенето в дърво зависи от неговата структура и целта на търсенето.

Основните методи за търсене са:

Търсене в дълбочина (DFS - Depth-First Search): Проходи възможно най-дълбоко по един клон, преди да премине към съседен. Реализира се с използване на стек (явно или чрез рекурсия).
- Предварително посещение (Pre-order): Посети корена, след това левото поддърво, след това дясното поддърво.
- Вътрешно посещение (In-order): Посети левото поддърво, след това корена, след това дясното поддърво. Използва се за получаване на сортиран списък от елементи в двоични дървета за търсене.
- Пост-ред (Post-order): Посети левото поддърво, след това дясното поддърво, след това корена.
Търсене по ширина (BFS - Breadth-First Search): Проучва всички съседни на текущия възел на един ниво, преди да премине към следващото. Реализира се с помощта на опашка.

Пример за DFS (In-order) за двоично дърво:

// TreeNode представлява възел на двоично дърво
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// InOrderTraversal извършва inorder обход
func InOrderTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Рекурсивен вик за левия поддърво
	result = append(result, InOrderTraversal(root.Left)...)
	// Посещение на текущия възел
	result = append(result, root.Val)
	// Рекурсивен вик за десния поддърво
	result = append(result, InOrderTraversal(root.Right)...)

	return result
}

Пример за BFS:

// TreeNode представлява възел на двоично дърво
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// BFSTraversal извършва BFS обход
func BFSTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Опашка за съхранение на възлите на текущото ниво
	queue := []*TreeNode{root}

	for len(queue) > 0 {
		// Извличане на първия елемент от опашката
		node := queue[0]
		queue = queue[1:]

		// Добавяне на стойността на възела към резултата
		result = append(result, node.Val)

		// Добавяне на левия наследник, ако съществува
		if node.Left != nil {
			queue = append(queue, node.Left)
		}
		// Добавяне на десния наследник, ако съществува
		if node.Right != nil {
			queue = append(queue, node.Right)
		}
	}
	return result
}

За двоични дървета за търсене (BST), където левият поддърво е по-малък от корена, а десният е по-голям:

Двоично търсене: При търсене на конкретна стойност сравняваме с корена. Ако стойността е по-малка, търсим в левия поддърво; ако е по-голяма, в десния. Това е най-ефективната стратегия за търсене в BST.

// TreeNode представлява възел на двоично дърво за търсене
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// SearchBST извършва двоично търсене в BST
func SearchBST(root *TreeNode, target int) *TreeNode {
	if root == nil || root.Val == target {
		return root // Възелът е намерен или дървото е празно
	}

	if target < root.Val {
		// Търсене в левия поддърво
		return SearchBST(root.Left, target)
	}
	// Търсене в десния поддърво
	return SearchBST(root.Right, target)
}

Изборът на алгоритъм за търсене зависи от задачата и характеристиките на дървото. DFS е подходящ за случаи, когато трябва да се премине дълбоко по една клонка или да се намери път към целта. BFS е подходящ за намиране на най-краткия път или обход по нива. Двоичното търсене е ефективно за намиране на конкретна стойност в сортирани структури като BST.