Дарахтсимон тузилмалар

Алгоритм

Бинар дарахт яратиш процедурси

Бинар дарахтни хосил қилиш учун ЭХМ хотирасида элементлар қуйидаги турда бўлиши лозим

P, Q – ишчи кўрсаткичлар

V=maketree(key,rec) – калит ва ёзув сегментини яратувчи процедура

P=getnode – янги элемент генерацияси

r=rec

k=key

V=P

left=nil

right=nil

tree – дарахт илдизига кўрсаткич

Бошида калит биринчи қиймати киритилади. Ундан сўнг элементн ўзини maketree процедураси орқали ҳосил қиламиз. Кейин эса кўрсаткич бўш қийматни кўрсатгунча циклни бўйича давом эттирамиз.

Topshiriq : Binar(Oddiy va Rekursiv) qidiruv algoritmi yordamida kiritilgan element “Daraxtsimon tuzilma”da bor yo yo’qligini aniqlang. Tuzilma elementlari ixtiyoriy o’sish tartibidagi sonlar.

Massiv elementlari sifatida { 2, 5, 8, 12, 23, 41, 56, 79, 90 } sonlari olindi

Topshiriq kodi : C++ dasturlash tilida :

#include

using namespace std;

int qidiruvBinar(int a[],int n,int r)

{

int c=n,l=0,mid;

for(int i=0; n>i; i++)

{

mid=(l+c)/2;

if(a[i]==r)

return i;

else if(a[i]

mid+1;

else if(a[i]>r)

mid-1;

}

return -1;

}

int RekursivBinar(int a[],int r,int l)

{

int n=9,c=n,mid;

if(l>n)

return -1;

mid=(l+c)/2;

if(a[mid]==r)

return mid;

else if(a[mid]

return RekursivBinar(a,r,mid+1) ;

else return RekursivBinar(a,r,l) ;

}

int main()

{

int n=9,j,a[100] = { 2, 5, 8, 12, 23, 41, 56, 79, 90 },r,key,l=0;

cout << "Axrorov Shuhratbek\t SWD030-L3\n\n";

cout << "\tOddiy binar qidiruvidan foydalnish\n\tQidirilayotgan elemntni kiriting ";

cin >> r;

key = qidiruvBinar(a , 9, r);

if(key == -1)

{

cout << "\n\tBunday element binar daraxtida yo'q!!!\n";

}

else

{

cout << "\n\tUshbu " << r << " elementi binar daraxtidan topildi!\n";

cout << "\tUning indeksi = " << key ;

}

cout << "\n\n\tRekursiv binar qidiruvidan foydalnish\n\tQidirilayotgan elemntni kiriting ";

cin >> j;

key = qidiruvBinar(a,j,l);

if(key == -1)

{

cout << "\n\tBunday element binar daraxtida yo'q!!!\n";

}

else

{

cout << "\n\tUshbu " << j << " elementi binar daraxtidan topildi!\n";

}

}

Dastur kompilyatsiyadan o’tganligi va javob olinganligi haqidagi ScreenShotlar :