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.
Ularnibosibo'tishningfaqatbittamantiqiyusulibo'lganchiziqlima'lumotlartuzil
malaridan (Array, bog'langanro'yxat, navbat, stekvaboshqalar) farqlio'laroq,
daraxtlarturliyo'llarbilano'tishimumkin. Quyida daraxtlardan o'tishning
odatda
foydalaniladigan usullari keltirilgan.
Chuqurlikdagi birinchi o'tish joylari:
(a) Inorder (chap, ildiz, o'ng): 4 2 5 1 3
(b) Oldindan buyurtma berish (Ildiz, chap, o'ng): 1 2 4 5 3
(c) 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.
