Daraxtlar, ikki tomonlama daraxtlar. Ikkilik daraxtlarning vakili. Ikkilik daraxtlarning o'tishi

Загружено в:

12.08.2023

Скачано:

0

Размер:

1497.8203125 KB

Скачать

Daraxtlar, ikki tomonlama daraxtlar. Ikkilik daraxtlarning vakili. Ikkilik
daraxtlarning o'tishi
M U N D A R I J A

Kirish ...............................................................................................................3
I. DARAXT - TERMINOLOGIYASI ...............................................................5
II. DARAXT VAKIL ......................................................................................12
III. IKKILIK DARAXTLAR MA’LUMOTLAR TUZILISHI ......................14
IV. IKKILIK DARAXTLAR VAKIL .............................................................18
V. IKKILIK DARAXTLARNING O’TISH ....................................................19
VI. IPLI IKKILIK DARAXTLAR .................................................................22
VII. IKKILIK QIDIRUV DARAXT ...............................................................24
Xulosa .............................................................................................................28
Foydalanilgan adabiyotlar ..............................................................................30
1

Kirish
Algoritm- bu aniq hisoblashlarni bajaruvchi protsedura bo’lib unga kirish qismida
kattalik yoki kattaliklar berilib chiqishda natijaviy kattalik yoki kattaliklar olinadi.
Demak algoritm hisoblovchi qadamlardan tashkil topgan bo'lib,dastlabki
qiymatlarga ko‘ra natijaviy kattaliklar qiymatini beradi. Daraxt tushunchasi.
Daraxtning kompyuter xotirasida tasvirlanishi. Daraxt - bu chiziqli bo‘lmagan
bog‘lamli ma‘lumotlar tuzilmasidir. Ikkilik qidiruv daraxti - bu ildiz otgan ikkilik
daraxtichki tugunlari har birida kalitni (va ixtiyoriy ravishda bog'liq qiymatni)
saqlaydi va har birida odatda belgilangan ikkita taniqli pastki daraxtlar mavjud
chap va to'g'ri. Daraxt qo'shimcha ravishda qoniqtiradi ikkilik qidirish xususiyati:
har bir tugundagi kalit chap pastki daraxtda saqlangan har qanday tugmachadan
kattaroq yoki teng, o'ng pastki daraxtda saqlangan har qanday tugmachadan
kichik yoki teng.Daraxtning barglarida (yakuniy tugunlarida) hech qanday kalit
yo'q va ularni bir-biridan ajratib turadigan tuzilishga ega emas. Ko'pincha, har bir
tugun tomonidan ko'rsatilgan ma'lumot bitta ma'lumot elementi emas, balki
yozuvdir. Biroq, ketma-ketlik maqsadida tugunlar o'zlarining tegishli
yozuvlarining biron bir qismiga emas, balki ularning kalitlariga qarab
taqqoslanadi. Ikkilik qidiruv daraxtlarining boshqa ma'lumotlar tuzilmalaridan
ustunligi shu bilan bog'liqdir algoritmlarni saralash va qidirish algoritmlari kabi
tartibda o'tish juda samarali bo'lishi mumkin. A ikkilik daraxt a daraxt
ma'lumotlari tuzilishi unda har bir tugun ko'pi bilan ikkitadan bolalar deb
nomlangan chap bola va o'ng bola . A rekursiv ta'rif faqat foydalanish to'plam
nazariyasi tushunchalar shundan iboratki (bo'shbo'lmagan) ikkilik daraxt a panjara
(L,S,R) qaerda L va R ikkilik daraxtlar yoki bo'sh to'plam va S a singleton
to'plami ildizni o'z ichiga olgan. Ba'zi mualliflar ikkitomonlama daraxtga ham
bo'sh to'plam bo'lishiga ruxsat berishadi. A dan grafik nazariyasi bu erda
aniqlangan istiqbolli, binar (va K-ary) daraxtlar aslida daraxtzorlar. Ikkilik
daraxtni shunday deb ham atash mumkin ikki tomonlama daraxtzor. Bu juda
qadimgi dasturlash kitoblarida uchraydigan atama, ilgari zamonaviy informatika
2

terminologiyasi ustun kelgan. Ikkilik daraxtni an deb talqin qilish ham
mumkin yo'naltirilmagan, a o'rniga yo'naltirilgan grafik,bu holda ikkilik daraxt
an buyurdi, ildiz otgan daraxt. Ba'zi mualliflar foydalanadilar ikkilik
daraxt o'rniga ikkilik daraxt daraxtning ildiz otganligini ta'kidlash uchun ,lekin
yuqorida ta'riflanganidek, ikkilik daraxt har doim ildiz otadi. Ikkilik daraxt - bu
buyurtma qilingan alohida holat K-ary daraxti, qayerda k 2. Matematikada nima
deyiladi ikkilik daraxt muallifdan muallifga sezilarli darajada farq qilishi mumkin.
Ba'zilar odatda kompyuter fanida ishlatiladigan ta'rifdan foydalanadilar,ammo
boshqalar buni aniq ikki bolali har bir yaproqsiz deb belgilaydilar va bolalarga
ham (chapda / o'ngda) buyurtma berishlari shart emas.Hisoblashda ikkilik
daraxtlar ikki xil usulda ishlatiladi:
 Birinchidan, har bir tugun bilan bog'liq ba'zi bir qiymat yoki yorliqlarga
asoslangan tugunlarga kirish vositasi sifatida.Amalga oshirish uchun shu tarzda
belgilangan ikkilik daraxtlar ishlatiladi ikkilik qidiruv daraxtlari va ikkilik
uyumlar va samaradorlik uchun ishlatiladi qidirish va tartiblash. Ildiz bo'lmagan
tugunlarni chap yoki o'ng bola deb belgilash, hatto bitta bola bo'lsa ham, ushbu
dasturlarning ayrimlarida, xususan,ikkilik qidiruv daraxtlarida muhim ahamiyatga
ega. Biroq, daraxtga ma'lum tugunlarni joylashtirish kontseptual ma'lumotlarning
bir qismi emas. Masalan, oddiy ikkilik qidiruv daraxtida tugunlarni joylashtirish
deyarli ularning qo'shilish tartibiga bog'liq va ularni qayta tartibga solish mumkin
(masalan muvozanatlash) ma'nosini o'zgartirmasdan.
 Ikkinchidan, ma'lumotlarning tegishli bifurkatsion tuzilishga ega vakili sifatida.
Bunday hollarda boshqa tugunlar ostidagi va / yoki chapga yoki o'ngga
tugunlarning alohida joylashuvi ma'lumotlarning bir qismidir (ya'ni uni
o'zgartirish ma'noni o'zgartirishi mumkin). Umumiy misollar Huffman
kodlash va kladogrammalar. Hujjatlarning har kungi boblarga, bo'limlarga,
xatboshilarga va boshqalarga bo'linishi binary daraxtlar o'rniga n-ary bilan
o'xshash misoldir.
3

I. Daraxt - terminologiyasi
Chiziqli ma'lumotlar strukturasida ma'lumotlar ketma-ketlikda va chiziqli bo'lmagan
ma'lumotlar tarkibida ma'lumotlar tasodifiy tartibda joylashtirilgan. Daraxt - bu juda
keng qo'llaniladigan, chiziqli bo'lmagan ma'lumotlar tuzilishi. Daraxt ma'lumotlari
tuzilishini quyidagicha aniqlash mumkin.
Daraxt - bu ma'lumotlarning ierarxik tarkibida tartibga soluvchi chiziqli bo'lmagan
strukturasi va bu rekursiv ta'rif. Daraxtlar ma'lumotlari tuzilishi - bu ierarxik
tuzilishda rekursiv ravishda tashkil etilgan ma'lumotlar to'plami (Tugun)
Daraxtlar ma'lumotlari tarkibida har bir alohida element tugun deb nomlanadi. Daraxt
ma'lumotlari tarkibidagi tugun ushbu elementning haqiqiy ma'lumotlarini saqlaydi va
ierarxik tuzilishdagi keyingi elementga bog'lanadi.
Daraxt ma'lumotlari tarkibida, agar bizda N tugunlari bo'lsa, unda biz maksimal N-1
sonli qirralarga ega bo'lishimiz mumkin.
Terminologiya
Daraxt ma'lumotlari tarkibida biz quyidagi terminologiyadan foydalanamiz ...
1. Ildiz tugun
Daraxt ma'lumotlari tarkibida birinchi tuguni ildiz tuguni deb nomlanadi. Har bir
daraxtda ildiz tuguni bo'lishi kerak. Ildiz tuguni daraxt ma'lumotlari tuzilishining
kelib chiqishi deb ayta olamiz. Har qanday daraxtda faqat bitta ildiz tuguni bo'lishi
kerak. Bizda hech qachon daraxtda bir nechta ildiz tugunlari bo'lmaydi.
4

2. Qirra
Daraxt ma'lumotlari tuzilmasida har qanday ikkita tugun orasidagi bog'lanish aloqasi
qirra deb nomlanadi. "N" tugunli daraxtda maksimal "N-1" qirralar bo'ladi.
3. Ota-ona
Daraxt ma'lumotlari tuzilmasida har qanday tugunning o'tmishi bo'lgan tugun ota-
ona tugun deb nomlanadi. Oddiy so'zlar bilan aytganda, undan boshqa har qanday
tugunga qadar shoxga ega bo'lgan tugun ota tugun deb ataladi. Ota-ona tugunini
"bolasi / bolalari bo'lgan tugun" deb ham aniqlash mumkin.
5

4. Bola
Daraxt ma'lumotlari tuzilmasida har qanday tugunning nasli bo'lgan tugun bola
tuguni deb nomlanadi. Oddiy so'zlar bilan aytganda, ota-ona tugunidan bog'langan
tugun bola tuguni deb nomlanadi. Daraxtda har qanday ota tugunda istalgan sonli
tugun bo'lishi mumkin. Daraxtda ildizdan tashqari barcha tugunlar bolalar tugunlari
hisoblanadi.
5. Birodarlar
Daraxt ma'lumotlari tarkibida bitta Ota-onaga tegishli tugunlar birodarlar deb
nomlanadi. Oddiy so'zlar bilan aytganda, bir xil ota-onaga ega tugunlar Birodar
tugunlari deb ataladi.
6

6. Barg
Daraxt ma'lumotlari tarkibida farzandi bo'lmagan tugun barg tuguni deb nomlanadi.
Oddiy so'zlar bilan aytganda, barg - bu farzandsiz tugun. Daraxt ma'lumotlari
tarkibida barg tugunlari tashqi tugunlar deb ham ataladi. Tashqi tugun ham farzandi
bo'lmagan tugundir. Daraxtda barg tuguni "Terminal" tuguni deb ham ataladi.
7. Ichki tugunlar
Daraxt ma'lumotlari tuzilmasida bitta bolaga ega bo'lgan tugun ichki tugun deb
nomlanadi. Oddiy so'zlar bilan aytganda, ichki tugun - bu kamida bitta bola bo'lgan
tugun. Daraxt ma'lumotlari tarkibida barg tugunlaridan tashqari boshqa tugunlar Ichki
tugunlar deb nomlanadi. Ildiz tuguni, shuningdek, daraxtda bir nechta tugun bo'lsa,
ichki tugun deyiladi. Ichki tugunlar "Terminal bo'lmagan" tugunlar deb ham ataladi.
7

8. Darajasi
Daraxt ma'lumotlari tarkibida tugunning barcha bolalar soni ushbu tugunning
darajasi deb nomlanadi. Oddiy so'zlar bilan aytganda, tugunning darajasi - bu
bolalarning umumiy soni. Daraxtdagi barcha tugunlar orasidagi tugunning eng yuqori
darajasi "Daraxt darajasi" deb nomlanadi.
9. Daraja
Daraxt ma'lumotlari tuzilmasida ildiz tuguni 0 darajasida, ildiz tugunining bolalari 1
darajada va 1 darajadagi tugunlarning bolalari 2 sathda va boshqalar deyiladi ...
Oddiy qilib aytganda so'zlar, daraxtda yuqoridan pastgacha har bir qadam daraja deb
nomlanadi va darajalar soni '0' dan boshlanadi va har bir sathda bittadan ko'paytiriladi
(Qadam).
8

10. Balandligi
Daraxt ma'lumotlari tuzilmasida eng uzun yo'lda barg tugunidan ma'lum tugunga
qadar qirralarning umumiy soni ushbu tugunning balandligi deb nomlanadi.
Daraxtda ildiz tugunining balandligi daraxtning balandligi deb aytiladi. Daraxtda
barcha barg tugunlarining balandligi '0' dir.
11. Chuqurlik
Daraxt ma'lumotlari tarkibida ildiz tugunidan ma'lum tugunga qadar qirralarning
umumiy soni ushbu tugunning chuqurlik deb nomlanadi. Daraxtda eng uzun yo'lda
ildiz tugunidan barg tugunigacha bo'lgan qirralarning umumiy soni daraxt chuqurligi
deb aytiladi. Oddiy so'zlar bilan aytganda, daraxtdagi har qanday barg tugunining eng
yuqori chuqurligi shu daraxtning chuqurligi deb aytiladi. Daraxtda ildiz tugunining
chuqurligi '0' dir.
9

12. Yo'l
Daraxt ma'lumotlari tarkibida tugunlar va qirralarning bir tugundan ikkinchi tugunga
ketma-ketligi shu ikki tugun o'rtasida yo’l deb nomlanadi. Yo'l uzunligi - bu yo'ldagi
tugunlarning umumiy soni. Quyidagi misolda A - B - E - J yo'lining uzunligi 4 ga
teng.
13. Kichik daraxt
Daraxt ma'lumotlari tarkibida tugundan har bir bola rekursiv ravishda kichik daraxt
hosil qiladi. Har bir bola tuguni ota tugunida kichik daraxt hosil qiladi.
daraxt qirralar bilan bog'langan tugunlarni ifodalaydi. Ikkilik daraxt yoki ikkilik
qidiruv daraxtini alohida muhokama qilamiz.
10

II. Daraxt vakillari
Daraxt vakillari tuzilishi ikki usulda ifodalanishi mumkin. Ushbu usullar
quyidagicha.
1. Ro'yxat vakili
2. Chap bola - o'ng birodarlik vakili
Quyidagi daraxtni ko'rib chiqing
1. Ro'yxat vakili
Ushbu vakillikda biz ikkita tugun turini ishlatamiz, ulardan biri tugunni "ma'lumotlar
tuguni" deb nomlangan vakili bilan ifodalash uchun, ikkinchisi esa faqat "mos
yozuvlar tuguni" deb nomlangan havolalarni ko'rsatish uchun. Biz daraxtdagi ildiz
tugunidan "ma'lumotlar tuguni" bilan boshlaymiz. Keyin u "tugun" orqali ichki
11

tugunga bog'langan bo'lib, u boshqa har qanday tugunga to'g'ridan-to'g'ri bog'lanadi.
Ushbu jarayon daraxtdagi barcha tugunlar uchun takrorlanadi.
Yuqoridagi misol daraxtini Ro'yxat vakili yordamida quyidagicha ko'rsatish mumkin.
2. Chap bola - o'ng birodarlik vakili
Ushbu vakillikda biz uchta maydondan iborat bo'lgan bitta tugunli ro'yxatni
ishlatamiz, ya'ni Ma'lumotlar maydoni, Chap bola yo'naltiruvchi maydoni va O'ng
aka-ukaning ma'lumot maydoni. Ma'lumotlar maydonida tugunning haqiqiy qiymati
saqlanadi, chap yo'nalish maydonida chap bolaning manzili va o'ng ma'lumot
maydonida birodarning o'ng tugunining manzili saqlanadi. Ushbu tugunning grafik
vakili quyidagicha.
Ma’lumotlar
Chap bola O’ng qardosh
Ushbu vakolatxonada har bir tugunning ma'lumotlar maydoni ushbu tugunning
haqiqiy qiymatini saqlaydi. Agar bu tugun bolani tashlab ketgan bo'lsa, chap
yo'nalish maydonida ushbu chap tugunning manzili saqlanadi, aks holda NULL
saqlanadi. Agar ushbu tugun birodarga to'g'ri kelsa, u holda o'ng yo'nalish maydonida
o'ng birodar tugunning manzili saqlanadi, aks holda NULL saqlanadi.
Yuqoridagi misol daraxtini chap bola - o'ng birodarlik vakili yordamida quyidagicha
ko'rsatish mumkin ...
12

III. Ikkilik daraxtlar ma'lumotlar tuzilishi
Oddiy daraxtda har bir tugunda istalgan sonli bola bo'lishi mumkin. Ikkilik daraxt -
bu har bir tugunda maksimal 2 bolaga ega bo'lishi mumkin bo'lgan daraxtlar
ma'lumotlari strukturasining maxsus turi. Ulardan biri chap bola, ikkinchisi esa o'ng
bola sifatida tanilgan.Har bir tugunda maksimal ikkitadan bola bo'lishi mumkin
bo'lgan daraxtga Ikkilik daraxt deyiladi. Ikkilik daraxtda har bir tugunda 0 bola yoki
1 bola yoki 2 bola bo'lishi mumkin, lekin ikkitadan ko'p bo'lmagan bola.
Ikkilik daraxtlarning har xil turlari mavjud va ular. . .
1.Qat'iy ikkilikli daraxt
Ikkilik daraxtda har bir tugun maksimal ko'pi bilan ikkita bolani tug'ishi mumkin.
Ammo qat'iy ravishda ikkitomonlama daraxtda har bir tugunning to'liq ikkita bolasi
13

bo'lishi kerak yoki yo'q. Bu shuni anglatadiki, har bir ichki tugunda to'liq ikkita bola
bo'lishi kerak.Qat'iy ikkilikli daraxtquyidagicha aniqlash mumkin ...
Har bir tugunda ikkita yoki nol sonli bolaga ega bo'lgan ikkitomonlama daraxtga
"Qat'iy ikkilikli daraxt" deyiladi . Qat'iy ikkilikli daraxt, shuningdek To'liq binar
daraxt yoki to'g'ri binar daraxt yoki 2 daraxt deb nomlanadi.
Matematik ifodalarni ifodalash uchun qat'iy ravishda ikkilik daraxt ma'lumotlari
tuzilishi qo'llaniladi.
2.To`liq ikkilik daraxt
Ikkilik daraxtda har bir tugun maksimal ko'pi bilan ikkita bolani tug'ishi mumkin.
Ammo qat'iy ravishda ikkitomonlama daraxtda har bir tugunda to'liq ikkita bola
bo'lishi kerak yoki yo'q va to'liq ikkilik daraxtda barcha tugunlar to'liq ikkita bolaga
ega bo'lishi kerak va to'liq binar daraxtning har darajasida tugunlarning soni ikki
darajali bo'lishi kerak. Masalan, 2-darajada 22 = 4 tugun va 3-darajada 23 = 8 tugun
bo'lishi kerak.Har bir ichki tugunda roppa-rosa ikkita bolaga ega bo'lgan va barcha
14

barg tugunlari bir xil darajada bo'lgan ikkilik daraxtga "To'liq ikkilik daraxt" deyiladi.
To'liq ikkilik daraxtni mukammal ikkilik daraxti deb ham atashadi.
3. Kengaytirilgan ikkilik daraxt
Ikkilik daraxtni kerak bo'lgan joyda mavjud tugunlarga qo'g'irchoq tugunlarini
qo'shish orqali to'liq ikkilik daraxtga aylantirish mumkin.
Ikkilik daraxtga qo'g'irchoq tugunlarini qo'shish natijasida olingan to'liq ikkilik daraxt
kengaytirilgan ikkilik daraxt deb nomlanadi.
Yuqoridagi rasmda oddiy ikkilik daraxt qo'shib to'liq ikkilik daraxtga aylantiriladi
(Pushti rangda).
4. Chala yoki patologik daraxt
Chala yoki patologik daraxt - bu chap yoki o'ngda bitta bolaga ega bo'lgan daraxt.
15

5. Qiyshaygan ikkilik daraxt
Qiyshaygan ikkilik daraxt - bu patologik / chala daraxt bo ' lib , unda daraxt chap
tugunlar yoki o ' ng tugunlar tomonidan boshqariladi . Shunday qilib , qiyshiq ikkilik
daraxtning ikki turi mavjud : chap qiyshiq ikkilik daraxt va o ' ng qiyshiq ikkilik daraxt .
6. Muvozanatli ikkilik daraxt
Bu har bir tugun uchun chap va o'ng pastki daraxtlar orasidagi farq 0 yoki 1 ga teng
bo'lgan ikkilik daraxt turidir.
16

IV. Ikkilik daraxt vakili
Ikkilik daraxt ma'lumotlari tuzilishi ikkita usul yordamida namoyish etiladi. Ushbu
usullar quyidagicha.
1. Massiv vakili
2. Bog'langan ro'yxat vakili
Quyidagi ikkilik daraxtni ko'rib chiqing.
1.Ikkilik daraxtlarning massivli vakil
Ikkilik daraxtni massivda aks ettirishda biz ikkilik daraxtni aks ettirish uchun bir
o'lchovli massivdan (1-D qator) foydalanamiz. Ikkilik daraxtning yuqoridagi misolini
ko'rib chiqing va u quyidagicha ifodalanadi ...
17

"N" chuqurlikdagi ikkilik daraxtni massiv vakil yordamida ko'rsatish uchun bizga
maksimal 2n + 1 o'lchamdagi bitta o'lchovli qator kerak.
2. Ikkilik daraxtlarning bog'langan ro'yxatli vakil
Ikkilik daraxtni ko'rsatish uchun biz ikkita bog'langan ro'yxatdan foydalanamiz. Ikki
tomonlama bog'langan ro'yxatda har bir tugun uchta maydondan iborat. Birinchi chap
bolaning manzilini saqlash maydoni, ikkinchisi haqiqiy ma'lumotlarni saqlash uchun,
uchinchisi esa o'ng manzilini saqlash uchun maydon.
Ushbu bog'langan ro'yxat vakilligida tugun quyidagi tuzilishga ega.
Bog'langan ro'yxat vakili yordamida namoyish etilgan ikkitomonlama daraxtning
yuqoridagi misoli quyidagicha ko'rsatilgan ...
V. Ikkilik daraxtlarning o'tish
18

Ikkilik daraxtni ko'rsatishni xohlaganimizda, biz ushbu ikkilik daraxtning barcha
tugunlari ko'rsatilishi kerak bo'lgan tartibni bajarishimiz kerak. Har qanday ikkilik
daraxtda tugunlarning tartibini ko'rsatish o`tish usulga bog'liq.
Ikki tomonlama o'tishning uch xil turi mavjud.
1. Buyurtma bo`ylab o`tish
2. Oldindan buyurtma bo`yicha o`tish
3. Keying buyurtma bo'yicha o`tish
Quyidagi ikkilik daraxtni tekshiring ...
1. Buyurtma bo`ylab o`tish (chap bola - ildiz – o`ng bola)
Tartibda o'tish (chap bola- ildiz – o`ng bola).
"Buyurtma bo`ylab" o'tishida ildiz tuguniga chap bola va o'ng bola o'rtasida tashrif
buyuriladi. Ushbu o'tishda biz avval chap tugunga, so'ngra ildiz tuguniga, so'ngra
o'ng tugunga tashrif buyuramiz. Ushbu tartibda o'tish daraxtdagi barcha kichik
daraxtlarning har bir ildiz tuguniga taalluqlidir. Bu daraxtdagi barcha tugunlar uchun
rekursiv ravishda amalga oshiriladi.
Yuqoridagi ikkilik daraxt misolida biz avval "A" ildiz tugunining chap bolasini
ko'rishga harakat qilamiz, ammo A ning chap bolasi "B" chap subtree uchun ildiz
tugunidir. shuning uchun biz uning (B) chap bolasi "D" ga tashrif buyurishga harakat
qilamiz va D yana D, I va J tugunlari bilan subtree uchun ildiz hisoblanadi, shuning
uchun biz uning chap bolasi "I" ga va u eng chap bolasiga tashrif buyurishga harakat
qilamiz. Shunday qilib, avval biz "I" ga tashrif buyurib, uning "D" ildiz tuguniga
boramiz, keyin D.ning o'ng farzandi "J" ga tashrif buyuramiz, shu bilan biz B
19

tugunining chap qismini to'ldirdik, so'ng "B" ga tashrif buyuring va keyingi B ning
o'ng bolasi "F" ga tashrif buyuradi. Shu bilan biz A tugunning chap qismini to'ldirdik,
so'ngra "A" ildiz tuguniga tashrif buyuring. Shu bilan biz A tugunning chap va ildiz
qismlarini to'ldiramiz, so'ng A tugunning o'ng qismiga o'tamiz. A ning o'ng tomonida
yana bitta C ildiz subtree bor, shuning uchun C ning chap bolasiga o'ting va yana u G
ning chap tomoni yo'q, shuning uchun biz "G" ga boramiz, keyin G ning o'ng bolasi
K tashrifiga boradi, u bilan biz C tugunning chap qismini to'ldirdik. Keyin "C" ildiz
tuguniga tashrif buyuring va tashrif buyuring daraxtning eng to'g'ri bolasi bo'lgan "H"
bolasi C. ning o'ng tomoni. Shunday qilib, biz jarayonni to'xtatamiz.
Demak, biz In-Order Traversal yordamida I - D - J - B - F - A - G - K - C - H
tartibida tashrif buyurganmiz. Yuqoridagi ikkitomonlama daraxt misolida tartibda
o'tish I - D - J - B - F - A - G - K - C – H
2. Oldindan buyurtma bo`yicha o`tishda (ildiz – chap bola – o`ng bola)
Oldindan buyurtma o'tishida ildiz tuguniga chap va o'ng tugun tugunlaridan oldin
tashrif buyuriladi. Ushbu o'tishda avval ildiz tuguniga, so'ngra chap bolasiga, keyin
esa o'ng bolasiga tashrif buyuriladi. Ushbu oldindan buyurtma o'tishi daraxtdagi
barcha kichik daraxtlarning har bir ildiz tuguni uchun amal qiladi.
Yuqoridagi ikkitomonlama daraxt misolida biz avval "A" ildiz tuguniga tashrif
buyuramiz, so'ng D va F uchun ildiz bo'lgan chap bolasi "B" ga tashrif buyuramiz,
shuning uchun biz B ning chap bolasi "D" ga va yana D I uchun ildiz hisoblanadi. va
J. Shunday qilib, biz D ning chap bolasi bo'lgan "Men" ga, ya'ni eng chap bolaga
tashrif buyuramiz. Shunday qilib, biz D ning o'ng bolasi "J" ni ziyorat qilish uchun
boramiz. Shu bilan biz D tugunining ildiz, chap va o'ng qismlarini va B tugunning
chap qismlarini to'ldirdik. Keyin B ning o'ng bolasi "F" ga tashrif buyuring. Shu bilan
biz A tugunning ildiz va chap qismlarini to'ldirdik, shuning uchun biz G va H uchun
ildiz tuguni bo'lgan A ning o'ng bolasi "C" ga boramiz, C ga tashrif buyurganimizdan
keyin uning chap bolasi "G" ga o'tamiz, bu ildiz tugun uchun K. Shunday qilib, biz G
ning chap tomoniga boramiz, lekin u chap bolaga ega emas, shuning uchun biz G
ning o'ng bolasi "K" tomon boramiz. Shu bilan biz C tugunining ildizi va chap
20

qismlarini to'ldirdik. Keyingi daraxtning eng o'ng bolasi bo'lgan S ning o'ng bolasi
"H" ga tashrif buyuring. Shunday qilib, biz jarayonni to'xtatamiz.
Bu shuni anglatadiki, biz A-B-D-I-J-F-C-G-K-H tartibida oldindan buyurtma o`tish
yordamida tashrif buyurdik. Yuqoridagi misol uchun "Oldindan buyurtma berish"
"Ikki tomonlama daraxt" A - B - D - I - J - F - C - G - K - H
3.Keying buyurtma o`tish (chap bola – o`ng bola - ildiz)
Keying buyuurtma o`tishda, ildiz tuguniga chap va o'ng boladan keyin tashrif
buyuriladi. Ushbu harakatlanishda avval chap tugunga, so'ng uning o'ng bolasiga,
so'ngra ildiz tuguniga tashrif buyuriladi. Bu rekursiv ravishda eng to'g'ri tugun tashrif
buyurguncha amalga oshiriladi. Bu erda biz I - J - D - F - B - K - G - H - C - A
tartibida keying buyurtma o`tish yordamida tashrif buyurdik. Yuqoridagi misol uchun
"Buyurtmadan keyingi o'tish" ikkilik daraxti I - J - D - F - B - K - G - H - C – A.
VI. Ipli ikkilik daraxtlar
Ikkilik daraxt massivni yoki bog'langan ro'yxatni namoyish qilish orqali namoyish
etilishi mumkin. Ikkilik daraxt bog'langan ro'yxat vakili yordamida ifodalanganida,
tugunchaning bolasi bo'lmagan mos yozuvlar qismi NULL ko'rsatkichi bilan
to'ldiriladi. Har qanday ikkilik daraxt bilan bog'langan ro'yxat vakolatxonasida
haqiqiy ko'rsatgichlarga qaraganda bir qator NULL ko'rsatkichlari mavjud. Odatda,
har qanday ikkilik daraxt bilan bog'langan ro'yxat ko'rsatuvida, agar mos yozuvlar
maydonlarining 2N soni bo'lsa, u holda N + 1 mos yozuvlar maydonlari NULL bilan
to'ldiriladi (N + 1, 2N dan NULL). Ushbu NULL ko'rsatkichi hech qanday rol
o'ynamaydi, faqat havola yo'qligini ko'rsatadi (bola yo'q).
J. Perlis va C. Torntonlar "Ipli ikkilik daraxt" deb nomlangan yangi binar daraxtni
taklif qildilar, bu uning o'tish jarayonini yaxshilash uchun NULL ko'rsatgichlaridan
foydalanadi. Ikki tomonlama daraxtda NULL ko'rsatkichlari daraxtning boshqa
tugunlari havolalari bilan almashtiriladi. Ushbu qo'shimcha ma'lumot havolalar deb
nomlanadi.
Ipli Ikkilik Daraxt ham ikkitomonlama daraxt bo'lib, unda NULL (bog'langan ro'yxat
vakolatxonasida) bo'lgan barcha chap ko'rsatgichlar tartibda oldingisiga ishora qiladi
21

va NULL (bog'langan ro'yxatdagi vakolatxonada) bo'lgan barcha o'ng ko'rsatgichlar
uning ichkarisiga ishora qiladi. buyurtma vorisi.
Agar tartibda oldingi yoki tartibli voris bo'lmasa, u ildiz tuguniga ishora qiladi.
Quyidagi ikkilik daraxtni ko'rib chiqing ...
Yuqoridagi misolni ikkitomonlama daraxtni ipli ikkilik daraxtga aylantirish uchun
avval ushbu daraxtning tartibli o'tishini toping ...
Yuqoridagi ikkitomonlama daraxtni tartibda kesib o'tish H - D - I - B - E - A - F - J -
C - G Yuqoridagi ikkilik daraxtni bog'langan ro'yxat vakili yordamida
ifodalaganimizda, H, I, E, F, J va G tugmalar tugmachalari NULL. Ushbu NULL
navbati bilan tartibda oldingisining manzili bilan almashtiriladi (I - D, E - B, F - A, J
- F va G - C), lekin bu erda H tugunida tartibli oldingisi yo'q, shuning uchun u A
tugun tuguniga ishora qiladi va H, I, E, J va G tugunlari o'ng tugmachalari NULL.
Ushbu NULL ko'rsatkichlari navbati bilan uning tartibidagi vorisning manzili bilan
almashtiriladi (H dan D, I dan B, E dan A va J dan C gacha), lekin bu erda G
tugunida tartibli vorisi yo'q, shuning uchun u ishora qiladi ildiz tuguniga A.
Yuqoridagi misolda ikkilik daraxt quyidagicha ipli ikkilik daraxtga aylantiriladi.
22

Yuqoridagi rasmda iplar nuqta bilan bog'langan holda ko'rsatilgan.
VII. Ikkilik qidiruv daraxti (IQD)
Ikkilik qidiruv daraxti - bu raqamlarning tartiblangan ro'yxatini tezda saqlashga
imkon beradigan ma'lumotlar tuzilishi.
Ikkilik daraxt deb ataladi, chunki har bir daraxt tugunida maksimal ikkitadan bola
bo'ladi. U qidiruv daraxti deb nomlanadi, chunki u O (log (n)) vaqt ichida raqam
mavjudligini qidirish uchun ishlatilishi mumkin.
Ikkilik qidiruv daraxtini oddiy ikkilik daraxtidan ajratib turadigan xususiyatlar:
1. Chap pastki daraxtning barcha tugunlari ildiz tugunidan kam.
2. O'ng pastki daraxtning barcha tugunlari ildiz tugunidan ko'proq.
3. Har bir tugunning ikkala pastki daraxtlari ham IQD hisoblanadi, ya'ni ular
yuqoridagi ikkita xususiyatga ega.
23

Ildizdan kichik bir qiymatga ega bo'lgan o'ng pastki daraxtga ega bo'lgan daraxt, bu
haqiqiy ikkilik qidiruv daraxti emasligini ko'rsatmoqda. O'ngdagi ikkilik daraxt
ikkilik qidiruv daraxti emas, chunki "3" tugunining o'ng pastki daraxtida undan
kichikroq qiymat mavjud. Algoritm IQD xususiyatiga bog'liq bo'lib, agar har bir chap
pastki daraxtda ildiz ostida qiymatlar bo'lsa va har bir o'ng pastki daraxtda ildizdan
yuqori qiymatlar mavjud bo'lsa. Agar qiymat ildizdan past bo'lsa, biz qiymat to'g'ri
pastki daraxtda emasligini aniq aytishimiz mumkin; biz faqat chap pastki daraxtda
qidirishimiz kerak va agar qiymat ildizdan yuqori bo'lsa, biz chap chap daraxtda
qiymat yo'qligini aniq aytishimiz mumkin; biz faqat to'g'ri kichik daraxtda
qidirishimiz kerak.
Keling, buni diagramma bilan tasavvur qilishga harakat qilaylik.
4 topilmadi, shuning uchun 8 ning chap pastki daraxtidan o'ting.
24

4 topilmadi, shuning uchun 3 ning o'ng pastki daraxtidan o'ting.
4 topilmadi, shuning uchun chap 6 ning pastki daraxtidan o'ting .
4 topildi
25

Agar qiymat topilsa, biz qiymatni qaytaramiz, shunda u har bir rekursiya bosqichida
quyidagi rasmda ko'rsatilgandek tarqaladi. Agar sezgan bo'lsangiz, biz to'rt marta
qaytish qidiruviga (struct node *) murojat qildik. Biz yangi tugunni yoki NULL-ni
qaytarganimizda, qiymat qidirish (root) yakuniy natijani qaytarguncha qayta-qayta
qaytariladi.
Agar qiymat biron bir kichik daraxtda topilsa, u ko'paytiriladi, natijada u qaytariladi,
aks holda null qaytariladi. Agar qiymat topilmasa, biz oxir-oqibat NULL bo'lgan barg
tugunining chap yoki o'ng bolasiga etib boramiz va u ko'payadi va qaytariladi.
26

Xulosa
Daraxt - bu chiziqli bo‘lmagan bog‘lamli ma‘lumotlar tuzilmasidir.
Daraxtni tasavvur qilish va elementlarini qayta ishlash algoritmlarini tahlil qilishda
uning chizma shaklidan foydalanish maqsadga muvofiq. Daraxt ma'lumotlari
tarkibida, agar bizda N tugunlari bo'lsa, unda biz maksimal N-1 sonli qirralarga ega
bo'lishimiz mumkin. Agar daraxtni tashkil etuvchi element(tugun)lardan ko`pi bilan
2ta shox chiqsa, yani har bir tugun tuzilmaning ko`pi bilan 2ta tuguni bilan
bog`langan bo`lsa, u holda bunday daraxt binar daraxt deyiladi.Umumiy holda binary
daraxt har bir elementi 4ta maydonga ega yozuv hisoblanadi. Kompyuter xotirasida
esa daraxtlarni bog‘lamli ro‘yxat shaklida tasvirlash ancha qulay. Bu ro‘yxatning
elementlari tugunning qiymati va shoxlanish darajasi sonini saqlovchi axborot
maydoniga hamda shoxlanish darajasiga teng bo‘lgan sondagi ko‘rsatkichlar
maydoniga ega bo‘ladi. Elementning ixtiyoriy ko‘rsatkichi ushbu tugunni o‘zining
o‘g‘il-tugunlariga yo‘naltiradi. Binar (ikkilik) daraxtlar Binar (ikkilik) daraxtning eng
ko‘p ishlatiladigan turlaridan biri binar daraxtdir. Daraxtni kompyuter xotirasida
tasvirlashda har bir element 4 ta maydondan iborat yozuvni hosil qiladi. Bu
maydonlarning qiymati mos ravishda yozuv kaliti, elementdan keyingi chap va o‘ng
elementga ko‘rsatkichlar hamda yozuv qiymatidan iborat. Hisoblashda ikkilik
daraxtlar ikki xil usulda ishlatiladi: Birinchidan, har bir tugun bilan bog'liq ba'zi bir
qiymat yoki yorliqlarga asoslangan tugunlarga kirish vositasi sifatida. Shu tarzda
etiketlangan ikkilik daraxtlar ikkilik qidiruv daraxtlari va ikkilik uyumlarni amalga
oshirish uchun ishlatiladi va samarali qidirish va saralash uchun ishlatiladi.
Ikkilik qidiruv daraxti - bu ildiz otgan ikkilik daraxtichki tugunlari har birida kalitni
(va ixtiyoriy ravishda bog'liq qiymatni) saqlaydi va har birida odatda belgilangan
ikkita taniqli pastki daraxtlar mavjud chap va to'g'ri. Daraxt qo'shimcha ravishda
qoniqtiradi ikkilik qidirish xususiyati: har bir tugundagi kalit chap pastki daraxtda
saqlangan har qanday tugmachadan kattaroq yoki teng, o'ng pastki daraxtda
saqlangan har qanday tugmachadan kichik yoki teng.Daraxtning barglarida (yakuniy
27

tugunlarida) hech qanday kalit yo'q va ularni bir-biridan ajratib turadigan tuzilishga
ega emas. Ko'pincha, har bir tugun tomonidan ko'rsatilgan ma'lumot bitta ma'lumot
elementi emas, balki yozuvdir. Biroq, ketma-ketlik maqsadida tugunlar o'zlarining
tegishli yozuvlarining biron bir qismiga emas, balki ularning kalitlariga qarab
taqqoslanadi. Ikkilik qidiruv daraxtlarining boshqa ma'lumotlar tuzilmalaridan
ustunligi shu bilan bog'liqdir algoritmlarni saralash va qidirish algoritmlari kabi
tartibda o'tish juda samarali bo'lishi mumkin. Ikkilik qidirish daraxtlari asosiy
hisoblanadi ma'lumotlar tuzilishi kabi mavhum ma'lumotlar tuzilmalarini qurish
uchun foydalaniladi to'plamlar, multisetsva assotsiativ massivlar. Ikkilik qidiruv
daraxtiga elementni kiritishda yoki qidirishda har bir tashrif buyurgan tugunning
kalitini kiritilishi yoki topilishi kerak bo'lgan elementning kaliti bilan taqqoslash
kerak. Ikkilik qidiruv daraxtining shakli butunlay qo'shilish va o'chirish tartibiga
bog'liq va buzilib ketishi mumkin. Tasodifiy kiritish va yo'q qilishning uzoq
aralashgan ketma-ketligidan so'ng, daraxtning kutilgan balandligi tugmalar sonining
kvadrat ildiziga yaqinlashadi, √n,[iqtibos kerak] bu nisbatan tezroq o'sadi jurnal n.
Daraxtning degeneratsiyasini oldini olish bo'yicha ko'plab tadqiqotlar o'tkazildi,
natijada eng yomon vaqt murakkabligi paydo bo'ldi O (n) (batafsil ma'lumot uchun
bo'limga qarang Turlari).
Buyurtma munosabati:
Ikkilik qidirish buyurtma munosabatini talab qiladi, unga ko'ra har bir element
(element) a ma'nosida boshqa elementlar bilan taqqoslanishi mumkin jami oldindan
buyurtma. Elementning taqqoslashda samarali bo'lgan qismi uning deb ataladi kalit.
Ikki nusxada bo'ladimi, ya'ni. e. daraxtda bir xil kalitga ega bo'lgan turli xil
elementlarga ruxsat beriladi yoki yo'q, buyurtma munosabatlariga bog'liq emas, balki
faqat dasturga bog'liq. Daraxtdagi dublikatlarni qo'llab-quvvatlash va ularga ishlov
berish uchun qidiruv funktsiyasi uchun bo'limga qarang. Ikki nusxada qidirishga
ruxsat berilgan.
28

Foydalanilgan adabiyotlar:
1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
Introduction to Algorithms. Third Edition. The MIT Press Cambridge,
Massachusetts London, England, 2009. – 1312 p.
2. Scheinerman Edwant C++ for Mathematicians. An Introduction for Students
and Professionals. Chapman&Hall/CRC, Taylor&Francis Group, LLC, Boc а
Raton, London, New York, 2006. - 496 p.
3. D.S. Malik C++ Programming: From Problem Analysis to Program Design.
Seventh Edition. Course Technology, 2014.-1488 p.
4. Герберд Шилдт С++базовый курс.3-е издание. Перевод с англ. –М.: Изд.
дом «Вильямс», 2010. - 624 c.
5. Культин Н.Б. С++Builder в задачах и примерах. -СПб.: БХВ-Петербург,
2005. -336 с.
6. Madraximov Sh.F., Ikramov A.M., Babajanov M.R. C++ tilida programmalash
bo’yicha masalalar to’plami. O’quv qo’llanma. T., O’zbekiston Milliy
universiteti, “Universitet” nashriyoti, 2014. - 160 b.
7. Gopal, Arpita. Ma'lumotlar strukturasini kattalashtirish . PHI Learning, 2010,
p. 352.
8. Richard F. Gilberg va Behruz A. Foruzan. Ma'lumotlar tuzilmalari: C bilan
psevdokod yondashuvi . Tomson kursi texnologiyasi, 2005, p. 280.
9. Mark Allen Vayss, Ma'lumotlar strukturasi va algoritm tahlili C da, 2-nashr ,
Addison Uesli nashrlari.
10. Gopal, Arpita. Ma'lumotlar strukturasini kattalashtirish . PHI Learning, 2010, p.
353.
Internet resurslari:
1. http://www.btechsmartclass.com/data_structures/avl-trees.html
2. https://www.ziyouz.com/books/kollej_va_otm_darsliklari/
axborot_texnologiyalari .
3. https://www.programiz.com/dsa/binary-search-tree.
29

Daraxtlar, ikki tomonlama daraxtlar. Ikkilik daraxtlarning vakili. Ikkilik daraxtlarning o'tishi M U N D A R I J A Kirish ...............................................................................................................3 I. DARAXT - TERMINOLOGIYASI ...............................................................5 II. DARAXT VAKIL ......................................................................................12 III. IKKILIK DARAXTLAR MA’LUMOTLAR TUZILISHI ......................14 IV. IKKILIK DARAXTLAR VAKIL .............................................................18 V. IKKILIK DARAXTLARNING O’TISH ....................................................19 VI. IPLI IKKILIK DARAXTLAR .................................................................22 VII. IKKILIK QIDIRUV DARAXT ...............................................................24 Xulosa .............................................................................................................28 Foydalanilgan adabiyotlar ..............................................................................30 1

Kirish Algoritm- bu aniq hisoblashlarni bajaruvchi protsedura bo’lib unga kirish qismida kattalik yoki kattaliklar berilib chiqishda natijaviy kattalik yoki kattaliklar olinadi. Demak algoritm hisoblovchi qadamlardan tashkil topgan bo'lib,dastlabki qiymatlarga ko‘ra natijaviy kattaliklar qiymatini beradi. Daraxt tushunchasi. Daraxtning kompyuter xotirasida tasvirlanishi. Daraxt - bu chiziqli bo‘lmagan bog‘lamli ma‘lumotlar tuzilmasidir. Ikkilik qidiruv daraxti - bu ildiz otgan ikkilik daraxtichki tugunlari har birida kalitni (va ixtiyoriy ravishda bog'liq qiymatni) saqlaydi va har birida odatda belgilangan ikkita taniqli pastki daraxtlar mavjud chap va to'g'ri. Daraxt qo'shimcha ravishda qoniqtiradi ikkilik qidirish xususiyati: har bir tugundagi kalit chap pastki daraxtda saqlangan har qanday tugmachadan kattaroq yoki teng, o'ng pastki daraxtda saqlangan har qanday tugmachadan kichik yoki teng.Daraxtning barglarida (yakuniy tugunlarida) hech qanday kalit yo'q va ularni bir-biridan ajratib turadigan tuzilishga ega emas. Ko'pincha, har bir tugun tomonidan ko'rsatilgan ma'lumot bitta ma'lumot elementi emas, balki yozuvdir. Biroq, ketma-ketlik maqsadida tugunlar o'zlarining tegishli yozuvlarining biron bir qismiga emas, balki ularning kalitlariga qarab taqqoslanadi. Ikkilik qidiruv daraxtlarining boshqa ma'lumotlar tuzilmalaridan ustunligi shu bilan bog'liqdir algoritmlarni saralash va qidirish algoritmlari kabi tartibda o'tish juda samarali bo'lishi mumkin. A ikkilik daraxt a daraxt ma'lumotlari tuzilishi unda har bir tugun ko'pi bilan ikkitadan bolalar deb nomlangan chap bola va o'ng bola . A rekursiv ta'rif faqat foydalanish to'plam nazariyasi tushunchalar shundan iboratki (bo'shbo'lmagan) ikkilik daraxt a panjara (L,S,R) qaerda L va R ikkilik daraxtlar yoki bo'sh to'plam va S a singleton to'plami ildizni o'z ichiga olgan. Ba'zi mualliflar ikkitomonlama daraxtga ham bo'sh to'plam bo'lishiga ruxsat berishadi. A dan grafik nazariyasi bu erda aniqlangan istiqbolli, binar (va K-ary) daraxtlar aslida daraxtzorlar. Ikkilik daraxtni shunday deb ham atash mumkin ikki tomonlama daraxtzor. Bu juda qadimgi dasturlash kitoblarida uchraydigan atama, ilgari zamonaviy informatika 2

terminologiyasi ustun kelgan. Ikkilik daraxtni an deb talqin qilish ham mumkin yo'naltirilmagan, a o'rniga yo'naltirilgan grafik,bu holda ikkilik daraxt an buyurdi, ildiz otgan daraxt. Ba'zi mualliflar foydalanadilar ikkilik daraxt o'rniga ikkilik daraxt daraxtning ildiz otganligini ta'kidlash uchun ,lekin yuqorida ta'riflanganidek, ikkilik daraxt har doim ildiz otadi. Ikkilik daraxt - bu buyurtma qilingan alohida holat K-ary daraxti, qayerda k 2. Matematikada nima deyiladi ikkilik daraxt muallifdan muallifga sezilarli darajada farq qilishi mumkin. Ba'zilar odatda kompyuter fanida ishlatiladigan ta'rifdan foydalanadilar,ammo boshqalar buni aniq ikki bolali har bir yaproqsiz deb belgilaydilar va bolalarga ham (chapda / o'ngda) buyurtma berishlari shart emas.Hisoblashda ikkilik daraxtlar ikki xil usulda ishlatiladi:  Birinchidan, har bir tugun bilan bog'liq ba'zi bir qiymat yoki yorliqlarga asoslangan tugunlarga kirish vositasi sifatida.Amalga oshirish uchun shu tarzda belgilangan ikkilik daraxtlar ishlatiladi ikkilik qidiruv daraxtlari va ikkilik uyumlar va samaradorlik uchun ishlatiladi qidirish va tartiblash. Ildiz bo'lmagan tugunlarni chap yoki o'ng bola deb belgilash, hatto bitta bola bo'lsa ham, ushbu dasturlarning ayrimlarida, xususan,ikkilik qidiruv daraxtlarida muhim ahamiyatga ega. Biroq, daraxtga ma'lum tugunlarni joylashtirish kontseptual ma'lumotlarning bir qismi emas. Masalan, oddiy ikkilik qidiruv daraxtida tugunlarni joylashtirish deyarli ularning qo'shilish tartibiga bog'liq va ularni qayta tartibga solish mumkin (masalan muvozanatlash) ma'nosini o'zgartirmasdan.  Ikkinchidan, ma'lumotlarning tegishli bifurkatsion tuzilishga ega vakili sifatida. Bunday hollarda boshqa tugunlar ostidagi va / yoki chapga yoki o'ngga tugunlarning alohida joylashuvi ma'lumotlarning bir qismidir (ya'ni uni o'zgartirish ma'noni o'zgartirishi mumkin). Umumiy misollar Huffman kodlash va kladogrammalar. Hujjatlarning har kungi boblarga, bo'limlarga, xatboshilarga va boshqalarga bo'linishi binary daraxtlar o'rniga n-ary bilan o'xshash misoldir. 3

I. Daraxt - terminologiyasi Chiziqli ma'lumotlar strukturasida ma'lumotlar ketma-ketlikda va chiziqli bo'lmagan ma'lumotlar tarkibida ma'lumotlar tasodifiy tartibda joylashtirilgan. Daraxt - bu juda keng qo'llaniladigan, chiziqli bo'lmagan ma'lumotlar tuzilishi. Daraxt ma'lumotlari tuzilishini quyidagicha aniqlash mumkin. Daraxt - bu ma'lumotlarning ierarxik tarkibida tartibga soluvchi chiziqli bo'lmagan strukturasi va bu rekursiv ta'rif. Daraxtlar ma'lumotlari tuzilishi - bu ierarxik tuzilishda rekursiv ravishda tashkil etilgan ma'lumotlar to'plami (Tugun) Daraxtlar ma'lumotlari tarkibida har bir alohida element tugun deb nomlanadi. Daraxt ma'lumotlari tarkibidagi tugun ushbu elementning haqiqiy ma'lumotlarini saqlaydi va ierarxik tuzilishdagi keyingi elementga bog'lanadi. Daraxt ma'lumotlari tarkibida, agar bizda N tugunlari bo'lsa, unda biz maksimal N-1 sonli qirralarga ega bo'lishimiz mumkin. Terminologiya Daraxt ma'lumotlari tarkibida biz quyidagi terminologiyadan foydalanamiz ... 1. Ildiz tugun Daraxt ma'lumotlari tarkibida birinchi tuguni ildiz tuguni deb nomlanadi. Har bir daraxtda ildiz tuguni bo'lishi kerak. Ildiz tuguni daraxt ma'lumotlari tuzilishining kelib chiqishi deb ayta olamiz. Har qanday daraxtda faqat bitta ildiz tuguni bo'lishi kerak. Bizda hech qachon daraxtda bir nechta ildiz tugunlari bo'lmaydi. 4

2. Qirra Daraxt ma'lumotlari tuzilmasida har qanday ikkita tugun orasidagi bog'lanish aloqasi qirra deb nomlanadi. "N" tugunli daraxtda maksimal "N-1" qirralar bo'ladi. 3. Ota-ona Daraxt ma'lumotlari tuzilmasida har qanday tugunning o'tmishi bo'lgan tugun ota- ona tugun deb nomlanadi. Oddiy so'zlar bilan aytganda, undan boshqa har qanday tugunga qadar shoxga ega bo'lgan tugun ota tugun deb ataladi. Ota-ona tugunini "bolasi / bolalari bo'lgan tugun" deb ham aniqlash mumkin. 5

Daraxtlar, ikki tomonlama daraxtlar. Ikkilik daraxtlarning vakili. Ikkilik daraxtlarning o'tishi

12.08.2023

0

1497.8203125 KB

Похожие