O’ZBEKISTON RESPUBLIKASI O’LIY TA’LIM , FAN VA INNOVATSIYALAR VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALAR UNIVERSITETI
Ma’lumotlar tuzilmasi va algoritm
6-Amaliy ish topshirig’i
Guruhi: SWD-018-2
Bajardi : Mamatov Sherzod
Tekshirdi : Bo’riyev Yusuf
Daraxt ko’rinishidagi ma’lumotlar
tuzilmasi haqida umumiy tushunchalar.
Daraxt ma'lumotlar strukturasi - ierarxik tuzilma bo'lib, u ma'lumotlarni navigatsiya qilish va qidirish uchun qulay tarzda taqdim etish va tartibga solish uchun ishlatiladi. Bu qirralar bilan bog'langan va tugunlar o'rtasida ierarxik munosabatlarga ega bo'lgan tugunlar to'plamidir.
Daraxtning eng yuqori tuguniga ildiz deyiladi, uning ostidagi tugunlarga esa bola tugunlari deyiladi. Har bir tugun bir nechta tugunlarga ega bo'lishi mumkin va bu tugunlar ham rekursiv tuzilmani tashkil etuvchi o'z tugunlariga ega bo'lishi mumkin.
Ildiz tugun daraxt ierarxiyasining eng yuqori tugunidir. Boshqacha qilib aytganda, ildiz tugunlari ota-onasi bo'lmagan tugundir. Yuqoridagi strukturada 1-raqamli tugun daraxtning ildiz tugunidir. Agar tugun to'g'ridan-to'g'ri boshqa tugun bilan bog'langan bo'lsa, u ota-ona munosabatlari deb ataladi
Tugunlar: Tugunlar ma'lumotlaringizning qiymatini saqlaydi, bu raqamlar, satrlar va boshqalar
Ildiz: Ildiz tugun daraxtning birinchi tugunidir. Yuqoridagi misolda ildiz tugun 2 ga teng.
Child: Ildiz tugunidan uzoqroqda joylashgan boshqa tugunga bevosita bog'langan tugun.
Parent:Bolaning teskarisi
Siblings:: bir xil ota-onaga ega bo'lgan tugunlar guruhi. Yuqoridagi misolda 9,12,8,99,10 barcha birodarlardir.
Leaf: bolalari bo'lmagan tugun. Yuqorida, 2 barg tuguniga misoldir.
Savol: Binar daraxtning tugunlari sonini aniqlashning algoritmi va dasturini keltiring
#include
using namespace std;
// Node structure for the binary tree
struct Node {
int data;
Node* left;
Node* right;
};
// Create a new node
Node* newNode(int value) {
Node* node = new Node();
node->data = value;
node->left = nullptr;
node->right = nullptr;
return node;
}
// Function to count nodes excluding the root
int countNodesExcludingRoot(Node* root) {
if (root == nullptr)
return 0;
int count = 0; // Initialize count as -1 to exclude the root node
if (root->left)
count += countNodesExcludingRoot(root->left) + 1;
if (root->right)
count += countNodesExcludingRoot(root->right) + 1;
return count;
}
int main() {
Node* root = newNode(10);
root->left = newNode(5);
root->right = newNode(15);
root->left->left = newNode(3);
root->left->right = newNode(7);
root->right->left = newNode(12);
root->right->right = newNode(18);
int nodesCount = countNodesExcludingRoot(root);
cout << "Number of nodes excluding root: " << nodesCount << endl;
return 0;
}
XULOSA
Daraxt ko'rinishidagi ma'lumotlar tuzilmasi haqida umumiy tushunchalar yozib berishimiz mumkin. Daraxt tuzilmasi bir nechta tugunlardan iborat bo'ladi. Har bir tugun o'ziga xos kalitni saqlaydi va o'ng yoki chap o'lchamdagi boshqa tugunga o'zgartirish orqali ma'lumotlar tuzilmasida joylashadi. Daraxtning boshida o'lchamli tugun joylashadi, undan o'ng tomonida kichik kelgan tugunlar joylashadi, va chap tomonida katta kelgan tugunlar joylashadi. Daraxtning boshidagi tugun "rizq" deb nomlanadi va u erda boshqa tugunlarga yo'l qo'yish uchun o'zgartirishlar saqlanadi. Tugunlar o'ng va chap o'lchamdagi tugunlarga qarab tartiblangan holda joylashadi. Daraxtda eng kichik tugun "engKichikKalit" deb nomlanadi va uni topish uchun "engKichikKalitniTopish" funktsiyasi ishlatiladi. Buning o'ng tomonidagi katta tugun "engKattaKalit" deb nomlanadi va uni topish uchun "engKattaKalitniTopish" funktsiyasi ishlatiladi. Shu bilan birga, dastur foydalanuvchidan elementlar sonini oladi va har bir elementni kiriting. Dastur tugunlarni qo'shadi va eng kichik tugunni va eng katta tugunni topadi. Agar eng kichik tugun bo'sh bo'lsa, "Bo'sh daraxt!" degan xabarni chiqaradi. Agar eng katta tugun bo'sh bo'lsa, "Bo'sh daraxt!" degan xabarni chiqaradi. Agar eng kichik tugun va eng katta tugun mavjud bo'lsa, ularning qiymatlarini chiqaradi.
Kod C++ tilida "UzNode" nomli klassdan foydalanib, ichki qidiruv daraxtasi ma'lumot tuzilmasini aniqlaydi. Daraxt tuzilmasi elementlardan iborat bo'ladi, har bir elementning kalit qiymati va chap-ong o'lchamdagi tugunlarga ko'rsatuvchi o'zgaruvchilari mavjud.
Kod "qoshish" funktsiyasini o'z ichiga oladi, bu funksiya daraxtga element qo'shish uchun ishlatiladi. Agar daraxt bo'sh bo'lsa, yangi bir "UzNode" obyekt yaratiladi va berilgan kalit qiymati va null qiymatga ega bo'lgan tugunlar orqali bu obyektga bog'langan. Aks holda, berilgan kalit qiymatiga qarab daraxtda yuqori yoki pastgi tugunlarga o'tish amalga oshiriladi.
"engKichikKalitniTopish" funktsiyasi daraxtning eng kichik kalit qiymatli tugunini topish uchun ishlatiladi. Agar daraxt bo'sh bo'lsa, null qiymat qaytariladi. Aks holda, daraxtda bosh tugun bo'lsa, u qaytariladi. Aks holda, daraxtning chap tomonidagi tugunlarga qarab rekursiv ravishda qidiruv amalga oshiriladi.
"engKattaKalitniTopish" funktsiyasi daraxtning eng katta kalit qiymatli tugunini topish uchun ishlatiladi. Agar daraxt bo'sh bo'lsa, null qiymat qaytariladi. Aks holda, daraxtda o'ng tomonidagi tugun bo'lsa, u qaytariladi. Aks holda, daraxtning o'ng tomonidagi tugunlarga qarab rekursiv ravishda qidiruv amalga oshiriladi.
Asosiy funksiyada foydalanuvchi elementlar sonini kiritishi so'raladi. Keyin, foydalanuvchidan bir nechta kalit qiymatlari kiritishi so'raladi va "qoshish" funktsiyasi yordamida bu qiymatlarni daraxtga qo'shadi.
Daraxt tuzilgandan so'ng, "engKichikKalitniTopish" funktsiyasi yordamida daraxtda eng kichik kalit qiymatli tugun topiladi va "engKattaKalitniTopish" funktsiyasi yordamida daraxtda eng katta kalit qiymatli tugun topiladi. Agar bu tugunlar mavjud bo'lsa, ularning qiymatlari konsolga chiqariladi. Aks holda, daraxtning bo'shligi haqidagi xabar konsolga chiqariladi.
Foydalanilgan adabiyotlar
https://www.prepbytes.com/blog/tree/data-structures-in-c-trees-graph-3/
https://www.softwaretestinghelp.com/trees-in-cpp/
https://betterprogramming.pub/a-look-at-the-tree-data-structure-in-c-49a33bc841eb
https://www.digitalocean.com/community/tutorials/trie-data-structure-in-c-plus-plus
https://www.cs.cmu.edu/~clo/www/CMU/DataStructures/Lessons/lesson4_1.htm
https://www.geeksforgeeks.org/introduction-to-tree-data-structure-and-algorithm-tutorials/
|
