daraxtlarni prufer usulida kodlash. daraxtlarni ularning kodi bo'yicha yasash

DOCX 264,6 КБ Бесплатная загрузка

Предварительный просмотр (5 стр.)

Прокрутите вниз 👇

1693470913.docx daraxtlarni prufer usulida kodlash. daraxtlarni ularning kodi bo'yicha yasash daraxtlarni prufer usulida kodlash. daraxtlarni ularning kodi bo'yicha yasash reja: 1) binar daraxtlar haqida 2) daraxtlar ustida ba`zi amallar 3) daraxtlarni ularning kodi bo`yicha yasash 4) xulosa 5) foydalanilgan adabiyotlar 1) daraxt - bu uning har bir tuguni nol yoki bir- necha bolaga ega bo‘lgan iyerarxik tuzilmadir. daraxt tuzilmasi quyidagi ko‘rinishda bo‘lishi mumkin: bu daraxt oila tuzilmasini ifoda etmoqda. daraxt tugunlari odamlarni ifodalamoqda, chiziqlar esa ular orasidagi bog‘lanishni. bu turdagi maʼlumotlarni saqlash uchun daraxt tuzilmasi eng qulay tuzilma hisoblanadi. ikkilik (binar) daraxt binar daraxt yuqorida ko‘rsatilgan daraxtga o‘xshaydi, lekin baʼzi qoidalarga asosan quriladi: · har bir tugundagi bolalar soni 2 tadan oshmasligi zarur · xar qanday tugun qiymatidan kichik bo‘lgan qiymat chap farzandga yoki chap farzandning chap farzandiga yoziladi · xar qanday tugun qiymatidan katta bo‘lgan qiymat o‘ng farzandga yoki ong farzandning o‘ng farzandiga yoziladi keling shu qoidalar asosida qurilgan …

adi. shunday qilib kiritilgan xar bir element uchun yuqoridagi solishtiruvlar qaytariladi. daraxtdan element olib tashlash daraxt elementini o‘chirish oddiy tuyulishi mumkin, lekin hisobga olish kerak bo‘lgan holatlari mavjud. algoritmning umumiy ko‘rinishi quyidagicha: · qiymatga mos elementni topish · uni o‘chirish biz berilgan qiymatga mos qiymatni topganimizdan keyin biz 3- xil holatga duch kelishimiz mumkin. 1 – holat: o‘chirilishi lozim bo‘lgan elementning o‘ng farzandi mavjud emas. bu holatda biz, shunchaki chap farzandni o’chirilgan element o’rniga ko’chiramiz. natijada yuqoridagi daraxt quyidagi ko’rinishga keladi: 2 – holat: o’chirilishi lozim bo’lgan elementning faqat o’ng farzandi mavjud va o’z navbatida bu farzandning chap tomonida element mavjud emas. bu holatda o’chirilgan element o’rniga o’ng farzand (6) ko’chiriladi. natijada daraxt quyidagi ko’rinishga keladi: 3 – holat: o’chirilayotgan elementning o’ng farzandi mavjud va bu farzandning chap farzandi mavjud: bu holatda o‘chirilgan element o‘rinini eng chapdagi element egallaydi yaʼni 6. bunga sabab element o‘chirilganda tuzilma o‘z xususiyatlarini saqlab qolishi …

a yangi yozuvni kiritish uchun, avvalo daraxtning shunday tugunini topish lozimki, natijada mazkur tugunga yangi element qo’shish mumkin bo’lsin. kerakli tugunni qidirish algoritmi ham xuddi berilgan kalit bo’yicha tugunni topish algoritmi kabi bo’ladi. daraxtda qo’shilayotgan element kalitiga teng kalitli element yo’q bo’lgan holda 5.8. binar daraxtdan elementni o’chirish funksiyasi tugunni o’chirib tashlash natijasida daraxtning tartiblanganligi buzilmasligi lozim. tugun daraxtda o’chirilayotganda 3 xil variant bo’lishi mumkin: 1) topilgan tugun terminal (barg). bu holatda tugun otasining qaysi tomonida turgan bo’lsa, otasining o’sha tomonidagi shoxi o’chiriladi va tugunning xotirada joylashgan sohasi tozalanadi. 2) topilgan tugun faqatgina bitta o’g’ilga ega. u holda o’g’il ota o’rniga joylashtiriladi. 3) o’chirilayotgan tugun ikkita o’g’ilga ega. bunday holatda shunday qism daraxtlar zvenosini topish lozimki, uni o’chirilayotgan tugun o’rniga qo’yish mumkin bo’lsin. bunday zveno har doim mavjud bo’ladi: - bu yoki chap qism daraxtning eng o’ng tomondagi elementi (ushbu zvenoga erishish uchun keyingi uchiga chap shox orqali o’tib, navbatdagi …

an) 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 1. binar daraxtni yaratib olamiz. 2. 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. 3. 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. 4. 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 …

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 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 vizual(tree->left,l+1);}} int avltree (node *tree){ int t; if (tree!=null){ t = height (tree->left) - height (tree->right); if ((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; int arr[n]; for(int i=0; i node *p=new node; node *last=new …

Хотите читать дальше?

Скачайте полный файл бесплатно через Telegram.

Скачать полный файл

О "daraxtlarni prufer usulida kodlash. daraxtlarni ularning kodi bo'yicha yasash"

1693470913.docx daraxtlarni prufer usulida kodlash. daraxtlarni ularning kodi bo'yicha yasash daraxtlarni prufer usulida kodlash. daraxtlarni ularning kodi bo'yicha yasash reja: 1) binar daraxtlar haqida 2) daraxtlar ustida ba`zi amallar 3) daraxtlarni ularning kodi bo`yicha yasash 4) xulosa 5) foydalanilgan adabiyotlar 1) daraxt - bu uning har bir tuguni nol yoki bir- necha bolaga ega bo‘lgan iyerarxik tuzilmadir. daraxt tuzilmasi quyidagi ko‘rinishda bo‘lishi mumkin: bu daraxt oila tuzilmasini ifoda etmoqda. daraxt tugunlari odamlarni ifodalamoqda, chiziqlar esa ular orasidagi bog‘lanishni. bu turdagi maʼlumotlarni saqlash uchun daraxt tuzilmasi eng qulay tuzilma hisoblanadi. ikkilik (binar) daraxt binar daraxt yuqorida ko‘rsatilgan daraxtga o‘xshaydi, lekin baʼzi qoidalarga asosan quril...

Формат DOCX, 264,6 КБ. Чтобы скачать "daraxtlarni prufer usulida kodlash. daraxtlarni ularning kodi bo'yicha yasash", нажмите кнопку Telegram слева.

Теги: daraxtlarni prufer usulida kodl… DOCX Бесплатная загрузка Telegram