Laboratoriya ishi 23

LABORATORIYA ISHI - 23

Mavzu: Muvozanatlangan binar daraxtlar.
Ishdan maqsad. Ushbu laboratoriya ishida talabalar binar daraxtlar tushunchasi bilan tanishib chiqishi va inorder preorder hamda postorder ko’rinishdagi tartiblar bilan tanishib chiqishlari kerak

Qo’yilgan masala. Talabalar topshiriq variantiga mos ravishda binar darxtlar ustida berilgan amallar bilan ishlash 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.
  

Ularni bosib o'tishning faqat bitta mantiqiy usuli bo'lgan chiziqli ma'lumotlar tuzilmalaridan (Array,bog'langan ro'yxat, navbat stek va boshqalar) farqli o'laroq, daraxtlar turli yo'llar bilan o'tishi mumkin.Quyida daraxtlardan o'tishning odatda foydalaniladigan usullari keltirilgan.

Chuqurlikdagi birinchi o'tish joylari:

1. 
   Inorder (chap, ildiz, o'ng): 4 2 5 1 3
   
2. 
   Oldindan buyurtma berish (Ildiz, chap, o'ng): 1 2 4 5 3
   
3. 
   Postorder (chap, o'ng, ildiz): 4 5 2 3 1
   

Birinchi yoki darajadagi buyurtmaning kengligi: 1 2 3 4 5

Inorder-dan foydalanish

Ikkilik qidiruv daraxtlari (BST) bo'lsa, Inorder traversal tugunlarni kamaymaydigan tartibda beradi. BST tugunlarini ko'payib bormaydigan tartibda olish uchun Inorder traversal s teskari yo'naltirilgan Inorder traversalining o'zgarishi mumkin.

Masalan: Yuqorida keltirilgan rasm uchun inorder o'tish 4 2 5 1 3 ga teng.
Preorder-dan foydalanish

Daraxtning nusxasini yaratish uchun oldindan buyurtma o'tish. Oldindan buyurtma o'tish, shuningdek, ifoda daraxtining prefiksini olish uchun ishlatiladi. Iltimos, prefiks iboralari nima uchun foydali ekanligini bilish uchun http://en.wikipedia.org/wiki/Polish_notation ga qarang.

Masalan: Yuqoridagi rasm uchun oldindan buyurtma o'tish 1 2 4 5 3.

Postorder dan foydalanish

Postorder traversal daraxtni yo'q qilish uchun ishlatiladi. Tafsilotlar uchun daraxtni yo'q qilish uchun savolga qarang. Postorder traversal, shuningdek, ifoda daraxtining postfix ifodasini olish uchun foydalidir. Iltimos, postfiks ifodasini ishlatish uchun http://en.wikipedia.org/wiki/Reverse_Polish_notation ga qarang.

Misol: Yuqoridagi rasm uchun postorder o'tish 4 5 2 3 1 ga teng.

Labarotoriya ishlari uchun topshiriqlar.

1. 
   Binar daraxt tuzilmasidan foydalanib yuqoridagi chizmani dasturiy kodi tuzilsin va ekranga inorder, preorder, postorder tartibida chiqarilsin.
   

2. 
   Binar daraxt tuzilmasidan foydalanib yuqoridagi chizmani dasturiy kodi tuzilsin va ekranga inorder, preorder, postorder tartibida chiqarilsin.
   

3. 
   Binar daraxt tuzilmasidan foydalanib yuqoridagi chizmani dasturiy kodi tuzilsin va ekranga inorder, preorder, postorder tartibida chiqarilsin.
   

4. 
   Binar daraxt tuzilmasidan foydalanib yuqoridagi chizmani dasturiy kodi tuzilsin va ekranga inorder, preorder, postorder tartibida chiqarilsin.
   

5. 
   Binar daraxt tuzilmasidan foydalanib yuqoridagi chizmani dasturiy kodi tuzilsin va ekranga inorder, preorder, postorder tartibida chiqarilsin.
   

6. 
   Binar daraxt tuzilmasidan foydalanib yuqoridagi chizmani dasturiy kodi tuzilsin va ekranga inorder, preorder, postorder tartibida chiqarilsin.
   

7. 
   Binar daraxt tuzilmasidan foydalanib yuqoridagi chizmani dasturiy kodi tuzilsin va ekranga inorder, preorder, postorder tartibida chiqarilsin.
   

8. 
   Binar daraxt tuzilmasidan foydalanib yuqoridagi chizmani dasturiy kodi tuzilsin va ekranga inorder, preorder, postorder tartibida chiqarilsin.
   

9. 
   Binar daraxt tuzilmasidan foydalanib yuqoridagi chizmani dasturiy kodi tuzilsin va ekranga inorder, preorder, postorder tartibida chiqarilsin.
   

10. 
    Binar daraxt tuzilmasidan foydalanib yuqoridagi chizmani dasturiy kodi tuzilsin va ekranga inorder, preorder, postorder tartibida chiqarilsin.
    

Nazorat savollar:

1. 
   Inorder-dan foydalanish usullarini ko`rsating?
   
2. 
   Preorder va postorder o`rtasida qanday farq bor?
   
3. 
   Oldindan buyurtma o'tish, shuningdek, ifoda daraxtining prefiksini olish uchun qanday funksiya ishlatiladi?
   
4. 
   Qaysi travelsal daraxtni yo`q qilish uchun ishlatiladi?