Texnologiyalari va kommunikatsiyalarni rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalar universiteti

Daraxat yechimlari


Daraxt-bu chiziqsiz bog’langan ma’lumotlar tuzilmasidir.




Daraxt o’zining quyidagi belgilari bilan tasniflanadi:
Daraxtda shunday bitta element borki, unga boshqa elementlardan murojat yo’q. Mazkur elementga daraxt ildizi deyiladi;
Daraxtda ixtiyoriy elementga chekli sondagi ko’rsatgichlar yordamida murojaat qilish mumkin;
Daraxtning har bir elementi faqatgina o’zidan oldingi kelgan bitta element bilan bog’langan.
Daraxtning har bir tuguni orqaliq yoki terminal (barg) bo’lishi mumkin.


Daraxt bosqichlari soniga daraxt balandligi deyiladi.

Tugunlardan chiqayotgan shohlar soni tugundan chiqish darajasi deyiladi.

Daraxtlar klassifikatsiyasi
Daraxt chiqish darajasi bo’yicha klassifikatsiya qilinadi.
1) Agar maksimal darajasi m bo’lsa, u holda bunday daraxt m-tartibli daraxt deyiladi;
2) Agar chiqish darajasi 0 yoki m bo’lsa, u holda to’liq m – tartibli daraxt deyiladi;
3) agar maksimal chiqish darajasi 2 bo’lsa, u holda bunday daraxt binary daraxt deyiladi;
4) agar chiqish darajasi 0 yoki 2 bo’lsa, u holda to’liq binary daraxt deyiladi.
Tugunlar orasidagi bog’liqlikni tavsiflash uchun yana quyidagicha atamadan foydaliniladi: Otao’g’il.


Daraxtlarni tavsiflash
Mantiqiy tasvirlashda daraxtlar bog’langan ro’yhatlar ko’rinishda ifodalanadi. Bunda ro’yhat elementi tugun qiymati va chiqish darajasini o’z ichiga oluvchi information maydonga hamda chiqish darajasiga teng bo’lgan ko’rsatkichlar maydoniga ega bo’ladi.
Daraxt grafik va chiziqsiz ro’yhat shaklidagi tasvirlanishi.


Daraxtlar ustida bajariladigan amallar

1. Daraxt ko’ruvi (Obxod dereva).

2. Qism daraxtni o’chirish.
3. Qism daraxt qo’yish.
Daraxt ko’ruvini amalga oshirish uchun quyidagi uchta prosedurani bajarish lozim:
1. Ildizni qayta ishlash.
2. Chap tarmoq(shox)ni qayta ishlash.
3. O’ng tarmoq(shox)ni qayta ishlash.
Yuqoridagi prosedura qanday ketma-ketlikda amalga oshirilishiga qarab ko’ruvni uchta ko’rinishga ajratiladi.

1. Yuqoridan quyiga. Prosedur quyidagi ketma-ketlikda bajariladi
A-B-C.
2.Chapdan o’ng. Prosedur quyidagi ketma-ketlikda bajariladi
B-A-C.
3. Quyidan yuqoriga. Prosedur quyidagi ketma-ketlikda bajariladi
B-C-A.

Masalan quyidagi daraxtda ko’ruv o’tkazaylik.

Daraxat ko’ruvi tartibi: Yuqoridan pastga: A,B,C,D,E,F,G. Chapdan o’nga: C,D,B,E,F,A,G. Pastdan yuqoriga: D,C,F,E,B,G,A.

Daraxt ko’rigini rekursiv prosedurlari:

1. 
   int pretrave(node *tree){
   

if(tree!=NULL) {int a=0,b=0;
if(tree->left!=NULL) a=tree->left->info;
if(tree->right!=NULL) b=tree->right->info;
cout<info<<" - chapida "<
pretrave(tree->left);
pretrave(tree->right);
}
return 0;
};

2. 
   int intrave(node *tree){
   

if(tree!=NULL) {
intrave(tree->left);
cout<info;
intrave(tree->right);
}
return 0;
};

3. 
   int postrave(node *tree){
   

if(tree!=NULL) {
postrave(tree->left);
postrave(tree->right);
cout<info;
}
return 0;
};


Xulosa

Kompyuter apparat kabi algoritmlami ham, texnologiya sifatida hisobga olinishimiz kerak. Umumiy tizim ish faoliyatini algoritm samaradorligiga ham bog‘liq va apparat kuchiga ham. Algoritm rivojlantirish sohasida jadal rivojlantirish bo‘lyapti, boshqa kompyuter texnologiyalaridek. Savol tug'iladi, algoritmlar shunchalik muhimi, zamonaviy kompyuterlarda ishlaydigan boisin. agar shunday kabi yuqori texnologiyalar boshqa sohalarda ulkan yutuqlarga erishilgan bo'Isa:

• zamonaviy kompyuter mimarileri va ularning ishlab chiqarish texnologiyalari; • osonlik bilan erishish, intuitiv grafik fovdalanuvchi interfeysi (GUI);
• obyektga yo‘naltirilgan tizimlar;
• integratsiyalashgan web texnologiyasi;
• tezroq tarmoqlari, simli va simsiz.
Misol uchun, bir joydan boshqasiga olish uchun qanday belgilaydigan Web xizmat. Uni amalga oshirish bir yuqori samarali apparat, grafik foydalanuvchi interfeysi, bir global tarmoq ehtimol, bir obyekt vo'naltiriigan yondashuv yotadi. Bundan tashqari, bunday yo'nalishlarini topish kabi bir berilgan web-xizmati tomonidan amalga muayyan operatsiyalar uchun zarur algoritmlami foydalanish, ko'rish va enterpolatsyon manzilini, xaritalar bilan foydalaniladi. Bundan tashqari, dastur, 2 Thomas H Comien va b. Intruduction to algorithms. Massachusetts Institute o f Technology. London 2009. (1 l-13pp) 16 yuqori saviyada algoritmik mazmunini talab qilmaydi, kuchli algoritmlarga bog‘liq. Bu dastur ishlash apparat ishiga bog‘liq ekanligi ma'Ium va amaliy rivojlanishida turli algoritmlardan foydalaniladi.
Biz hammamiz bilamizki, ilova yaqindan grafik foydalanuvchi interfeysi bilan bogiiq va har qanday grafik foydalanuvchi interfeysini ishlab chiqish uchun talab algoritmlari kerak bo‘ladi. Tarmoq ustida ishlaydigan ilovalarni eslatib o’tamiz. Ular faoliyat olib borishlari uchun, algoritmlarga asoslangan yo‘nalishni olib borishlari kerak bo‘ladi. Eng keng tarqalgan dasturlar tilda tuziladi, mashinadan farqli. Ularning kodi turli kompilyator va interpretatorlar bilan islilov beriladi, turli algoritmlardan keng foydalanadi. Bundan tashqari, kompyuterlar kuchini doimiy o‘sishi, ular tobora murakkab vazifalarni hal qilish uchun qo‘llaniladi. Biz muammoni murakkabligini o’tishimiz bilan, ikki saralash usullari qiyosiy tahlili rnisolida ko‘rib turganimizdek eng muhim farqlar algoritmlari samaradorligi oshirilmoqda. Asosiy algoritmlar va ularni rivojlantirish usullari-asosiy xususiyatlatdan biri. Zamonaviy kompyuter texnologiyalari bilan, ayrirn vazifalarni algoritmlarni bilmagan holda ham qilinishi mumkin, lekin bu sohada ko‘p narsaga erishish mumkin
Foydalanilgan adabiyotlar

1. google.ru C++ oid mavzular

2. ziyonet.uz Algoritm ga oid mavzularda
3. M.O‘. ASHUROV, SH.A. SATTAROVA, SH.U. USMONQULOV
ALGORITMLAR
4. ПРОГРАММИРОВАНИЕ С/С++. ПРОЕКТИРОВАНИЕ АЛГОРИТМОВ
И ПРОГРАММ
Учебное текстовое электронное издание локального
распространения Омск Издательство ОмГТУ 2017
Составитель О. П. Шафеева, канд. техн. наук, доцент кафедры ИВТ