24 / 69

Full Binary Tree

To'liq ikkilik daraxt

To'liq ikkilik daraxt (Full Binary Tree) — har bir ota tugun yoki ichki tugun yo 0 ta, yo roppa-rosa 2 ta bola tugunga ega bo'ladigan ikkilik daraxtning maxsus turidir. Boshqacha aytganda, bunday daraxtda faqat bitta bolaga ega bo'lgan tugun bo'lishi mumkin emas.

U adabiyotlarda shuningdek proper binary tree deb ham yuritiladi.

Full binary tree

To'liq ikkilik daraxt (Full Binary Tree)

To'liq ikkilik daraxt teoremalari

Belgilashlar kiritamiz:

  • i — ichki tugunlar soni (number of internal nodes)
  • n — umumiy tugunlar soni (total number of nodes)
  • l — barg tugunlar soni (number of leaves)
  • λ — darajalar / qavatlar soni (number of levels)

Ushbu parametrlar o'rtasida quyidagi qonuniyatlar mavjud:

  • Barg tugunlar soni ichki tugunlar sonidan bittaga ko'p: l = i + 1
  • Jami tugunlar soni: n = 2i + 1
  • Ichki tugunlar soni jami tugunlar orqali: i = (n - 1) / 2
  • Barg tugunlar soni jami tugunlar orqali: l = (n + 1) / 2
  • Jami tugunlar soni barg tugunlar orqali: n = 2l - 1
  • Ichki tugunlar soni barg tugunlar orqali: i = l - 1
  • Barg tugunlar soni ko'pi bilan: 2^(λ - 1) ga teng bo'lishi mumkin.

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

Quyidagi dastur berilgan ikkilik daraxtning to'liq ikkilik daraxt ekanligini rekursiv ravishda tekshiradi.

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

import "fmt"

type Node struct {
	item       int
	leftChild  *Node
	rightChild *Node
}

func newNode(item int) *Node {
	return &Node{
		item:       item,
		leftChild:  nil,
		rightChild: nil,
	}
}

// To'liq ikkilik daraxt ekanligini tekshirish funksiyasi
func isFullTree(root *Node) bool {
	// Daraxt bo'sh bo'lgan holat
	if root == nil {
		return true
	}

	// Agar bola tugunlari bo'lmasa (barg tugun)
	if root.leftChild == nil && root.rightChild == nil {
		return true
	}

	// Agar ikkala bola tugun ham mavjud bo'lsa
	if root.leftChild != nil && root.rightChild != nil {
		return isFullTree(root.leftChild) && isFullTree(root.rightChild)
	}

	return false
}

func main() {
	root := newNode(1)
	root.rightChild = newNode(3)
	root.leftChild = newNode(2)
	root.leftChild.leftChild = newNode(4)
	root.leftChild.rightChild = newNode(5)
	root.leftChild.rightChild.leftChild = newNode(6)
	root.leftChild.rightChild.rightChild = newNode(7)

	if isFullTree(root) {
		fmt.Println("Daraxt to'liq ikkilik daraxt (full binary tree)")
	} else {
		fmt.Println("Daraxt to'liq ikkilik daraxt EMAS (not a full binary tree)")
	}
}