25 / 69

Perfect Binary Tree

Mukammal ikkilik daraxt

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

Perfect Binary Tree

Mukammal ikkilik daraxt (Perfect Binary Tree)

Mukammal ikkilik daraxtda barcha ichki tugunlarning darajasi (degree) 2 ga teng bo'ladi.

Rekursiv ravishda mukammal ikkilik daraxt quyidagicha ta'riflanadi:

  • Agar bitta tugun hech qanday bolaga ega bo'lmasa, u balandligi h = 0 bo'lgan mukammal ikkilik daraxtdir.
  • Agar tugun h > 0 balandlikka ega bo'lsa, uning har ikkala quyi daraxti ham h - 1 balandlikdagi mukammal ikkilik daraxt bo'lsa va o'zaro tutashmasa (alohida bo'lsa), u holda butun daraxt mukammal ikkilik daraxt hisoblanadi.

Perfect Binary Tree (Recursive Representation)

Mukammal ikkilik daraxtning rekursiv ifodalanishi

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

Quyidagi dastur berilgan ikkilik daraxtning mukammal ikkilik daraxt ekanligini chuqurlik va qavatlarni solishtirish orqali tekshiradi.

// Go tilida daraxtning mukammal ikkilik daraxt (Perfect Binary Tree) ekanligini tekshirish
package main

import "fmt"

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

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

// Daraxt chuqurligini hisoblash
func calculateDepth(node *Node) int {
	if node == nil {
		return 0
	}
	leftDepth := calculateDepth(node.left)
	rightDepth := calculateDepth(node.right)
	if leftDepth > rightDepth {
		return leftDepth + 1
	}
	return rightDepth + 1
}

// Mukammal ikkilik daraxt ekanligini tekshirish
func isPerfect(root *Node, d int, level int) bool {
	// Bo'sh daraxt holati
	if root == nil {
		return true
	}

	// Barg tugun holati
	if root.left == nil && root.right == nil {
		return d == level+1
	}

	// Agar faqat bitta bolasi bo'lsa
	if root.left == nil || root.right == nil {
		return false
	}

	return isPerfect(root.left, d, level+1) && isPerfect(root.right, d, level+1)
}

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)
	root.right.right = newNode(7)

	d := calculateDepth(root)
	if isPerfect(root, d, 0) {
		fmt.Println("Daraxt mukammal ikkilik daraxt (perfect binary tree)")
	} else {
		fmt.Println("Daraxt mukammal ikkilik daraxt EMAS (not a perfect binary tree)")
	}
}