Чӣ гуна ҷустуҷӯ дар дарахт кор мекунад?

Ҷустуҷӯ дар дарахт вобаста ба сохтор ва ҳадафи ҷустуҷӯ мебошад.

Роҳҳои асосии ҷустуҷӯ:

Ҷустуҷӯи дарозо (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 иҷро мекунад гузариши дарунӣ
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.