Ағашта издөө кантип иштейт?

Дарахттагы издөө анын түзүлүшүнө жана издөө максатына жараша болот.

Негизги издөө ыкмалары:

Туура тереңдикте издөө (DFS - Depth-First Search): Бир бутакта эң тереңге чейин барып, андан кийин көршү бутакка өтөт. Стек (такыр же рекурсия аркылуу) колдонуу менен ишке ашырылат.
- Алдын ала өтүү (Pre-order): Тамырды карап чыгуу, андан кийин сол жактагы даракты, андан кийин оң жактагы даракты.
- Ички өтүү (In-order): Сол жактагы даракты, андан кийин тамырды, андан кийин оң жактагы даракты. Бул бинардык издөө дарактары үчүн колдонулат, сортталган элементдердин тизмесин алуу үчүн.
- Пост-ред (Post-order): Сол жактагы даракты, андан кийин оң жактагы даракты, андан кийин тамырды.
Кеңейтүү аркылуу издөө (BFS - Breadth-First Search): Бир деңгээлдеги бардык көршүлөрдү изилдейт, андан кийин кийинки деңгээлге өтөт. Күтүү (queue) колдонуу менен ишке ашырылат.

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), анда сол жактагы дарак кичирээк, ал эми оң жактагы дарак чоңураак:

Бинардык издөө: Конкреттүү маанини издегенде, аны тамыр менен салыштырабыз. Эгер кичирээк болсо, сол жактагы даракта издөө; эгер чоңураак болсо, оң жакта. Бул эң эффективдүү издөө стратегиясы:

// TreeNode бинардык издөө дарагынын түйүнү
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// SearchBST бинардык издөө жүргүзөт
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, конкреттүү маанини эффективдүү табуу үчүн колдонулат.