Complete Binary Tree

To'ldirilgan ikkilik daraxt (Complete Binary Tree) — barcha qavatlari to'liq to'ldirilgan (oxirgi qavat bundan mustasno bo'lishi mumkin) va oxirgi qavatdagi barcha barg tugunlari chap tomondan o'ngga qarab zich joylashgan ikkilik daraxtdir.

To'ldirilgan ikkilik daraxt xuddi to'liq ikkilik daraxtga (Full Binary Tree) o'xshaydi, lekin ikkita asosiy farqqa ega:

• Barcha barg elementlari chap tomonga qarab zich joylashishi shart.
• Oxirgi barg elementning o'ng qo'shnisi (sherigi) bo'lmasligi mumkin, ya'ni to'ldirilgan ikkilik daraxt to'liq (full) bo'lishi shart emas.

To'ldirilgan ikkilik daraxt (Complete Binary Tree)

Full Binary Tree va Complete Binary Tree taqqoslash

Quyidagi rasmlarda qaysi daraxt to'liq (Full) va qaysi biri to'ldirilgan (Complete) ekanligi ko'rsatilgan:

Full va Complete ikkilik daraxtlar taqqoslanishi (1)

Full va Complete ikkilik daraxtlar taqqoslanishi (2)

Full va Complete ikkilik daraxtlar taqqoslanishi (3)

Full va Complete ikkilik daraxtlar taqqoslanishi (4)

To'ldirilgan ikkilik daraxt qanday quriladi?

1. Ro'yxatning birinchi elementini ildiz tugun sifatida tanlang (1-qavatdagi elementlar soni: 1):

Birinchi elementni ildiz sifatida tanlash

2. Ikkinchi elementni ildiz tugunning chap bolasi, uchinchi elementni esa o'ng bolasi qilib joylashtiring:

12 ni chap bola va 9 ni o'ng bola qilib joylashtirish

3. Keyingi ikkita elementni ikkinchi qavatdagi chap tugunning bolalari qilib qo'ying. Yana keyingi ikkita elementni ikkinchi qavatdagi o'ng tugunning bolalari qilib qo'ying:

5 ni chap bola va 6 ni o'ng bola qilib joylashtirish

4. Oxirgi elementga yetgunga qadar shu tartibda davom eting.

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

Quyidagi dastur massiv indekslari mantiqiga asoslanib, berilgan ikkilik daraxtning to'ldirilgan ikkilik daraxt ekanligini tekshiradi.

// Go tilida daraxtning to'ldirilgan ikkilik daraxt (Complete Binary Tree) ekanligini tekshirish
package main

import "fmt"

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

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

// Daraxtdagi umumiy tugunlar sonini hisoblash
func countNodes(root *Node) int {
	if root == nil {
		return 0
	}
	return 1 + countNodes(root.left) + countNodes(root.right)
}

// To'ldirilgan ikkilik daraxt ekanligini tekshirish
func isComplete(root *Node, index int, numberNodes int) bool {
	// Bo'sh daraxt holati
	if root == nil {
		return true
	}

	// Agar indeks tugunlar umumiy sonidan katta yoki teng bo'lsa, daraxt to'ldirilgan emas
	if index >= numberNodes {
		return false
	}

	return isComplete(root.left, 2*index+1, numberNodes) &&
		isComplete(root.right, 2*index+2, numberNodes)
}

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

	nodeCount := countNodes(root)
	index := 0

	if isComplete(root, index, nodeCount) {
		fmt.Println("Daraxt to'ldirilgan ikkilik daraxt (complete binary tree)")
	} else {
		fmt.Println("Daraxt to'ldirilgan ikkilik daraxt EMAS (not a complete binary tree)")
	}
}