Binary Tree

Ikkilik daraxt (Binary Tree) — har bir ota tugun ko'pi bilan ikkita bolaga ega bo'la oladigan daraxt ma'lumotlar tuzilmasidir. Ikkilik daraxtdagi har bir tugun odatda uchta elementdan iborat bo'ladi:

• ma'lumot elementi (data item)
• chap bolaning xotiradagi manzili (address of left child)
• o'ng bolaning xotiradagi manzili (address of right child)

Ikkilik daraxt (Binary Tree)

Ikkilik daraxt turlari

1. To'liq ikkilik daraxt

Full Binary Tree — har bir ota tugun (yoki ichki tugun) yo 0 ta, yo roppa-rosa 2 ta bolaga ega bo'ladigan maxsus ikkilik daraxt turidir.

To'liq ikkilik daraxt (Full Binary Tree)

Batafsil ma'lumot uchun Full Binary Tree darsini ko'ring.

2. Mukammal ikkilik daraxt

Perfect Binary Tree — har bir ichki tugun roppa-rosa 2 ta bola tugunga ega bo'lgan va barcha barg tugunlar bir xil chuqurlikda (darajada) joylashgan ikkilik daraxt turidir.

Mukammal ikkilik daraxt (Perfect Binary Tree)

Batafsil ma'lumot uchun Perfect Binary Tree darsini ko'ring.

3. To'ldirilgan ikkilik daraxt

Complete Binary Tree xuddi to'liq ikkilik daraxtga o'xshaydi, lekin ikkita asosiy farqqa ega:

• Har bir qavat (daraja) to'liq to'ldirilgan bo'lishi shart (eng oxirgi qavat bundan mustasno bo'lishi mumkin).
• Barcha barg elementlar chap tomonga qarab zich joylashishi shart.
• Oxirgi barg elementning o'ng qo'shnisi (sherigi) bo'lmasligi mumkin, ya'ni to'ldirilgan ikkilik daraxt mukammal bo'lishi shart emas.

To'ldirilgan ikkilik daraxt (Complete Binary Tree)

Batafsil ma'lumot uchun Complete Binary Tree darsini ko'ring.

4. Degenerat yoki patologik daraxt

Degenerate Tree — har bir ota tugun faqat bitta bolaga (yo faqat chapga, yo faqat o'ngga) ega bo'lgan daraxtdir. Bu kabi daraxt o'zining xossalari jihatidan bog'langan ro'yxatga (linked list) aylanib qoladi.

Degenerat ikkilik daraxt (Degenerate Binary Tree)

5. Bir tomonga og'gan ikkilik daraxt

Skewed Binary Tree — patologik/degenerat daraxtning bir ko'rinishi bo'lib, unda daraxt butunlay faqat chap tugunlar (left-skewed) yoki butunlay faqat o'ng tugunlar (right-skewed) tomonidan egallangan bo'ladi.

Bir tomonga og'gan ikkilik daraxt (Skewed Binary Tree)

6. Balanslangan ikkilik daraxt

Balanced Binary Tree — har bir tugun uchun uning chap va o'ng quyi daraxtlari balandliklari o'rtasidagi farq 0 yoki 1 dan oshmaydigan ikkilik daraxt turidir.

Balanslangan ikkilik daraxt (Balanced Binary Tree)

Batafsil ma'lumot uchun Balanced Binary Tree darsini ko'ring.

Ikkilik daraxtning dasturiy ifodalanishi

Ikkilik daraxtning har bir tuguni ma'lumot qismi va boshqa ikkita tugunga havolani (ko'rsatkichni) o'z ichiga olgan struktura orqali ifodalanadi:

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

Ikkilik daraxt tugunining xotirada ifodalanishi

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

// Go tilida Ikkilik daraxt (Binary Tree) va uni aylanib chiqish
package main

import "fmt"

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

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

// Preorder aylanib chiqish (Ildiz -> Chap -> O'ng)
func (n *Node) traversePreOrder() {
	if n == nil {
		return
	}
	fmt.Printf("%d ", n.val)
	if n.left != nil {
		n.left.traversePreOrder()
	}
	if n.right != nil {
		n.right.traversePreOrder()
	}
}

// Inorder aylanib chiqish (Chap -> Ildiz -> O'ng)
func (n *Node) traverseInOrder() {
	if n == nil {
		return
	}
	if n.left != nil {
		n.left.traverseInOrder()
	}
	fmt.Printf("%d ", n.val)
	if n.right != nil {
		n.right.traverseInOrder()
	}
}

// Postorder aylanib chiqish (Chap -> O'ng -> Ildiz)
func (n *Node) traversePostOrder() {
	if n == nil {
		return
	}
	if n.left != nil {
		n.left.traversePostOrder()
	}
	if n.right != nil {
		n.right.traversePostOrder()
	}
	fmt.Printf("%d ", n.val)
}

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

	fmt.Print("Pre order Traversal: ")
	root.traversePreOrder()

	fmt.Print("\nIn order Traversal: ")
	root.traverseInOrder()

	fmt.Print("\nPost order Traversal: ")
	root.traversePostOrder()
	fmt.Println()
}