Ekiston axborot texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti

O’ZBEKISTON AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

MTA fanidan

4 - laboratoriya ishi

Bajardi: 411-20 guruh

talabasi G’anijonov S.

Tekshirdi: Xojiyeva N.

Mavzu: DARAXTSIMON MA’LUMOTLAR TUZILMASINI TADQIQ QILISH

Ishdan maqsad: Talabalar daraxtsimon tuzilmalar, binar daraxtlarni e’lon qilish, uning ustida amallar bajarish algoritmlarini tadqiq qilishlari va o’rganishlari kerak, bu algoritmlarning dasturiy realizatsiyasini amalga oshirish ko’nikmasiga ega bo’lishlari kerak.

Ish tartibi:

• 
  Tajriba ishi nazariy ma’lumotlarini o’rganish;
  
• 
  Berilgan topshiriqning algoritmini ishlab chiqish;
  
• 
  C++ dasturlash muhitida dasturni yaratish;
  
• 
  Natijalarni tekshirish;
  
• 
  Hisobotni tayyorlash va topshirish.
  

6. 
   variant.
   

Daraxt tugunlari haqiqiy sonlar bo’lsin. Yozuvi berilgan kalit qiymatidan kichik bo’lgan daraxt tugunlarini o’chiruvchi dastur tuzing.

Yechish:

1. 
   Avval foydalanuvchi tomonidan binar daraxt ko’rinishida ma’lumotlar olamiz. 2
   
2. 
   So’ngra ixtiyoriy kalit qiymatidan kichik bo’lgan daraxt tugunlarini o’chiramiz. Aytaylik foydalanuvchi tomonidan quyidagicha ma’lumot kiritilsin:
   

20, 8, 22, 4, 12, 10, 14 ; daraxt ko’rinishida esa quyidagi rasmdagidek:

Berilgan kalit qiymatdan kichik daraxt tugunlarini o’chirish kerak!

Aytaylik kalit qiymati 3 ga teng bo’lsin, ya’ni 3 dan kichik barcha daraxt tugunlari o’chirilsin.

Dastur kodi:

#include

using namespace std;

struct Node

{ int key;

struct Node* left, *right; };

void printLevels(Node* root, int low) {

queue Q;

Node *marker = new Node;

int level = 1;

Q.push(root);

Q.push(marker);

while (Q.empty() == false) {

Node *n = Q.front();

Q.pop();

if (n == marker) {

cout << endl;

level++;

if (Q.empty() == true) break;

Q.push(marker); continue; }

if (level >= low)

cout << n->key << " ";

if (n->left != NULL) Q.push(n->left);

if (n->right != NULL) Q.push(n->right); } }

Node* newNode(int key) {

Node* temp = new Node;

temp->key = key;

temp->left = temp->right = NULL;

return (temp); }

int main() {

struct Node *root = newNode(20);

root->left = newNode(8);

root->right = newNode(22);

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

root->left->right = newNode(12);

root->left->right->left = newNode(10);

root->left->right->right = newNode(14);

printLevels(root, 3);

return 0; }