204-guruh talabasi jo`rayev sherzodning algoritmlar nazariyasi fanidan tayyorlagan kurs ishi reja

An ajdodlar jadvali mukammal chuqurlik-4 ikkilik daraxtiga xaritalar.

A to'liq ikkilik daraxt (ba'zan a deb ham nomlanadi to'g'ri yoki samolyot ikkilik daraxt) har bir tugunda 0 yoki 2 boladan iborat bo'lgan daraxt. To'liq ikkilik daraxtni aniqlashning yana bir usuli bu rekursiv ta'rif. To'liq ikkilik daraxt ham:

Bitta tepalik.

Ildiz tugunida ikkita kichik daraxt bo'lgan daraxt, ikkalasi ham to'liq ikkilik daraxtlardir.

A to'liq har darajadagi ikkilik daraxt, ehtimol oxirgisi bundan mustasno, to'liq to'ldirilgan va oxirgi darajadagi barcha tugunlar iloji boricha chaproq. U 1 dan 2 gacha bo'lishi mumkin h oxirgi darajadagi tugunlar Muqobil ta'rif - eng to'g'ri barglari (ehtimol barchasi) olib tashlangan mukammal daraxt. Ba'zi mualliflar ushbu atamadan foydalanadilar to'liq Buning o'rniga quyida keltirilgan mukammal ikkilik daraxtga murojaat qilish, bu holda ular ushbu turdagi daraxtlarni (ehtimol oxirgi daraja to'ldirilmagan holda) deyarli to'liq ikkilik daraxt yoki deyarli yakunlandi ikkilik daraxt. To'liq ikkilik daraxt massiv yordamida samarali tarzda ifodalanishi mumkin.

To'liq ikkilik daraxt (bu to'liq emas)

A mukammal ikkilik daraxt - bu barcha ichki tugunlarning ikkita farzandi bo'lgan ikkilik daraxt va barcha barglar bir xil chuqurlik yoki bir xil Daraja. Barkamol binar daraxtning misoli (qarindosh bo'lmagan). ajdodlar jadvali insonning ma'lum bir chuqurlikka ega bo'lishi, chunki har bir odamning ikkita biologik ota-onasi (bitta onasi va bitta otasi) bor.

Agar ota-bobolar jadvalida onaning va otaning ma'lum bir tugun uchun har doim bir tomonda bo'lishi sharti bilan, ularning jinsi chap va o'ng bolalarning o'xshashligi sifatida qaralishi mumkin, bolalar bu erda algoritmik atama sifatida tushuniladi. Shuning uchun mukammal daraxt har doim to'liq bo'ladi, ammo to'liq daraxt mukammal bo'lishi shart emas.

In cheksiz to'liq ikkitomonlama daraxt, har bir tugunda ikkita bola bor (va shuning uchun darajalar to'plami shunday) nihoyatda cheksiz). Barcha tugunlarning to'plami son-sanoqsiz, ammo ildizdan chiqadigan barcha cheksiz yo'llarning to'plamini hisoblash mumkin emas. doimiylikning kardinalligi. Buning sababi shundaki, bu yo'llar buyurtmani saqlash bilan mos keladi bijection ning nuqtalariga Kantor o'rnatilgan, yoki (a misolidan foydalanib Stern-Brocot daraxti) ijobiy to'plamga mantiqsiz raqamlar.