• Всего документов: 5844
  • Число пользователей: 15251

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

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

Продавец

Arslonbek Sulaymanov

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

26 Продаж

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

/ \ \ 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;  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. 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 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 ʻ 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. 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 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 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: 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 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 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 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.
Купить