logo
  1. Bosh sahifa
  2. Diplom ishlar
  3. Umumiy
  4. Daraxtlar. Ikki tomonlama daraxtlar. Ikkilik daraxtlar vakili. Pryufer kodi

Daraxtlar. Ikki tomonlama daraxtlar. Ikkilik daraxtlar vakili. Pryufer kodi

Yuklangan vaqt:

12.08.2023

Ko'chirishlar soni:

0

Hajmi:

651.0068359375 KB
Ko'chirib olish
Mavzu: Daraxtlar. Ikki tomonlama daraxtlar. Ikkilik daraxtlar vakili. Pryufer kodi. Reja: Kirish Asosiy qism. 1.Daraxtlar haqida umumiy tushuncha. 2.Ikkilik daraxtlarning vakili. 3. Pryufer kodi. Xulosa Foydalanilgan adabiyotlar. Kirish Bizga dasturlash hayotimizda muhim ro l o ynaydi. Bunda bizga algoritmlash faniʻ ʻ yordam beradi. Algoritmlash fanining bir bo limi bu daraxtlar va graflar ʻ nazariyasi.Daraxt - bu bog langan asiklik graf, ya’ni sikllar yo q va uchlar juftligi ʻ ʻ orasida bitta yo l bor (29-rasm). Kirishning nol darajasiga ega bo lgan uch ʻ ʻ daraxtning ildizi, chiqish nol darajaga ega tugunlar esa barglar deb nomlanadi. Graflar nazariyasi haqida umumiy ma’lumotlar. 1736 yilda L. Eyler tomonidan o‘sha davrda qiziqarli amaliy masalalardan biri hisoblangan Kyonigsberg ko‘priklari haqidagi masalaning qo‘yilishi va yechilishi graflar nazariyasining paydo bo‘lishiga asos bo‘ldi. Kyonigsberg shahridagi Pregel daryosi ustida qurilgan yettita ko‘priklar joylashuvi 1- shakldagi qadimiy xaritada tasvirlangan va qurilishi tartibida 1, 2, 3, 4, 5, 6 va 7 raqamlar bilan belgilangan. Pregel daryosi Kyonigsberg shahrini o‘sha davrda to‘rtta , , va qismlarga bo‘lgan. Shaharning ixtiyoriy qismida joylashgan uydan chiqib yettita ko‘priklardan faqat bir martadan o‘tib, yana o‘sha uyga qaytib kelish mumkinmi? Kyonigsberg ko‘priklari haqidagi bu masalani hal qilish jarayonida graflarda maxsus marshrut (hozirgi vaqtda graflar nazariyasida bu marshrut Eyler sikli nomi bilan yuritiladi, mavjudligi shartlari ham topildi. Bu natijalar e’lon qilingan tarixiy ilmiy ishning birinchi sahifasi 2- shaklda keltirilgan. L. Eylerning bu maqolasi yuz yildan ko‘p vaqt mobaynida graflar nazariyasi bo‘yicha yagona ilmiy ish bo‘lib keldi. XIX asrning o‘rtalarida graflar nazariyasi bilan bog‘liq tadqiqotlar G. Kirxgof va A. Keli ishlarida paydo bo‘ldi. “Graf” iborasi D. Kyonig tomonidan 1936 yilda graflar nazariyasiga bag‘ishlangan dastlabki darslikda uchraydi. Graflar nazariyasi bo‘yicha tadqiqotlar natijalari inson faoliyatining turli sohalarida qo‘llaniladi. Ulardan ba’zilari quyidagilardir: boshqotirmalarni hal qilish; qiziqarli o‘yinlar; yo‘llar, elektr zanjirlari, integral sxemalari va boshqarish sistemalarini loyihalashtirish; avtomatlar, blok-sxemalar va komp’yuter uchun programmalarni tadqiq qilish va hokazo. Kurs ishining maqsadi. Algoritmlash fanini talabalarga o qitish va uniʻ rivojlantirish. Kurs ishining vazifasi. Agoritmlash fanini o tgan choraklarga qaraganda ʻ rivojlantirish va uni namoyish etish. Kirs ishining tarkibi. Mazkur ish "Kirish" Asosiy qism, "Xulosa", hamda foydalanilgan adabiyotlardan tashkil topgan. Asosiy qism 1.Mavzu:Daraxtlar haqida umumiy tushuncha Daraxt - bu bog langan asiklik graf, ya’ni sikllar yo q va uchlar juftligi orasida ʻ ʻ bitta yo l bor Kirishning nol darajasiga ega bo lgan uch daraxtning ildizi, chiqish ʻ ʻ nol darajaga ega tugunlar esa barglar deb nomlanadi. Ulanish har qanday uchlar juftligi o rtasida marshrut mavjudligini anglatadi, aylanuvchanlik sikllar yo qligini ʻ ʻ anglatadi. Demak, xususan, shundan kelib chiqadiki, daraxtdagi qirralarning soni uchlar sonidan bitta kamroq va har qanday uchlar juftlari orasida bitta va faqat bitta yo l bor. ʻ O rmon – juda ko p daraxtlardir. ʻ ʻ Yo naltirilgan (oriyentirlangan) daraxt - bu faqat bitta vertikal kirish nol darajasigaʻ ega bo lgan (boshqa yoylar unga olib kelmaydigan), boshqa uchlarning kirish ʻ darajasi 1 bo lgan siklik orgraf (sikllarni o z ichiga olmaydigan yo naltirilgan ʻ ʻ ʻ graf). Yo naltirilgan daraxt ʻ Daraxtning asosiy tushunchalari Ildiz tuguni - daraxtning eng yuqori tuguni (18-rasmdagi 8-tugun ). Ildiz – ixtiyoriy tanlab olingan uchlardan biri. Barg yoki terminal tuguni – avlodi mavjud bo lmagan tugun (18-rasmdagi 1, 4, 7, 13 tugunlari). ʻ Ichki tugun - bu daraxtga avlodi mavjud bo lgan har qanday tugun va shuning ʻ uchun barg tuguni emas (18-rasmda 3, 6, 10, 14). Uchning darajasi - unga tushgan qirralarning soni. Sentroid - uch, u olib tashlanganida hosil bo lgan ulanish komponentlariningʻ o lchamlari n2 dan oshmaydi (asl daraxtning yarmi kattaligi) ʻ Tugun. Tugun - bu ba’zi bir qat’iy tabiat obyektiga mos keladigan ikki turdagi graf elementlaridan birining nusxasi. Tugun ma’lum bir ma’lumot strukturasining yoki daraxtning o zi qiymatini, holatini yoki ko rinishini o z ichiga olishi mumkin. ʻ ʻ ʻ Daraxtning har bir tugunida daraxt ostida joylashgan nol yoki undan ko p avlod ʻ tugunlari mavjud (odatda, daraxtlar haqiqiy daraxtlar singari yuqoriga emas, pastga qarab "o sadi"). Avlodga ega bo lgan tugun o z avlodiga nisbatan ajdod tugun deb ʻ ʻ ʻ nomlanadi (oldingi tugun yoki kattaroq tugun). Har bir tugunning ko pi bilan bitta ʻ ajdodi bor. Tugunning balandligi - bu tugundan eng pastki tugunga (chekka tugunga) barg deb ataladigan pastga tushadigan yo lning maksimal uzunligi. Ildiz tugunining ʻ balandligi butun daraxtning balandligiga teng. Ildiz tugunlari. Ajdodlari bo lmagan ʻ tugun (eng yuqorisi) ildiz tuguni deb ataladi. Bu daraxtdagi ko plab amallar ʻ boshlanadigan tugun (garchi ba’zi algoritmlar "barglar" dan boshlanib, ular ildizga yetguncha davom etadi). Boshqa barcha tugunlarga ildiz tugunidan qirralar (yoki bog lanishlar) bo ylab harakatlanish orqali erishish mumkin (rasmiy ta’rifga ko ra, ʻ ʻ ʻ har bir bunday yo l noyob bo lishi kerak). Diagrammalarda u odatda eng yuqori ʻ ʻ qismida tasvirlangan. Ba’zi daraxtlarda, masalan, uyumlarda, ildiz tuguni maxsus xususiyatlarga ega. Daraxtdagi har bir tugunni shu tugundan "o sayotgan" kichik ʻ daraxtning ildiz tuguni deb hisoblash mumkin. Daraxt osti - bu alohida daraxt sifatida namoyish etilishi mumkin bo lgan daraxtga o xshash ma’lumotlar ʻ ʻ strukturasining bir qismidir. T daraxtining har qanday tuguni va uning barcha nasl tugunlari bilan birga T daraxtining pastki daraxti hisoblanadi. Daraxt osti har qanday tuguni uchun, yo ushbu kichik daraxtning ildiz tuguniga yo l bo lishi ʻ ʻ kerak, yo tugunning o zi ildiz bo lishi kerak. Ya’ni, kichik daraxt ildiz tuguniga ʻ ʻ butun daraxt bilan bog lanadi va boshqa barcha tugunlar bilan daraxt osti aloqasi ʻ tegishli daraxt osti tushunchasi orqali aniqlanadi (“to plam osti" atamasi bilan ʻ o xshashlik bo yicha). ʻ ʻ Daraxt strukturasi orasida tartiblangan daraxtlar eng keng tarqalgan. Binar (Ikkilik) qidiruv daraxti - tartiblangan daraxt turidir. Daraxtlar ustida bajariladigan umumiy amallar: 1) yangi elementni ma’lum bir joyga kiritish; 2) daraxt osti kiritish; 3) daraxt shoxini qo shish (payvandlash deb ataladi);ʻ 4) har qanday tugun uchun ildiz elementini topish; 5) ikkita uchning eng kichik umumiy ajdodini topish; 6) daraxtning barcha elementlarini sanab chiqish; 7) daraxt novdasi elementlarini sanab chiqish; 8) izomorfik daraxt osti qidirish; 9) elementni qidirish; 10) daraxt shoxini olib tashlash; 11) daraxt ostini olib tashlash; 12) elementni o chirish. ʻ Daraxtlarning qo llanish sohalari: ʻ 1) ma’lumotlar iyerarxiyasini boshqarish; 2) axborot olishni soddalashtirish 3) ma’lumotlarning saralangan ro yxatlarini boshqarish; ʻ 4) arifmetik ifodalarni tahlil qilish (inglizcha parsing), dasturni optimallashtirish; 5) turli xil vizual effektlarni olish uchun raqamli rasmlarni yaratish texnologiyasi sifatida;  6) ko p bosqichli qaror qabul qilish shakllarida (shaxmat).ʻ 2. Mavzu : Ikkilik daraxtlar vakili. Ikkilik daraxtlar. Barcha ma’lumot tugunlari ikkitadan ko’pbo’lmagan eng yaqin avlod tugunlariga ega bo’lgan daraxtlarbinar binar daraxtlar deb ataladi.Ikkilik daraxt - bu har bir tugunda ko pi bilan ikkita avlod (bola) bo lgan ma’lumotlarning ʻ ʻ iyerarxik tuzilishi. Odatda, birinchisi ajdod tuguni, avlodlar esa chap va o ng ʻ merosxo rlar deb nomlanadi. ʻ Kalitlari lotin alifbosi bo lgan ikkilik qidiruv daraxti, alfavit bo yicha ʻ ʻ tartiblangan . 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. A ildiz otgan ikkilik daraxt bor ildiz tuguni va har bir tugunning ko'pi bilan ikkita bolasi bor. olib An ajdodlar jadvali mukammal chuqurlik-4 ikkilik daraxtiga xaritalar. A to'liq ikkilik daraxt (ba'zan a deb ham nomlanadi to'g'ri[15] yoki samolyot ikkilik daraxt)[16][17] har bir tugunda 0 yoki 2 boladan iborat bo'lgan daraxt. To'liq ikkilik daraxtni aniqlashning yana bir usuli bu rekursiv ta'rif. To'liq ikkilik daraxt ham:[11]. Ikkilik daraxtlarning xususiyatlari Tugunlarning soni n to'liq ikkilik daraxtda, hech bo'lmaganda n=2h+1 va ko'pi bilan {displaystyle n=2^{h+1}-1}, qayerda h bo'ladi balandlik daraxtning. Faqatgina ildiz tugunidan iborat daraxtning balandligi 0 ga teng. Barg tugunlari soni l mukammal ikkilik daraxtda, bo'ladi l=(n+1)/2 chunki bargsiz (ichki a) tugunlarning soni. Bu degani, to'liq binar daraxt bilan l barglari bor n=2l- 1 tugunlar. A muvozanatli to'liq ikkilik daraxt, A mukammal to'liq ikkilik daraxt, l=2^{h} shunday qilib n=2^(h+1)-1 Ning ikkilik daraxtidagi bo'sh havolalar soni (ya'ni tugunlarning yo'q bolalari) n tugunlari (n+1). A-dagi ichki tugunlarning soni to'liq binar daraxt n tugunlar lfloor n/2floor . Bilan har qanday bo'sh bo'lmagan ikkilik daraxt uchun n0 barg tugunlari va n2 2- darajali tugunlar, n0 = n2 + 1.[25] Muvozanatlangan binar daraxtlar Daraxtni muvozanatlash algoritmi Binar daraxt muvozanatlangan yoki AVL-muvozanatlangan bo’lishi mumkin. DaraxtAVL-muvozanatlangan (1962 yil sovet olimlariAdelson, Velsk Georgiy Maksimovich va Landis Yevgeniya Mihaylovichlar tomonidan taklif qilingan) deyiladi , agar daraxtdagi har bir tugunning chap va o’ng qismdaraxtlari balandliklari farqi 1 tadan ko’p bo’lmasa. Berilgan butun sonlar – kalitlar ketma-ketligidan binar daraxt yaratib olamiz va uni muvozanatlaymiz. Daraxtni muvozanatlashdan maqsad, bunday daraxtga yangi element kiritish va daraxtdan element izlash algoritmi samaradorligini oshirishdan iborat, ya’ni bu amallarni bajarishdagi solishtirishlar soni kamayadi. Binar daraxtni muvozanatlash algoritmi quyidagicha bo’ladi. Algoritm Binar daraxtni yaratib olamiz. Binar daraxtni chapdan o’ngga ko’rikdan o’tkazamiz va tugunlarning info maydonlaridan a[..] massiv hosil qilamiz. Tabiiyki , massiv o’sish bo’yicha tartiblangan bo’ladi. Muvozanatlangan daraxtning tugunlarini belgilash uchun massivni ko’riladigan oralig’ini belgilab olamiz, ya’ni start=0 va end=n-1. Massivning ko’rilayotgan oralig’i o’rtasida joylashgan elementni, ya’ni mid=(start+end)/2 va a[mid] ni muvozanatlangan daraxtning tuguni qilib olinadi. Agar ko’rilayotgan oraliqda bitta ham element qolmagan bo’lsa, ya’ni start>end bo’lsa, bajarilish joriy seansdan keyingisiga uzatiladi. Ko’rilayotgan tugunning chap qismdaraxtini hosil qilish uchun massivning ko’rilayotgan oralig’ining 1-yarmini olamiz, ya’ni start=0 va end=mid-1.3-5 qadamlarni takrorlaymiz. Ko’rilayotgan tugunning o’ng qismdaraxtini hosil qilish uchun massivning ko’rilayotgan oralig’ining 2-yarmini olamiz, ya’ni start=mid+1 va end=end(oldingi qadamdagi end). 3-5 qadamlarni takrorlaymiz. Binar daraxtni ko’rikdan o’tkazayotganda biz yuqorida har bir tugunni o’ngida va chapida turgan tugunlarni so’z bilan ifodaladik. Lekin bu usul bir muncha noqulay. Daraxtni vizual ko’rinishda ifodalash uni anglashning juda qulay usuli hisoblanadi. Daraxtni vizuallashtirishning grafik ko’rinishi va konsol oynasida ifodalash kabi turlari mavjud. Shundan konsol oynasida daraxtni vizuallashtirishni ko’rib chiqamiz. Bunda sonlar daraxt shaklida joylashtiriladi. Quyida bunday usulning dastur kodi keltirilgan. Datur kodi <endl;< i=""><n; i++){<="" i=""><endl;< i=""><endl;< i="">void vizual(node *tree,int l) { int i; if(tree!=NULL) { vizual(tree->right,l+1); for (i=1; i<=l; i++) cout<<" "; cout<info<<endl;< i=""> vizual(tree->left,l+1); } } Dastur natijasi. Binar daraxtni muvozana’qligini tekshirish Daraxtning balandligini aniqlashni o’rganganimizdan keyin uning muvoza- natlanganligini tekshirish mumkin. Binar daraxtning muvozanatlanganligini tekshirish uchun uning har bir tugunini har ikkala qismdaraxti balandliklarini hisoblab, farqlarini tekshirib ko’rish kerak. Agar farq 0 yoki 1 ga teng bo’lsa, bu muvozanatlangan daraxt hisoblanadi. Quyida binar daraxtni muvozanatlanganlikka tekshirishning rekursiv funksiyasini qo’llovchi dastur keltirilgan. Dastur kodi #include #include using namespace std; class node{ public: int info ; node *left; node *right; }; int k=0,Flag=1; int height (node *tree){ int h1,h2; if (tree==NULL) return (-1); else { h1 = height(tree->left); h2 = height(tree->right); if (h1>h2) return (1 + h1); else return (1 + h2); } } void vizual (node *tree,int l) { int i; if(tree!=NULL) { vizual(tree->right,l+1); for (i=1; i<=l; i++) cout<<" "; cout<info<<endl;< i=""> vizual(tree->left,l+1); } } int AVLtree (node *tree){ int t; if (tree!=NULL){ t = height (tree->left) - height (tree->right); if ((t<-1) || (t>1)) { Flag = 0; return Flag ; } AVLtree (tree->left); AVLtree (tree->right); } } int GetFlag (){return Flag;} int main () { int n,key,s; node *tree=NULL,*next=NULL; cout<<"n="; cin>>n; int arr[n]; for(int i=0; i<n; i++){<="" i=""> node *p=new node; node *last=new node; cin>>s; p->info=s; p->left=NULL; p->right=NULL; if(i==0){tree=p; next=tree; continue ; } next=tree; while(1) { last=next; if(p->infoinfo)next=next->left; else next=next->right; if(next==NULL)break; } if(p->infoinfo)last->left=p; else last->right=p;} cout<<endl;< i=""> cout<<"\nbinar daraxt:\n"; vizual(tree,0); AVLtree(tree); if(GetFlag()) cout<<"ha,muvozanatlangan daraxt"; else cout<<"yo’q, muvozanatlanmagan daraxt";cout<<endl;< i=""> getch(); } 3.Mavzu: Pryufer kodi. Pryufer kodi [1, n] kesmadagi n-2 butun sonlar ketma-ketligi yordamida n uchlari bilan belgilangan daraxtlarni birma-bir kodlash usuli. Ya’ni, Pryufer kodi - bu to liq graf va raqamlar ketma-ketligining barcha daraxtlari orasidagiʻ biyeksiyasidir. Daraxtlarni kodlashning ushbu usuli nemis matematiki Xaynts Pryufer tomonidan 1918-yilda taklif qilingan. ta uchlari bilan berilgan daraxt uchun Pryufer kodini qurish algoritmini ko rib chiqaylik. Kirishda qirralarning ʻ ro yxati berilgan. Eng kichik raqamga ega bo lgan daraxtning bargi tanlanadi, ʻ ʻ keyin u daraxtdan olib tashlanadi va bu barg bilan bog langan uchlarning soni ʻ Pryufer kodiga qo shiladi. Ushbu protsedura n − 2 marta takrorlanadi. Oxir-oqibat, ʻ daraxtda faqat 2 ta uch qoladi va algoritm shu yerda tugaydi. Qolgan ikkita uchning raqamlari kodga yozilmaydi.Shunday qilib, ma’lum bir daraxt uchun Pryufer kodi n − 2 ta raqamlar ketma-ketligi bo lib, bu yerda har bir raqam eng ʻ kichik barg bilan bog langan uchning soni - bu segmentdagi raqam [1, n ]. ʻ Pryufer kodini aniqlash. Kodni olish algoritmi quyidagicha. Daraxt tugunlari 1 dan n gacha bo lganʻ raqamlar bilan belgilangan (raqamlangan) bo lsin. Biz eng kichik sonli 1-darajali ʻ uchni topamiz va kodga unga qo shni bo lgan uchning sonini kiritamiz, shundan ʻ ʻ so ng topilgan uchni (qirrasi bilan birga) o chirib tashlaymiz. Olingan graf osti ʻ ʻ bilan biz xuddi shu amalni bajaramiz, uni faqat bitta qirra qolguncha takrorlaymiz. Kodni yaratish jarayoni 34-rasmda keltirilgan. Keyingi bosqichda o chirilgan ʻ uchning soni ramkaga kiritilgan. Berilgan grafda (34-rasm, a) birinchi darajali uchlar orasida minimal son 2-uchda joylashgan. U 1-uchga qo shni. Shuning uchun ʻ Pryufer kodining birinchi raqami 1. 2-uchni olib tashlash natijasida biz b-rasmda ko rsatilgan grafni olamiz. Ushbu grafda darajasi birga teng bo lgan uchlar ʻ ʻ orasidagi minimal son 3 ga teng, shuning uchun kodning ikkinchi raqami 4. Shaklda ko rsatilgan graflarga mos keladigan yana uchta takrorlashni bajargandan ʻ so ng, c, d, e-rasmlardagi bitta qirradan iborat daraxtni olamiz {7; 6}. Jarayon ʻ tugallandi. Qabul qilingan qadamlarning natijalari jadvalda keltirilgan. Oxirgi qatorida kerakli kod mavjud - 14166. Pryufer kodi orqali daraxtni tiklash. Pryufer kodi bilan ifodalangan daraxtlarni hosil qilish algoritmi qirralarning tegishli ro yxatini olishga imkon beradi.Antikodni Pryufer kodiga kiritilmaganʻ uchlar sonining ortib boruvchi ketma-ketligi deylik. Ko rib chiqilgan misol uchun ʻ antikod 2357 ga teng.Daraxt ketma-ket qirralarni qo shib quriladi. Keyingi ʻ qo shilgan chekka, birinchisid ʻ an boshlab, vertikal juftlik bilan hosil bo ladi, ʻ ularning raqamlari kod satrida va antikod satrida birinchi bo ladi. Shundan so ng, ʻ ʻ ishlatilgan satr elementlari chiziladi. Agar kod satridan chiqib ketgan raqam undagi qolgan elementlar qatoriga kiritilmagan bo lsa, uning tartibini buzmasdan antikod ʻ qatoriga qo shilishi kerak. Ta’riflangan harakatlar kod va antikod satrlarining ʻ "qoldiqlari" bilan ularning birinchisining barcha elementlari o chirilguncha ʻ takrorlanadi. Bunday holda, antikod chizig ida hosil qilingan ro yxatga ʻ ʻ qo shiladigan so nggi chekkani belgilaydigan ikkita element bo ladi, natijada biz ʻ ʻ ʻ Pryufer kodi bilan belgilangan daraxtga mos keladigan n - 1 qirralarning ro yxatini ʻ olamiz. Umumiy daraxtlarni ikkilik daraxtlar sifatida kodlash Umumiy buyurtma qilingan daraxtlar va ikkilik daraxtlar o'rtasida birma-bir xaritalash mavjud, ular ayniqsa foydalaniladi Lisp umumiy tartibli daraxtlarni ikkilik daraxtlar sifatida ko'rsatish. Umumiy buyurtma qilingan daraxtni ikkilik daraxtga aylantirish uchun biz faqat umumiy daraxtni chapdan o'ngga birodarlik usulida namoyish etishimiz kerak. Ushbu namoyish natijasi, agar boshqa nuqtai nazardan qaralsa, avtomatik ravishda ikkilik daraxt bo'ladi. Har bir tugun N buyurtma qilingan daraxtda tugunga to'g'ri keladi N ' ikkilik daraxtda; The chap ning farzandi N ' ning birinchi bolasiga mos keladigan tugun N, va to'g'ri ning farzandi N ' ga to'g'ri keladigan tugun N keyingi birodar ---, ya'ni ota-onasining farzandlari orasida navbatdagi tugun N. Umumiy tartib daraxtining bu ikkilik daraxt tasvirini ba'zida a deb ham atashadi chap bolada o'ng aka-uka ikkilik daraxt (shuningdek, LCRS daraxti, juft zanjirli daraxt, filial-merosxo'r zanjiri deb ham ataladi). Bu haqda o'ylashning bir usuli shundaki, har bir tugunning bolalari a bog'langan ro'yxat, ular bilan birga zanjirlangan to'g'ri maydonlari va tugun faqat ushbu ro'yxatning boshiga yoki boshiga ko'rsatgichga ega chap maydon. Masalan, chap tomondagi daraxtda A ning 6 ta farzandi bor {B, C, D, E, F, G}. Uni o'ngdagi ikkilik daraxtga aylantirish mumkin. Xulosa Bizga dasturlash hayotimizda muhin ro’l oynaydi.Kruskal algoritmida qirralarning butun birlashtirilgan ro'yxati kamaymaydigan uch darajalariga muvofiq tartiblangan. Bundan tashqari, qirralar darajalari kichikroq bo'lgan qirralardan yuqori tomonga siljiydi va keyingi uch ilgari tanlangan qirralar bilan sikl hosil qilmasa, karkasga qo'shiladi. Xususan, grafdagi minimal darajadagi qirralaridan biri har doim birinchi bo'lib tanlanadi. Tanlangan qirralarning sikl hosil qilmasligini tekshirish uchun biz grafni bir nechta bog langan komponentlarningʻ birlashishi sifatida namoyish etamiz. Eng boshida, grafning chekkalari tanlanmaganida, har bir uch alohida bog langan komponent hisoblanadi. Yangi ʻ qirralar qo'shilganda, ulanish komponentlari bitta umumiy ulanish komponenti bo'lguncha birlashadi. Barcha bog langan tarkibiy qismlarni raqamlaymiz va har ʻ bir uch uchun uning ulangan qismlarini sonini saqlaymiz, shuning uchun har bir uch uchun boshida uning bog langan komponentlari soni uchning o'zi soniga teng ʻ bo'ladi va oxirgi barcha uchlar bir-biriga bog langan komponentning bir xil ʻ raqamlariga tegishli bo'ladi. Keyingi qirrani ko'rib chiqayotganda, ushbu qirraning uchlariga to'g ri keladigan ulangan komponentlarning raqamlarini ko'rib chiqamiz. ʻ Agar bu raqamlar bir xil bo'lsa, unda qirra allaqachon bir xil bog langan ʻ komponentda joylashgan ikkita uchni birlashtiradi, shuning uchun bu qirrani qo'shish siklni tashkil qiladi. Agar qirra ikki xil bog langan komponentni, masalan, ʻ ?????? va ?????? raqamlari bilan bog lasa, u holda qirra asosiy daraxtning bir qismiga ʻ qo'shiladi va bu ikkita bog langan komponentlar birlashtiriladi. Buning uchun, ʻ masalan, ilgari ?????? komponentida bo'lgan barcha uchlar uchun komponent raqamini ?????? ga o'zgartirish kerak Foydalanilgan adabyotlar 1.Varden V., Probujdayushayasya nauka, M., 1959; 2.Istoriya matematiki (v 3 tomax), M, 1970—72; 3.Matviyevskaya G. P., Ucheniye o chisle na srednevekovom Vostoke, T., 1967; 4.Burbaki N., Ocherki po istorii matematiki, M., 1963. 5. Bruno R. Preiss. „Expression Trees“ (1998). 19-yanvar 2017-yilda asl nusxadan arxivlandi . Qaraldi: 20-dekabr 2010-yil. 6. Mark Allen Weiss, Data Structures and Algorithm Analysis in C,2nd edition , Addison Wesley publications 7. Bruno R. Preiss. „Expression Trees“ (1998). 19-yanvar 2017-yilda asl nusxadan arxivlandi . Qaraldi: 20-dekabr 2010-yil. Bruno R. Preiss (1998). „Expression Trees“ . Archived from the original on January 19, 2017 . Retrieved December 20, 2010 . Internet saytlar 1.httpps://uz.m.wikipedia.org/wiki/Daraxtlar 2.https://uz.zahn-info-portal.de/wiki/Binary_tree 2.https://uz.m.wikipedia.org/wiki/Binar_daraxti

Mavzu: Daraxtlar. Ikki tomonlama daraxtlar. Ikkilik daraxtlar vakili. Pryufer kodi. Reja: Kirish Asosiy qism. 1.Daraxtlar haqida umumiy tushuncha. 2.Ikkilik daraxtlarning vakili. 3. Pryufer kodi. Xulosa Foydalanilgan adabiyotlar.

Kirish Bizga dasturlash hayotimizda muhim ro l o ynaydi. Bunda bizga algoritmlash faniʻ ʻ yordam beradi. Algoritmlash fanining bir bo limi bu daraxtlar va graflar ʻ nazariyasi.Daraxt - bu bog langan asiklik graf, ya’ni sikllar yo q va uchlar juftligi ʻ ʻ orasida bitta yo l bor (29-rasm). Kirishning nol darajasiga ega bo lgan uch ʻ ʻ daraxtning ildizi, chiqish nol darajaga ega tugunlar esa barglar deb nomlanadi. Graflar nazariyasi haqida umumiy ma’lumotlar. 1736 yilda L. Eyler tomonidan o‘sha davrda qiziqarli amaliy masalalardan biri hisoblangan Kyonigsberg ko‘priklari haqidagi masalaning qo‘yilishi va yechilishi graflar nazariyasining paydo bo‘lishiga asos bo‘ldi. Kyonigsberg shahridagi Pregel daryosi ustida qurilgan yettita ko‘priklar joylashuvi 1- shakldagi qadimiy xaritada tasvirlangan va qurilishi tartibida 1, 2, 3, 4, 5, 6 va 7 raqamlar bilan belgilangan. Pregel daryosi Kyonigsberg shahrini o‘sha davrda to‘rtta , , va qismlarga bo‘lgan. Shaharning ixtiyoriy qismida joylashgan uydan chiqib yettita ko‘priklardan faqat bir martadan o‘tib, yana o‘sha uyga qaytib kelish mumkinmi? Kyonigsberg ko‘priklari haqidagi bu masalani hal qilish jarayonida graflarda maxsus marshrut (hozirgi vaqtda graflar nazariyasida bu marshrut Eyler sikli nomi bilan yuritiladi, mavjudligi shartlari ham topildi. Bu natijalar e’lon qilingan tarixiy ilmiy ishning birinchi sahifasi 2- shaklda keltirilgan. L. Eylerning bu maqolasi yuz yildan ko‘p vaqt mobaynida graflar nazariyasi bo‘yicha yagona ilmiy ish bo‘lib keldi.

XIX asrning o‘rtalarida graflar nazariyasi bilan bog‘liq tadqiqotlar G. Kirxgof va A. Keli ishlarida paydo bo‘ldi. “Graf” iborasi D. Kyonig tomonidan 1936 yilda graflar nazariyasiga bag‘ishlangan dastlabki darslikda uchraydi. Graflar nazariyasi bo‘yicha tadqiqotlar natijalari inson faoliyatining turli sohalarida qo‘llaniladi. Ulardan ba’zilari quyidagilardir: boshqotirmalarni hal qilish; qiziqarli o‘yinlar; yo‘llar, elektr zanjirlari, integral sxemalari va boshqarish sistemalarini loyihalashtirish; avtomatlar, blok-sxemalar va komp’yuter uchun programmalarni tadqiq qilish va hokazo. Kurs ishining maqsadi. Algoritmlash fanini talabalarga o qitish va uniʻ rivojlantirish. Kurs ishining vazifasi. Agoritmlash fanini o tgan choraklarga qaraganda ʻ rivojlantirish va uni namoyish etish. Kirs ishining tarkibi. Mazkur ish "Kirish" Asosiy qism, "Xulosa", hamda foydalanilgan adabiyotlardan tashkil topgan. Asosiy qism 1.Mavzu:Daraxtlar haqida umumiy tushuncha Daraxt - bu bog langan asiklik graf, ya’ni sikllar yo q va uchlar juftligi orasida ʻ ʻ bitta yo l bor Kirishning nol darajasiga ega bo lgan uch daraxtning ildizi, chiqish ʻ ʻ nol darajaga ega tugunlar esa barglar deb nomlanadi. Ulanish har qanday uchlar juftligi o rtasida marshrut mavjudligini anglatadi, aylanuvchanlik sikllar yo qligini ʻ ʻ anglatadi. Demak, xususan, shundan kelib chiqadiki, daraxtdagi qirralarning soni uchlar sonidan bitta kamroq va har qanday uchlar juftlari orasida bitta va faqat bitta yo l bor. ʻ O rmon – juda ko p daraxtlardir. ʻ ʻ

Yo naltirilgan (oriyentirlangan) daraxt - bu faqat bitta vertikal kirish nol darajasigaʻ ega bo lgan (boshqa yoylar unga olib kelmaydigan), boshqa uchlarning kirish ʻ darajasi 1 bo lgan siklik orgraf (sikllarni o z ichiga olmaydigan yo naltirilgan ʻ ʻ ʻ graf). Yo naltirilgan daraxt ʻ Daraxtning asosiy tushunchalari Ildiz tuguni - daraxtning eng yuqori tuguni (18-rasmdagi 8-tugun ). Ildiz – ixtiyoriy tanlab olingan uchlardan biri. Barg yoki terminal tuguni – avlodi mavjud bo lmagan tugun (18-rasmdagi 1, 4, 7, 13 tugunlari). ʻ Ichki tugun - bu daraxtga avlodi mavjud bo lgan har qanday tugun va shuning ʻ uchun barg tuguni emas (18-rasmda 3, 6, 10, 14). Uchning darajasi - unga tushgan qirralarning soni.

Sentroid - uch, u olib tashlanganida hosil bo lgan ulanish komponentlariningʻ o lchamlari n2 dan oshmaydi (asl daraxtning yarmi kattaligi) ʻ Tugun. Tugun - bu ba’zi bir qat’iy tabiat obyektiga mos keladigan ikki turdagi graf elementlaridan birining nusxasi. Tugun ma’lum bir ma’lumot strukturasining yoki daraxtning o zi qiymatini, holatini yoki ko rinishini o z ichiga olishi mumkin. ʻ ʻ ʻ Daraxtning har bir tugunida daraxt ostida joylashgan nol yoki undan ko p avlod ʻ tugunlari mavjud (odatda, daraxtlar haqiqiy daraxtlar singari yuqoriga emas, pastga qarab "o sadi"). Avlodga ega bo lgan tugun o z avlodiga nisbatan ajdod tugun deb ʻ ʻ ʻ nomlanadi (oldingi tugun yoki kattaroq tugun). Har bir tugunning ko pi bilan bitta ʻ ajdodi bor. Tugunning balandligi - bu tugundan eng pastki tugunga (chekka tugunga) barg deb ataladigan pastga tushadigan yo lning maksimal uzunligi. Ildiz tugunining ʻ balandligi butun daraxtning balandligiga teng. Ildiz tugunlari. Ajdodlari bo lmagan ʻ tugun (eng yuqorisi) ildiz tuguni deb ataladi. Bu daraxtdagi ko plab amallar ʻ boshlanadigan tugun (garchi ba’zi algoritmlar "barglar" dan boshlanib, ular ildizga yetguncha davom etadi). Boshqa barcha tugunlarga ildiz tugunidan qirralar (yoki bog lanishlar) bo ylab harakatlanish orqali erishish mumkin (rasmiy ta’rifga ko ra, ʻ ʻ ʻ har bir bunday yo l noyob bo lishi kerak). Diagrammalarda u odatda eng yuqori ʻ ʻ qismida tasvirlangan. Ba’zi daraxtlarda, masalan, uyumlarda, ildiz tuguni maxsus xususiyatlarga ega. Daraxtdagi har bir tugunni shu tugundan "o sayotgan" kichik ʻ daraxtning ildiz tuguni deb hisoblash mumkin. Daraxt osti - bu alohida daraxt sifatida namoyish etilishi mumkin bo lgan daraxtga o xshash ma’lumotlar ʻ ʻ strukturasining bir qismidir. T daraxtining har qanday tuguni va uning barcha nasl tugunlari bilan birga T daraxtining pastki daraxti hisoblanadi. Daraxt osti har qanday tuguni uchun, yo ushbu kichik daraxtning ildiz tuguniga yo l bo lishi ʻ ʻ kerak, yo tugunning o zi ildiz bo lishi kerak. Ya’ni, kichik daraxt ildiz tuguniga ʻ ʻ butun daraxt bilan bog lanadi va boshqa barcha tugunlar bilan daraxt osti aloqasi ʻ tegishli daraxt osti tushunchasi orqali aniqlanadi (“to plam osti" atamasi bilan ʻ o xshashlik bo yicha). ʻ ʻ

O'xshashlar

Daraxtlar, ikki tomonlama daraxtlar. Ikkilik daraxtlarning vakili. Ikkilik daraxtlarning o'tishi
Dataxtlar, ikki tomonlama daraxtlar, ikkilik daraxtlarning vakilligi, ikkilik daraxtlarning o’tishi
Elyer o’tuvchi daraxtlar
Balanslangan qidiruv daraxtlari
DEKART DARAXTI (TREAP, DERAMID)