Fan: Algoritmlar va ma'lumotlar strukturalari

4.10. Binar daraxt balandligi

Binar daraxtning balandligi deb daraxt bosqichlari soniga aytiladi. Binar daraxt balandligini aniqlash uchun uning har bir tuguni chap va o’ng qismdaraxtlari balandliklari solishtiriladi va maksimal qiymat balandlik deb olinadi. Misol uchun quyidagi 4.9-rasmdagi daraxtning balandligi 2 ga teng.

4.9-rasm. Binar daraxt balandligi

Daraxt balandligini aniqlash dastur kodini keltiramiz.

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);

}

}


4.11. Binar daraxtni muvozanatlanganmi yoki yo’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<

vizual(tree->left,l+1);

}

}

int AVLtree (node *tree){

int t;

if (tree!=NULL){

20. 
    = 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>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<

cout<<‘\nbinar daraxt:\n’;

vizual(tree,0);

AVLtree(tree);

if(GetFlag()) cout<<‘ha, muvozanatlangan daraxt’; else cout<<‘yo’q, muvozanatlanmagan daraxt’;cout<

getch();

}


Dastur natijasi

XULOSA
Ko’rish maydonidagi obyektlar soni bittadan ko’p bo’lgan holda ularni geometrik xarakteristikalarini hisoblab bo’lmaydi. Bunday xolda ularning topologik xarakteristikalaridan foydalanib murakkab obyektni sodda obyektlarga ajratish mumkin.

1. Binar tasvirlarning ikki elementlari o’rtasida bog’liqlikning xar tomonlama tahlil va qilindi va tasvirni turli kompanentalariga belgi qo’yish usullari ishlab chiqildi. Bu usullar tasvir elementlarining o’zaro bog’liqlik (qo’shni) tushunchasini kiritish muxiti va ularni ko’rib chiqish ketma-ketligi bilan bir-biridan farq qiladi.
2. Tasvirlarga ishlov berishni qisqa vaqt ichida amalga oshirish uchun hisoblash jarayonlarini paralellashtirishdan keng foydalaniladi. Shuning uchun binar tasvirga lokal usulda va interaktiv modifikasiya usulda ishlov berish algoritmlarining yutuq va kamchiliklari tahlil qilingan. Ya’ni:
Binar tasvirlarning berilish usullari va xarateristikalarini o’rganib chiqdim; Trassani izlashning to’lqinli izlash algoritmini bilan tanishdim va dasturini tuzildi; Trassani izlashning marshrutli izlash algoritmini o’rganildi va dasturi tuzildi; Xaritaning bitkartali tasvirida eng qisqa yo’lni aniqlash dasturini ishlab chiqildi. To’lqinli algoritmnin yutug’i shundaki, uning yordamida ixtiyoriy labirintda va ixtiyoriy sondagi to’siqlarda trassani topish mumkin. Yagona kamchiligi trassani qurishda katta xajmdagi xotirani talab qiladi. Marshrutli izlash algoritmning asosiy yutug’i soddaligidir, va yana unda diagonal bo’ylab harakatlanish mumkin.

ADABIYOTLAR

1. Ўзбекистон Республикаси қонун ҳужжатлари тўплами, 2012 й., 13-сон, 139-модда.(http://www.lex.uz)
2. Ўзбекистон Республикаси қонун ҳужжатлари тўплами, 2012 й., 5-сон, 47-модда. (http://www.lex.uz)
3. Ўзбекистон Республикаси Президентининг “Компьютерлаштиришни янада ривожлантириш ва ахборот-коммуникация технологияларини жорий этиш тўғрисида” 2002 йил 30 майдаги ПФ-3080-сонли фармони.
4. Ўзбекистон Республикаси Вазирлар маҳкамасининг “Компьютерлаштиришни янада ривожлантириш ва ахбороткоммуникация технологияларини жорий этиш чора-тадбирлари тўғрисида” 2002 йил 6 июндаги 200-сонли қарори.
5. Павлидис Т. Алгоритмы машинной графики и обработки изображений. -М.: Радио и связь, 1986.
6. Байгарова Н.С., Бухштаб Ю.А., Евтеева Н.Н., Корягин Д.А. Некоторые подходы к организации содержательного поиска изображений и видеоинформации. Препринт Института прикладной математики им. М.В. Келдыша РАН. Москва, 2002.
7. Гуленко И.Е. Система видеозахвата и анализа движения – распознавание трансформаций и движения объекта. – Труды конференции “Новые информационные технологии” (Судак, Крым, 15– 25 мая 2004 г.), с. 141-142. 8.Байгарова Н.С., Бухштаб Ю.А., Горный А.А.. Методы индексирования и поиска визуальных данных. Препринт Института прикладной математики им. М.В. Келдыша РАН, N 7. Москва, 2000.
9.www.ziyonet.uz
10.www.arxiv.uz
11.www.google.uz