Berilganlarning chiziqsiz strukturalari. Daraxtlar.
Reja:
1.
Daraxt tushunchasi.
2.
Daraxt turlari.
3.
Binar daraxtni to’liq aylanib chiqish algoritmlari.
Ma’ruzachi: M.Tojiyev
Chiziqli
ma'lumotlar
tuzilmasida
ma'lumotlar
ketma-ket
tartibda
joylashadi.
Chiziqli
bo'lmagan
ma'lumotlar strukturasida ma’lumotlar
tasodifiy tartibda joylashadi. Daraxt bu
juda
ko’p
foydalaniladigan
tuzilma
hisoblanadi.
Dasturiy
ilovalarda
qo'llaniladigan
mashhur
chiziqli
bo'lmagan ma'lumotlar strukturasidir.
1.Daraxt tushunchasi:
Daraxt - bu ma'lumotlarni ierarxik tuzilishga tartibga
soluvchi chiziqli bo'lmagan ma'lumotlar strukturasi
va bu esa uning rekursiv ta’rifidir.
Kirishning
nol
darajasiga
ega
boʻlgan uch
daraxtning ildizi, chiqish nol darajaga ega tugunlar
esa barglar deb nomlanadi.
Daraxtlar ko'pincha ma'lumotlar o'rtasidagi ierarxik
munosabatlarni ifodalash uchun ishlatiladi, masalan,
kompyuterdagi fayl tizimi.
Daraxt ma'lumotlar tuzilmasida, agar bizda N sonli tugunlar
bo'lsa, u holda biz eng ko'p N-1 havolaga ega bo'lishimiz
mumkin.
Yoʻnaltirilgan (oriyentirlangan) daraxt - bu faqat bitta
vertical kirish nol darajasiga ega boʻlgan (boshqa yoylar
unga olib kelmaydigan), boshqa uchlarning kirish darajasi 1
boʻlgan siklik orgraf (sikllarni oʻz ichiga olmaydigan
yoʻnaltirilgan graf).
|