Ağaçta arama nasıl çalışır?

Bir ağaçta arama, yapısına ve arama amacına bağlıdır.

Ana arama yöntemleri:

1. Derinlik Öncelikli Arama (DFS - Depth-First Search): Bir dalda mümkün olan en derine iner, sonra diğerine geçer. Yığın (stack) kullanılarak uygulanır (açık veya örtük olarak rekürsiyonla).

   • Ön sıralama (Pre-order): Kökü ziyaret et, sonra sol alt ağacı, sonra sağ alt ağacı.
   • Sıralı gezinme (In-order): Sol alt ağacı ziyaret et, sonra kökü, sonra sağ alt ağacı. Sıralı liste elde etmek için ikili arama ağaçlarında kullanılır.
   • Post-sıralama (Post-order): Sol alt ağacı ziyaret et, sonra sağ alt ağacı, sonra kökü.

2. Genişlik Öncelikli Arama (BFS - Breadth-First Search): Aynı seviyedeki tüm komşuları keşfeder, sonra bir sonraki seviyeye geçer. Kuyruk kullanılır.

İkili ağaçlar (DFS ve BFS) için örnekler:

// TreeNode ikili ağaç düğümünü temsil eder
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// InOrderTraversal inorder gezinmeyi gerçekleştirir
func InOrderTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Sol alt ağaç için rekürsif çağrı
	result = append(result, InOrderTraversal(root.Left)...)
	// Düğüm ziyaret et
	result = append(result, root.Val)
	// Sağ alt ağaç için rekürsif çağrı
	result = append(result, InOrderTraversal(root.Right)...)

	return result
}

// BFSTraversal BFS gezinmeyi gerçekleştirir
func BFSTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Mevcut seviyedeki düğümleri tutan kuyruk
	queue := []*TreeNode{root}

	for len(queue) > 0 {
		// Kuyruğun ilk elemanını çıkar
		node := queue[0]
		queue = queue[1:]

		// Düğüm değerini sonucu ekle
		result = append(result, node.Val)

		// Sol çocuk varsa kuyruğa ekle
		if node.Left != nil {
			queue = append(queue, node.Left)
		}
		// Sağ çocuk varsa kuyruğa ekle
		if node.Right != nil {
			queue = append(queue, node.Right)
		}
	}
	return result
}

İkili arama ağaçları (BST) için, sol alt ağaç küçük, sağ alt ağaç büyük:

3. İkili Arama (Binary Search): Belirli bir değeri ararken, onu kök ile karşılaştırırız. Değer küçükse sol alt ağaçta ararız; büyükse sağ alt ağaçta. Bu, BST'de arama için en etkili stratejidir.

// TreeNode ikili arama ağacını temsil eder
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// SearchBST BST'de ikili arama yapar
func SearchBST(root *TreeNode, target int) *TreeNode {
	if root == nil || root.Val == target {
		return root // Düğüm bulundu veya ağaç boş
	}

	if target < root.Val {
		// Sol alt ağaçta arama
		return SearchBST(root.Left, target)
	}
	// Sağ alt ağaçta arama
	return SearchBST(root.Right, target)
}

Arama algoritmasının seçimi, göreve ve ağacın özelliklerine bağlıdır. DFS, derinlemesine bir dalda ilerlenmesi veya hedefe ulaşmak için yol bulunması gereken durumlar için uygundur. BFS, en kısa yolu bulmak veya seviyeler halinde gezinmek için uygundur. İkili arama ise sıralı yapılarda belirli bir değeri bulmak için etkilidir, örneğin BST'de.