Tree Traversal

Daraxtni aylanib chiqish (traversing a tree) — daraxtdagi har bir tugunga birma-bir tashrif buyurish demakdir. Masalan, siz daraxtdagi barcha tugunlarning qiymatlarini yig'indisini hisoblash yoki ularning ichidan eng kattasini topishni xohlashingiz mumkin. Bularning barchasi uchun daraxtning har bir tuguniga tashrif buyurish talab etiladi.

Massivlar, steklar, navbatlar va bog'langan ro'yxatlar kabi chiziqli ma'lumot tuzilmalarida ma'lumotlarni o'qishning faqat bitta yo'li mavjud — ularni ketma-ket boshidan oxirigacha o'qish. Biroq daraxt kabi iyerarxik ma'lumotlar tuzilmasini turli xil yo'llar bilan aylanib chiqish mumkin.

Daraxtni aylanib chiqish namunasi

Yuqoridagi rasmda ko'rsatilgan daraxt elementlarini qanday tartibda o'qishimiz mumkinligini o'ylab ko'raylik:

• Tepadan boshlab, chapdan o'ngga: 1 → 12 → 5 → 6 → 9
• Pastdan boshlab, chapdan o'ngga: 5 → 6 → 12 → 9 → 1

Garchi bunday tartib sodda ko'rinsa-da, u daraxtning iyerarxik tuzilishini inobatga olmaydi, faqat tugunlarning joylashuv chuqurligiga tayanadi.

Buning o'rniga, biz daraxtning asosiy tuzilishini hisobga oluvchi maxsus usullardan foydalanamiz:

type Node struct {
    data  int
    left  *Node
    right *Node
}

Bu yerda left va right ko'rsatkichlari ko'rsatib turgan tugunlar o'z navbatida boshqa chap va o'ng bola tugunlarga ega bo'lishi mumkin. Shu sababli ularni shunchaki alohida tugun emas, balki quyi daraxtlar (subtrees) deb qarashimiz kerak.

Ushbu tuzilishga ko'ra, har qanday daraxt quyidagilarning birlashmasidan iborat:

• Ma'lumot tashuvchi bitta asosiy tugun (ildiz)
• Ikkita quyi daraxt (chap va o'ng quyi daraxtlar)

Chap va o'ng quyi daraxt tushunchasi

Bizning asosiy maqsadimiz — har bir tugunga tashrif buyurish. Demak, biz chap quyi daraxtdagi barcha tugunlarga, ildiz tugunga va o'ng quyi daraxtdagi barcha tugunlarga tashrif buyurishimiz kerak.

Ushbu amallarni qaysi ketma-ketlikda bajarishimizga qarab, aylanib chiqishning 3 ta asosiy turi mavjud:

1. Inorder traversal

1. Avval chap quyi daraxtdagi barcha tugunlarga tashrif buyuring
2. So'ngra ildiz tugunga tashrif buyuring
3. Keyin o'ng quyi daraxtdagi barcha tugunlarga tashrif buyuring

inorder(root.left)
display(root.data)
inorder(root.right)

2. Preorder traversal

1. Ildiz tugunga tashrif buyuring
2. Chap quyi daraxtdagi barcha tugunlarga tashrif buyuring
3. O'ng quyi daraxtdagi barcha tugunlarga tashrif buyuring

display(root.data)
preorder(root.left)
preorder(root.right)

3. Postorder traversal

1. Chap quyi daraxtdagi barcha tugunlarga tashrif buyuring
2. O'ng quyi daraxtdagi barcha tugunlarga tashrif buyuring
3. Oxirida ildiz tugunga tashrif buyuring

postorder(root.left)
postorder(root.right)
display(root.data)

Inorder traversal jarayonini tasavvur qilish

Inorder tartibida aylanib chiqishni bosqichma-bosqich ko'rib chiqamiz. Biz ishni ildiz tugundan boshlaymiz:

Chap va o'ng quyi daraxt hamda ildiz

Biz avval chap quyi daraxtni aylanib chiqamiz. Shuningdek, ildiz tuguniga va o'ng quyi daraxtga keyinroq tashrif buyurishimiz kerakligini eslab qolishimiz zarur. Bularni eslab qolish uchun ularni stekka joylaymiz:

Stek yordamida eslab qolish

Endi biz stekning eng yuqori (TOP) qismidagi quyi daraxtga o'tamiz. Yana inorder qoidasiga amal qilamiz: Chap quyi daraxt → Ildiz → O'ng quyi daraxt

Chap quyi daraxtni aylanib chiqqach, stek quyidagi ko'rinishga keladi:

Chap quyi daraxt aylanib chiqilgandan keyingi stek holati

"5" tuguni hech qanday quyi daraxtga ega bo'lmagani sababli uni to'g'ridan-to'g'ri chop etamiz. Shundan so'ng uning ota tuguni "12" ni, keyin esa "6" ni chiqaramiz.

Ildizning chap quyi daraxti to'liq aylanib chiqilgach, stekdan asosiy ildiz "1" olinadi va chop etiladi, nihoyat o'ng quyi daraxt "9" aylanib chiqiladi.

Barcha elementlarni aylanib chiqqach, Inorder tartibi quyidagicha bo'ladi: 5 → 12 → 6 → 1 → 9

Biz ushbu stekni qo'lda yaratishimiz shart emas, chunki dasturdagi rekursiya ushbu tartibni biz uchun xotirada (chaqiruvlar stekida) avtomatik saqlab beradi.

Dasturiy namunalar: Go, Python, Java, C va C++

// Go tilida Tree traversal (Inorder, Preorder, Postorder)
package main

import "fmt"

type Node struct {
	val   int
	left  *Node
	right *Node
}

func newNode(item int) *Node {
	return &Node{val: item}
}

// Inorder traversal (Chap -> Ildiz -> O'ng)
func inorder(root *Node) {
	if root != nil {
		// Chap quyi daraxtni aylanib chiqish
		inorder(root.left)
		// Ildizni chiqarish
		fmt.Printf("%d->", root.val)
		// O'ng quyi daraxtni aylanib chiqish
		inorder(root.right)
	}
}

// Preorder traversal (Ildiz -> Chap -> O'ng)
func preorder(root *Node) {
	if root != nil {
		// Ildizni chiqarish
		fmt.Printf("%d->", root.val)
		// Chap quyi daraxtni aylanib chiqish
		preorder(root.left)
		// O'ng quyi daraxtni aylanib chiqish
		preorder(root.right)
	}
}

// Postorder traversal (Chap -> O'ng -> Ildiz)
func postorder(root *Node) {
	if root != nil {
		// Chap quyi daraxtni aylanib chiqish
		postorder(root.left)
		// O'ng quyi daraxtni aylanib chiqish
		postorder(root.right)
		// Ildizni chiqarish
		fmt.Printf("%d->", root.val)
	}
}

func main() {
	root := newNode(1)
	root.left = newNode(2)
	root.right = newNode(3)
	root.left.left = newNode(4)
	root.left.right = newNode(5)

	fmt.Println("Inorder traversal:")
	inorder(root)

	fmt.Println("\n\nPreorder traversal:")
	preorder(root)

	fmt.Println("\n\nPostorder traversal:")
	postorder(root)
	fmt.Println()
}