Ikkilik daraxtning balandligini qanday topish mumkin?

Muhammad al-Xorazmiy nomidagi Toshkent axborot texnologiyalari universiteti Samarqand filiali

“Kompyuter injiniring” fakulteti

“Dasturiy injiniring” yo’nalishi

“Ma’lumotlar tuzilmasi va Algoritmlar” fanidan

Ishlagan 8- hafta topshirig’i

Bajardi: Hamzaqulov Og’abek DI20-11-guruh

Tekshirdi: Mirsaidov. B

Mavzu: Binar daraxtlar.Daraxt balandligi va ko’ruv. Muvozanatlashgan binary daraxtlar.Binary Heap.

1. 
   Ishdan maqsad:
   

Daraxtlar ustida bajariladigan amallar:tugun qo’yish, o’chirish va o’rnini almashtirish, Daraxtlarni binary ko’rinishga keltirish masalalarini ko’rib chiqish

2. 
   Mavzu bo’yicha qisqacha tushunchalar
   

 Ikkilik daraxt - bu kompyuter texnologiyalari sohasida ma'lumotlarni saqlash sxemalari uchun qabul qilingan noyob ma'lumotlar strukturasidir. Ikkilik daraxtning har bir tugunida ko'pi bilan ikkita bola bo'lishi mumkin. Ikkilik daraxt ma'lumotlar tuzilmasidan foydalanish foydalidir, chunki u tartiblangan massiv va bog'langan ro'yxatning afzalliklariga ega, shuning uchun qidiruv uchun vaqt murakkabligi tartiblangan massivdagi kabi tezdir va kiritish yoki o'chirish operatsiyalari bir qatordagi kabi tezdir. bog'langan ro'yxat. 

Ikkilik daraxtga misol: 

Ikkilik daraxtning balandligini qanday topish mumkin?

Ikkilik daraxtning balandligi ildiz tugunidan boshlab ikkilik daraxtning har qanday barg tuguniga qadar eng uzun yo'l hisoblanadi. Agar biz balandlikni hisoblashimiz kerak bo'lgan maqsadli tugunga boshqa tugunlar ulanmagan bo'lsa, u holda bu tugunning balandligi 0 ga teng bo'ladi. Shunday qilib, biz ikkilik daraxtning balandligi deb aytishimiz mumkin. butun ikkilik daraxtdagi ildiz tugun. Oddiy so'z bilan aytganda, ikkilik daraxtning balandligi ikkilik daraxtning ildizidan boshlab eng siyrak barg tuguniga qadar bo'lgan qirralarning eng katta miqdoriga teng.

Ikkilik daraxt ma'lumotlar strukturasidagi tegishli tushuncha daraxtning chuqurligidir. Ikkilik daraxtda tugunning chuqurligi ta'rifiga ko'ra, ildiz tugunidan maqsad tugungacha bo'lgan umumiy qirralarning miqdori. Bundan tashqari, ikkilik daraxtning chuqurligi - ildiz tugunidan boshlab eng uzoqdagi barg tuguniga qadar qirralarning umumiy miqdori. Va bu maqolada biz ikkilik daraxtning balandligi/maksimal chuqurligini rekursiya yordamida va rekursiyadan foydalanmasdan qanday topishni bilib olamiz. 

Misol: Quyidagi rasmda 4 darajali ikkilik daraxt ko'rsatilgan. 

3. 
   Masalani yechish (algoritm, dastur kodi, natija)
   

Berilgan binar daraxtning har bir tuguni chap tomoni tugunlaridan tashkil topgan muvozanatlangan binar daraxt hosil qilish algoritmi va dasturini tuzing.

Dastur kodi:

// Binary Tree in C++

#include

#include

using namespace std;
struct node {

int data;

struct node *left;

struct node *right;

};
struct node *newNode(int data) {

struct node *node = (struct node *)malloc(sizeof(struct node));

node->data = data;
node->left = NULL;

node->right = NULL;

return (node);

}

void traversePreOrder(struct node *temp) {

if (temp != NULL) {

cout << " " << temp->data;

traversePreOrder(temp->left);

traversePreOrder(temp->right);

}

}
void traverseInOrder(struct node *temp) {

if (temp != NULL) {

traverseInOrder(temp->left);

cout << " " << temp->data;

traverseInOrder(temp->right);

}

}
void traversePostOrder(struct node *temp) {

if (temp != NULL) {

traversePostOrder(temp->left);

traversePostOrder(temp->right);

cout << " " << temp->data;

}

}
int main() {

struct node *root = newNode(1);

root->left = newNode(2);

root->right = newNode(3);

root->left->left = newNode(4);

cout << "Daraxtning oldingi ko'rinishi: ";

traversePreOrder(root);

cout << "\nDaraxtning keyingi ko'rinishi: ";

traverseInOrder(root);

cout << "\nVa daraxtning oxirgi ko'rinishi: ";

traversePostOrder(root);

}

4. 
   Xulosa:
   

Daraxtlar ustida bajariladigan amallar:tugun qo’yish, o’chirish va o’rnini almashtirish, daraxtlarni binary ko’rinishga keltirish masalalarini dasturda bajarishni o’rgandik.