Binary Tree (Ikkilik daraxtlar) va ular yordamida masalalarni hal etish

Информация о документе

Цена	15000UZS
Размер	46.4KB
Покупки	0
Дата загрузки	09 Июнь 2025
Расширение	docx
Раздел	Курсовые работы
Предмет	Биология

Продавец

Arslonbek Sulaymanov

Дата регистрации 01 Декабрь 2024

25 Продаж

Binary Tree (Ikkilik daraxtlar) va ular yordamida masalalarni hal etish

Купить

O‘ZBEKISTON RESPUBLIKASI OLIY TA’LIM, FAN VA
INNOVATSIYALAR VAZIRLIGI
SAMARQAND DAVLAT UNIVERSITETINING
KATTAQO‘RG‘ON FILIALI ANIQ VA TABIIY FANLAR
FAKULTETI
60610200 - AXBOROT TIZIMLARI VA TEXNOLOGIYALARI
(tarmoqlar va sohalar bo‘yicha) YO‘NALISHI
RAQAMLI TEXNOLOGIYALAR VA IQTISODIYOT
KAFEDRASI
“Dasturiy injenering” fanidan
“Binary Tree (Ikkilik daraxtlar) va ular yordamida masalalarni hal
etish” mavzusidagi
KURS ISHI
Bajaruvchi: 4-bosqich AT_21_13- guruh talabasi Shukirillayeva Muhlisa
Kurs ishi rahbari: o‘qituvchi ass. Sh.Himmatov
Kurs ishi Raqamli texnologiyalar va Iqtisodiyot kafedrasida bajarildi.
Kafedra mudiri: dots. Sh. K. Daliyev
Kurs ishi kafedraning 202_-yil ______ oyida himoya qilindi va ___
foizga baholandi.
Komissiya raisi: _________________________________
A’zolari: _________________________________
_________________________________
_________________________________
KATTAQO‘RG‘ON – 2025

MUNDARIJA
Kirish.....................................................................................................
.............. 3
I.BOB Ikkilik daraxtlar (Binary Tree) tushunchasi va
turlari .................................... 5
1.1. Ikkilik daraxt (Binary Tree) tushunchasi va asosiy
elementlari ....... 5
1.2. Ikkilik daraxt
tushunchasi …………………………………………………. 7
1.3 . Ikkilik daraxtlarda ko‘rish (traversal) usullari 9
II.BOB Ikkilik daraxtlar asosida masalalarni yechish
usullari ....................... 1
1
2.1. Binary Tree yordamida qidiruv, qo‘shish va o‘chirish
operatsiyalari … …………………. 1
1
2.2. Python dasturlash tilida ikkilik daraxtni yaratish usullari .
…………………….. 1
4
2.3 Amaliy masalalarni ikkilik daraxtlar yordamida
yechish ………… ……....... 1
7
Xulosa
Foydalanilgan adabiyotlar

Kirish
Ikkilik daraxtlar (Binary Trees) ma'lumotlarni saqlash, tartiblash va
izlash uchun ishlatiladigan samarali va muhim ma'lumotlar tuzilmasidir.
Ma'lumotlar strukturalari sohasida ikkilik daraxtlar juda keng tarqalgan
bo'lib, ularning o'ziga xos xususiyatlari tufayli ko'plab muammolarni
samarali hal qilishda qo'llaniladi. Ikkilik daraxtlarning asosiy afzalligi —
ular orqali ma'lumotlarni izlash va manipulyatsiya qilish juda tez va
samarali amalga oshiriladi. Daraxtlarning ierarxik strukturasini ishlatish
orqali, ma'lumotlarga tezkor kirish va ularni oson qayta ishlash mumkin.
Bugungi kunda, kompyuter ilmlari va dasturlash tillarida turli xil
ma'lumotlar strukturalari ishlatilsa-da, ikkilik daraxtlar o'zining soddaligi
va samaradorligi bilan juda muhim o'rin tutadi. Ular nafaqat ma'lumotlar
bazalarida, balki algoritm dizayni va optimallashtirish masalalarida ham
keng qo'llaniladi. Ikkilik daraxtlar yordamida nafaqat ma'lumotlar
qidiriladi, balki ma'lumotlar o'rtasidagi munosabatlar, bog'lanishlar va
bog'lanmagan tuzilmalar ham aniqlanadi.
Ushbu kurs ishi Python dasturlash tilida ikkilik daraxtlarni yaratish,
ularni boshqarish va amaliy masalalarni hal etish bo'yicha yo'naltirilgan.
Kurs ishida ikkilik daraxtlarning tushunchasi, Python dasturlash tilida
ularni yaratish va ularni dasturlashda qanday ishlatishni o'rganamiz.
Shuningdek, ikkilik daraxtlar yordamida qidiruv, siqish, balanslash kabi
murakkab algoritmlar va masalalar qanday hal etilishi ko'rib chiqiladi.

Kurs ishining maqsadi — Ushbu kurs ishining maqsadi — ikkilik
daraxtlarning nazariy asoslarini, ularni yaratish va amaliyotda qo'llashni
o'rganishdir. Maqsad, Python dasturlash tilida ikkilik daraxtlarni yaratish
va ular yordamida turli xil masalalarni hal qilishni chuqur o'rganishdir. .
Kurs ishining obekti: ikkilik daraxtlar (Binary Trees) va ular
yordamida turli xil masalalarni hal qilishda ishlatiladigan algoritmlar va
metodlar hisoblanadi.
Kurs ishining dolzarbligi: Ikkilik daraxtlar, ma'lumotlarni saqlash
va ularga samarali kirishni ta'minlashda muhim rol o'ynaydi. Dasturlash
va algoritm dizayni sohasida ikkilik daraxtlar keng qo'llaniladigan
ma'lumotlar tuzilmasi bo'lib, ular nafaqat ma'lumotlar bazalarida, balki
murakkab algoritmlarda ham ishlatiladi. Python dasturlash tili, o'zining
soddaligi va kuchli kutubxonalari bilan ma'lumotlar tuzilmalari va
algoritmlarni o'rganishda juda qulaydir. Ushbu kurs ishida Python
yordamida ikkilik daraxtlarni yaratish va ularni boshqarish, murakkab
masalalarni hal qilish usullari o'rganiladi. Bu esa dasturchilarga nafaqat
algoritmik bilimlarni, balki Python tilida samarali kod yozish
ko'nikmalarini ham rivojlantirishga yordam beradi.
Kurs ishining predmeti: ikkilik daraxtlar (Binary Trees) va ular
yordamida turli xil ma'lumotlar strukturalari va algoritmlarini yaratish va
ishlatish jarayonlaridir.
Kurs ishing hajmi: Ushbu kurs ishi kirish, 3 ta Bob, 8 ta reja,
xulosa va foydalanilgan adabiyotlar qismidan iborat.

I. BOB Ikkilik daraxtlar (Binary Tree) tushunchasi va turlari
Binar daraxti ikkilik ifodalarni ifodalash uchun ishlatiladigan dastur tili
hisoblanadi. Binar daraxti ifodalashi mumkin bo lgan ikkita keng tarqalgan ikkilik ʻ
ifoda turi algebraik va mantiqiy ifoda turlari hisoblanadi. Binar daraxti birlik va
ikkilik operatorlarni o z ichiga olgan ifodalarni ifodalashi mumkin.
ʻ Ikkilik ifoda
daraxtining barglari operandlar, masalan, doimiylar yoki o zgaruvchilar nomlari va
ʻ
boshqa tugunlarda operatorlar mavjud. Bu alohida daraxtlar ikkilik bo ladi, chunki
ʻ
barcha operatsiyalar ikkilikdir va bu eng oddiy holat bo lsa-da, tugunlarda
ʻ
ikkitadan ortiq son bo lishi mumkin. Bundan tashqari, birlik minus operatorida
ʻ
bo lgani kabi, tugunning har biri faqat bitta songa ega bo lishi mumkin. Ifodalar
ʻ ʻ
daraxti T ni chap va o ng pastki daraxtlarni rekursiv baholash natijasida olingan
ʻ
qiymatlarga ildizdagi operatorni qo llash orqali baholash mumkin.
ʻ

O tish
ʻ
Algebraik ifoda ikkilik ifoda daraxtidan qavs ichiga olingan chap ifodani
rekursiv ishlab chiqarish, so ngra operatorni ildizga chiqarish va nihoyat,
ʻ
qavs ichiga olingan o ng ifodani rekursiv ishlab chiqarish orqali ishlab
ʻ
chiqarilishi mumkin. Ushbu umumiy strategiya (chap, tugun, o ng)
ʻ
<b>tartibli o'tish</b> sifatida tanilgan. Muqobil o tish strategiyasi chap
ʻ
pastki daraxtni, o ng pastki daraxtni va keyin operatorni rekursiv ravishda
ʻ
chop etishdir. Ushbu o tish strategiyasi odatda <b>buyruqdan keyingi
ʻ
o'tish</b> sifatida tanilgan. Uchinchi strategiya — avval operatorni chop
etish, so ngra oldindan tartibli o tkazish deb nomlanuvchi chap va o ng
ʻ ʻ ʻ
pastki daraxtni rekursiv ravishda chop etish. Ushbu uchta standartdan
birinchi o tish uch xil ifoda formatlarining ifodasidir: infiks, postfiks va
ʻ
prefiks. Infiks ifodasi tartibni kesib o tish orqali, postfiks ifodasi
ʻ

$buyruqdan keyingi o tish orqali va prefiks ifodasi oldindan tartibli o tishʻ ʻ orqali hosil bo ladi. ʻ 1.1. Ikkilik daraxt (Binary Tree) tushunchasi va asosiy elementlari izlash va tartibga solish eng muhim muammolardan biridir. Ushbu maqsadlarda turli ma'lumotlar tuzilmalari, jumladan, daraxt tuzilmalari keng qo'llaniladi. Ayniqsa, har bir tuguni eng ko'pi bilan ikkita farzandga ega bo'lgan daraxt shaklidagi ma'lumotlar tuzilmasi — ikkilik daraxt (binary tree) keng tarqalgan. Ushbu kurs ishida ikkilik daraxtlar tushunchasi, ularning asosiy turlari, vakilligi va algoritmik amallari tahlil qilinadi. Ikkilik daraxt — bu rekursiv tarzda aniqlanuvchi ma'lumotlar tuzilmasi bo'lib, har bir tugun (node) maksimal ikki farzandga: chap (left child) va o'ng (right child) bolalarga ega bo'lishi mumkin. Daraxtning yuqori darajadagi tuguni "ildiz tugun" (root node) deb nomlanadi. Tugunlar kZamonaviy axborot texnologiyalarida ma'lumotlarni samarali saqlash, eyingi elementlarni ko'rsatgan holatda daraxt rekursiv tarzda kengayadi. Ikkilik daraxtning umumiy ko'rinishi A / \ B C / \ \ D E F Ikkilik daraxtlar quyidagi asosiy elementlardan iborat: Ildiz (Root) : Daraxtning boshlang'ich tuguni Tugun (Node) : Daraxtdagi har bir element Shox (Edge) : Tugunlar orasidagi bog'lanish Barg (Leaf) : Farzandi yo'q tugun Subdaraxt : Har bir tugunning chap va o'ng farzandlari bilan hosil qilgan daraxti 2. Ikkilik daraxtlarning turlari$

To'liq ikkilik daraxt (Full Binary Tree) : Har bir tugun 0 yoki 2 ta
farzandga ega.
Tugal ikkilik daraxt (Complete Binary Tree) : Har bir daraja to'liq
to'ldirilgan va oxirgi darajadagi tugunlar chapdan o'ngga qarab
to'ldirilgan.
Ideal daraxt (Perfect Binary Tree) : Har bir daraja to'liq to'ldirilgan va
barcha barglar bir xil chuqurlikda joylashgan.
Balanslashgan daraxt (Balanced Binary Tree) : Chap va o'ng
subdaraxtlar chuqurligi farqi 1 dan oshmaydi.
Degenerativ daraxt (Degenerate Tree) : Har bir tugun faqat bitta
farzandga ega, daraxt chiziqli ko'rinishga ega bo'ladi.
Ikkilik daraxtlarning vakilligi va ko'rsatilishi
Diplom ishlar (Oefen.uz, 2024) asosida ikkilik daraxtlar kompyuter
xotirasida quyidagi usullar bilan ifodalanadi:
Ko'rsatkichlar yordamida : Har bir tugun o'zining chap va o'ng
farzandlariga ko'rsatkich saqlaydi.
Massiv yordamida : Daraxt elementlari massiv indekslari orqali
joylashtiriladi (odatda tugal daraxtlar uchun qulay).
Vakillikning har biri o'ziga xos afzallik va kamchiliklarga ega bo'lib,
ularni tanlash amaliyotga bog'liq bo'ladi.
4. Daraxt bo'ylab yurish algoritmlari (Tree traversal)
Ikkilik daraxtlarda uch asosiy yurish (traversal) usullari mavjud
(Oefen.uz, 2024):
Preorder (ILDIZ -> CHAP -> O‘NG)
Inorder (CHAP -> ILDIZ -> O‘NG)
Postorder (CHAP -> O‘NG -> ILDIZ)

$1.2. Ikkilik daraxt tushunchasi Binary Tree ierarxik data structure bo’lib har bir node maksimal ikkita bolaga ega bo’lishi mumkin. Bu bolalar odatda chap va o’ng bola deb ataladi. Binary Tree ma’lumotlarni mantiqiy tarzda tashkil etish imkonini beradi va ko’plab algorithmlar uchun muhim ahamiyat kasb etadi. Tree strukturasi rekursiv tabiatga ega bo’lib, har bir sub-tree ham o’ziga xos Binary Tree hisoblanadi. Binary Search Tree (BST) Binary Treening maxsus turi bo’lib, chap bolalar ota-onasidan kichik, o’ng bolalar esa kattaroq qiymatga ega. Bu tartib qidiruv qo’shish va o’chirish operatsiyalarini O(log n) vaqtda amalga oshirish imkonini beradi. Amalda ma’lumotlar bazalarida indekslash, fayl tizimlari va ifoda daraxtlarini yaratishda foydalaniladi. Binary Tree-ning moslashuvchanligi uni ko’plab murakkab algorithmlarda qollash imkonini berdi. Ikkilik daraxt — bu har bir tuguni eng ko‘pi bilan ikki farzand tuguniga ega bo‘lgan ma'lumotlar tuzilmasidir. Daraxtning eng yuqori qismidagi tugun ildiz (root) deb ataladi. Har bir tugun o‘z farzandlariga bog‘langan bo‘lib, ularning chap va o‘ng farzandlari mavjud bo‘lishi mumkin Asosiy elementlari: Ildiz (Root) – daraxtning boshlang‘ich tuguni; Tugun (Node) – daraxtdagi har bir element; Shox (Edge) – tugunlarni birlashtiruvchi bog‘lanishlar; Barg (Leaf) – farzand tuguni bo‘lmagan tugun; Subdaraxt (Subtree) – har bir tugun bilan boshlanadigan kichik daraxt. Ikkilik daraxtning oddiy ko‘rinishi (ildiz, tugunlar, shoxlar, barglar) A / \ B C$ $/ \ \ D E F 1.3 Daraxt bo‘ylab yurish usullari (Traversal turlari ) Ikkilik daraxtning eng yuqorisida joylashgan tugun ildiz deyiladi, farzandlari mavjud bo’lmagan tugun barg deb nomlanadi. Daraxtdagi har bir tugun quyidagilarni o‘z ichiga oladi: Ma’lumot;  Chap farzand tugun;  O‘ng farzand tugun.  Data nomli tugunning chap farzandi left va o‘ng farzandi right deb nomlangan. Har bir tugun uchun ushbu qoida amal qiladi. Ikkilik daraxt ustida quyidagi amallarni bajarish mumkin: Daraxtga yangi tugun qo‘shish; $

Daraxtning biror tugunini olib tashlash; 
Daraxt tugunlari ichidan biror tugunni qidirish;

Daraxt tugunlari ichidan biror tugunga murojaat qilish;

Daraxtning balandligini topish;

Daraxtning darajasini aniqlash;

Ikkilik daraxt strukturasi qo‘llanilishi:
Kompyuterlarda tezkor xotira ajratishni amalga oshirishda ishlatiladi;

Gcc va aocl kabi dasturlash uchun ishlab chiqilgan kompilyatorlarda

arifmetik
amallarni bajarish uchun ishlatiladi;
Ma’lumotlar segmentidan qisqa vaqt ichida biror ma’lumotni izlash

uchun
ishlatiladi(ikkilik qidiruv algoritm);
Microsoft excel va elektron jadvallar kabi dasturlarni tahrirlashda

ishlatiladi;
Ikkilik daraxti saralash algoritmlarini amalga oshirish uchun ishlatilishi

mumkin, masalan heapsort saralash algoritmida tez va samarali saralash
uchun
ishlatiladi;
Kodlash va dekodlash jarayonlarida qo‘llaniladi.

Ikkilik daraxtda o‘tish algoritmlari:
Daraxtda o‘tish algoritmlarini ikki toifaga bo‘lish mumkin:
Chuqurlik bo‘yicha qidiruv(DFS) algoritmlari;

Kenglik bo‘yicha qidiruv(BFS) algoritmlari

1.3 . Ikkilik daraxtlarda ko‘rish (traversal) usullari

D araxtlarda, ma’lumotlarni o‘qish, qidirish yoki ularni tahlil qilish jarayonlarida ko‘rish (traversal)
usullari muhim o‘rin egallaydi. Traversal — daraxt tugunlarini belgilangan tartibda bosib o‘tish
algoritmlaridir. Ikkilik daraxtlarda uch asosiy traversal usuli mavjud: in-order , pre-order va post-
order . Bundan tashqari, level-order (kenglik bo‘yicha ko‘rish) usuli ham qo‘llaniladi.
1. In-order traversal (chap-korish-o‘ng)
2. Bu usulda daraxt quyidagi tartibda ko‘riladi:
Chap ost daraxtga o‘tish
Joriy tugunni ko‘rish
O‘ng ost daraxtga o‘tish
Bu traversal turi aynan ikkilik qidiruv daraxtlarida (Binary Search Tree – BST)
ishlatilganda tugunlarning qiymatlarini o‘sish tartibida olish imkonini beradi.
def in_order(node):
if node:
in_order(node.left)
print(node.data)
in_order(node.right)
2. Pr e-or der t r aver sal (k or ish-chap-o‘ng)
Bu usulda:
Joriy tugun birinchi ko‘riladi
Chap ost daraxtga o‘tiladi
O‘ng ost daraxtga o‘tiladi
Bu traversal usuli rekursiv algoritmlarni test qilish , daraxtni nusxalash va uni
seriyalash (serialization) uchun foydali.
def pre_order(node):
if node:

print(node.data)
pre_order(node.left)
pre_order(node.right)
3. Post -or der t raver sal ( chap-o‘ng-k or ish)
Bu yondashuvda:
Chap ost daraxtga o‘tiladi
O‘ng ost daraxtga o‘tiladi
So‘ng joriy tugun ko‘riladi
Bu traversal odatda xotirani bo‘shatish (memory cleanup), yig‘ish (deletion) yoki
hisoblash daraxtlari (expression tree) da amal bajarish tartibini aniqlashda
qo‘llaniladi.
def post_order(node):
if node:
post_order(node.left)
post_order(node.right)
print(node.data)
4. Level-or der t r aver sal (k englik bo‘yicha)
Bu traversal daraxt tugunlarini sathma-sath ko‘rishga asoslanadi va navbat (queue)
ma’lumotlar tuzilmasidan foydalanadi.
Bu usul foydalanuvchi interfeyslarida daraxtlarni grafik ko‘rinishda chiqarish, qisqa
yo‘l topish (shortest path) yoki izohli algoritmlarda ishlatiladi.
from collections import deque
def level_order(root):
if not root:
return

queue = deque([root])
while queue:
node = queue.popleft()
print(node.data)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
5. Dar ax tni gr afi k ko‘r inishda tasvir lash
Daraxt strukturasini vizual shaklda ko‘rsatish ularni tahlil qilish, o‘rganish va
interfeyslar yaratishda qulaylik yaratadi.

Купить

Информация о документе

Продавец

Binary Tree (Ikkilik daraxtlar) va ular yordamida masalalarni hal etish

Похожие документы