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

A muvozanatli ikkilik daraxt - bu har bir tugunning chap va o'ng pastki daraxtlari balandligi bo'yicha 1 dan ko'p bo'lmagan farq qiladigan ikkilik daraxt tuzilishi. Ikkala daraxtni ham ko'rib chiqish mumkin, u erda hech qanday barg bargdan boshqa bargga qaraganda ancha uzoqroq joylashgan. (Turli xil muvozanatlash sxemalari "ancha uzoqroq" ning turli xil ta'riflariga imkon beradi.)

A buzilib ketgan (yoki patologik) daraxt - bu har bir ota-ona tugunida faqat bitta bog'langan tugun mavjud.

Bu shuni anglatadiki, daraxt o'zini a kabi tutadi bog'langan ro'yxat ma'lumotlar tuzilishi.

Ikkilik daraxtlarning xususiyatlari

Tugunlarning soni to'liq ikkilik daraxtda, hech bo'lmaganda va ko'pi bilan , qayerda bo'ladi balandlik daraxtning. Faqatgina ildiz tugunidan iborat daraxtning balandligi 0 ga teng.

Barg tugunlari soni mukammal ikkilik daraxtda, bo'ladi chunki bargsiz (ichki a) tugunlarning soni .

Bu degani, to'liq binar daraxt bilan barglari bor tugunlar.

A muvozanatli to'liq ikkilik daraxt, (qarang ship funktsiyasi).

A mukammal to'liq ikkilik daraxt, shunday qilib .

Ning ikkilik daraxtidagi bo'sh havolalar soni (ya'ni tugunlarning yo'q bolalari) n tugunlari (n+1).

A-dagi ichki tugunlarning soni to'liq binar daraxt n tugunlar .

Bilan har qanday bo'sh bo'lmagan ikkilik daraxt uchun n0 barg tugunlari va n2 2-darajali tugunlar, n0 = n2 + 1.

Ikkilik daraxtlarni saqlash usullari

Ikkilik daraxtlarni qurish mumkin dasturlash tili ibtidoiy usullar.

Tugunlar va ma'lumotnomalar

Bilan tilda yozuvlar va ma'lumotnomalar, ikkilik daraxtlar odatda daraxt tugunlari tuzilishi bilan qurilgan bo'lib, unda ba'zi ma'lumotlar va chap farzandi va uning o'ng bolasi haqida ma'lumotlar mavjud. Ba'zan unda noyob ota-onasiga havola mavjud. Agar tugunda ikkitadan kam bola bo'lsa, ko'rsatgichlarning ayrimlari maxsus nol qiymatiga yoki maxsus qiymatga o'rnatilishi mumkin qo'riqchi tuguni.