Cum funcționează căutarea în arbore?

Căutarea într-un copac depinde de structura sa și de scopul căutării.

Principalele metode de căutare:

Căutarea în adâncime (DFS - Depth-First Search): Se duce cât mai adânc într-o ramură înainte de a trece la alta. Se implementează folosind o stivă (explicit sau implicit prin recursie).
- Traversare pre-ordine: Vizitează rădăcina, apoi subarborele stâng, apoi cel drept.
- Traversare în ordine (In-order): Vizitează subarborele stâng, apoi rădăcina, apoi subarborele drept. Folosit în arborii binari de căutare pentru a obține o listă sortată de elemente.
- Traversare post-ordine: Vizitează subarborele stâng, apoi cel drept, apoi rădăcina.
Căutarea în lățime (BFS - Breadth-First Search): Explorează toți vecinii nodului curent pe un nivel înainte de a trece la nivelul următor. Se implementează folosind o coadă.

Exemplu DFS (In-order) pentru un arbore binar:

// TreeNode reprezintă un nod al unui arbore binar
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// InOrderTraversal efectuează o traversare inorder
func InOrderTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Apel recursiv pentru subarborele stâng
	result = append(result, InOrderTraversal(root.Left)...)
	// Vizitează nodul curent
	result = append(result, root.Val)
	// Apel recursiv pentru subarborele drept
	result = append(result, InOrderTraversal(root.Right)...)

	return result
}

Exemplu BFS:

// TreeNode reprezintă un nod al unui arbore binar
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// BFSTraversal efectuează o traversare BFS
func BFSTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Coada pentru stocarea nodurilor la nivelul curent
	queue := []*TreeNode{root}

	for len(queue) > 0 {
		// Extrage primul element din coadă
		node := queue[0]
		queue = queue[1:]

		// Adaugă valoarea nodului în rezultat
		result = append(result, node.Val)

		// Adaugă copilul stâng în coadă dacă există
		if node.Left != nil {
			queue = append(queue, node.Left)
		}
		// Adaugă copilul drept în coadă dacă există
		if node.Right != nil {
			queue = append(queue, node.Right)
		}
	}
	return result
}

Pentru arborii binari de căutare (BST), unde subarborele stâng este mai mic decât rădăcina, iar cel drept este mai mare:

Căutare binară: La căutarea unei valori specifice, o comparăm cu rădăcina. Dacă valoarea este mai mică, căutăm în subarborele stâng; dacă este mai mare, în cel drept. Aceasta este strategia cea mai eficientă pentru căutarea în BST.

// TreeNode reprezintă un nod al unui arbore binar de căutare
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// SearchBST efectuează o căutare binară în BST
func SearchBST(root *TreeNode, target int) *TreeNode {
	if root == nil || root.Val == target {
		return root // Nod găsit sau arbore gol
	}

	if target < root.Val {
		// Caută în subarborele stâng
		return SearchBST(root.Left, target)
	}
	// Caută în subarborele drept
	return SearchBST(root.Right, target)
}

Alegerea algoritmului de căutare depinde de sarcină și de caracteristicile arborelui. DFS este potrivit pentru sarcini în care trebuie să parcurgi adânc într-o ramură sau să găsești un drum către un scop. BFS este potrivit pentru a găsi cel mai scurt drum sau pentru traversarea pe niveluri. Căutarea binară este eficientă pentru găsirea unei valori specifice în structuri sortate, precum BST.