O’zbekiston Respublikasi Oliy va O’rta maxsus ta’lim vazirligi Muhammad Al-Xorazmiy nomidagi Toshkent Axborot Texnologiyalari Universititeti Farg’ona filliali
Download 391.18 Kb. Pdf ko'rish
|
Rasuljonov Musobek
- Bu sahifa navigatsiya:
- 15-MA’RUZA: DARAXTSIMON MA’LUMOTLAR TUZILMALARI.
- Kalit so’zlari
|
O’zbekiston Respublikasi Oliy va O’rta maxsus ta’lim vazirligi Muhammad Al-Xorazmiy nomidagi Toshkent Axborot Texnologiyalari Universititeti Farg’ona filliali Kompyuter injiniring fakulteti 616-21 guruh talabasi Rasuljonov Musobekning “Ma’lumotlar tuzilmasi va algoritmlar” fanidan “ DARAXTSIMON MA’LUMOTLAR TUZILMALARI ” mavzusida tayyorlagan MUSTAQIL ISHI Farg’ona-2022 15-MA’RUZA: DARAXTSIMON MA’LUMOTLAR TUZILMALARI. Reja: 1. Asosiy tushunchalar. 2. Daraxtning rekursiv aniqlanishi. 3. Ikkilik daraxt va ular ustida bajariladigan amallar. 4. Daraxtni aylanib o’tish (daraxt elementlarini o’qish). 5. Daraxt yordamida qidiruv. 6. Arifmetik ifodalarni daraxt yordamida yoyish. Kalit so’zlari: daraxt, ildiz, tugun, ajdod tugun, avlod tugun, ota tugun, o’g’il tugun, daraxt bosqichi, daraxt shoxlanish darjasi, qism daraxt, barg (terminal), daraxt balandligi, ikkilik (binary) daraxt, daraxtda o’tishlar. 1. Asosiy tushunchalar Daraxt — bu tugunlar (cho’qqilar) va ularni birlashtiruvchi yo’naltirilgan yoy (shox)lar majmuasi bo’lib, har bir tugunga (ildizdan tashqari) bitta shox (kirish yoyi) yo’naltirilgan bo’ladi. Ildiz — bu daraxtning boshlang’ich tuguni bo’lib, unga kirish yoy (shox)lar mavjud emas. Daraxt tuzilmasiga misol sifatida biror bir shaxsning oila shajarasini olish mumkin. Bunda daraxt ildiziga ushbu shaxs joylashtirilsa, uning farzandlari uning davomchisi (avlodi) sifatida keyingi tugunlarga joylashadi. Masalan, buyuk sarkarda, davlat arbobi Amir Temur shajarasini olish mumkin. Quyidagi rasmda bir nechta daraxt tuzilmasiga misollar keltirilgan: 1-rasm. Daraxt tuzilmalariga misollar Daraxt tuzilmalarida quyidagi asosiy tushunchalarni kiritish mumkin: ildiz, avlod, ajdod, ota, o’g’il, barg (terminal), ichki (oraliq) tugun, bochqich, balandlik, daraja. Ajdod – bu daraxt tuguni bo’lib, undan biror x tugunga shox chiqariladi, ya’ni x tugundan yuqorida turuvchi tugunlar “ajdod” tugunlar hisoblanadi. Masalan, 1 a)- rasmdagi 1 tuguni 2,3,4, 5,6, 7,8 tugunlari uchun ajdod tugun hisoblanadi. Avlod – bu daraxtning tuguni bo’lib, unga biror “ajdod” tugundan shox yo’naltirilgan, ya’ni daraxtning biror x tugunining davomchilari – quyida turuvchi tugunlari avlod tugunlar hisoblanadi. Masalan, 5 va 6 tugunlari 2 va 1 tugunlari uchun avlod deyiladi. Ota – o’zidan keyingi x tugunga bevosita shox (yoy) bilan bog’langan tugun. Masalan, 1a)-rasmdagi 1 tuguni 2,3,4 lar uchun ota, 2 tuguni 5 va 6 uchun ota tugun. O’g’il – o’zidan oldingi x tugunga bevosita bog’langan tugun. Masalan, rasmdagi 8 tuguni 6 tugun uchun o’g’il, 6 tuguni 2 uchun o’g’il tugun deyiladi. Bosqich – ildizdan x tugungacha bo’lgan masofa (yo’l). Ildiz 0-bosqichda joylashgan deb qaraladi. Masalan, 1a)-rasmdagi 8 tuguni 3 bosqichda joylashgan ungacha 3 ta yoy mavjud, ya’ni 1 dan 2 ga, 2 dan 6 ga, 6 dan 8 ga. Daraja – daraxt tugunlaridan chiquvchi shox (yoy)larning maksimal soni. Masalan, 1a)-rasmdagi daraxt tugunlaridan chiquvchi shoxlarning maksimal soni 3 ga teng, shuning uchun bu daraxt 3 – darjali daraxt deyiladi. 1b)-rasmdagi daraxtda maksimal chiqish darajasi 2 ga teng, bu daraxt ikkinchi darajali daraxt deb ataladi. Barg (terminal) – daraxtning eng oxirgi tuguni, ya’ni bu tugunning avlodlari mavjud emas. Masalan, 1a)-rasmda 3, 5, 7, 8 tugunlari barg yoki terminal deyiladi. 1b)-rasmda esa, 2, 4, 6, 7 tugunlar barg. Download 391.18 Kb. Do'stlaringiz bilan baham: 
|