Толық екілік ағаш пен толық екілік ағаш
Екілік ағаш - әр түйінде бір немесе екі бала болатын ағаш. Екілік ағашта түйінде екіден артық бала болуы мүмкін емес. Екілік ағашта балаларды «сол» және «оң» балалар деп атайды. Еншілес түйіндерде олардың ата-анасына сілтеме бар. Толық екілік ағаш - соңғы деңгейден басқа екілік ағаштың әрбір деңгейі толығымен толтырылған екілік ағаш. Толтырылмаған деңгейде түйіндер ең сол жақтан бастап бекітіледі. Толық екілік ағаш - ағаштың жапырақтарынан басқа әрбір түйінде екі бала болатын ағаш.
Толық екілік ағаш дегеніміз не?
Толық екілік ағаш - бұл ағаштың әрбір түйінінде дәл нөл немесе екі бала болатын екілік ағаш. Басқаша айтқанда, жапырақтардан басқа ағаштың әрбір түйінінде дәл екі бала болады. Төмендегі 1-суретте толық екілік ағаш бейнеленген. Толық екілік ағашта түйіндер саны (n), таңбалар саны (l) және ішкі түйіндер саны (i) ерекше түрде байланысты, сондықтан олардың кез келгенін білсеңіз, қалған екеуін анықтауға болады. мәндер келесідей:
1. Толық екілік ағаштың i ішкі түйіндері болса:
– Жапырақтар саны l=i+1
– Түйіндердің жалпы саны n=2i+1
2. Толық екілік ағашта n түйін болса:
– Ішкі түйіндер саны i=(n-1)/2
– Жапырақтар саны l=(n+1)/2
3. Толық екілік ағашта l жапырақ болса:
– Түйіндердің жалпы саны n=2l-1
– Ішкі түйіндер саны i=l-1
Толық екілік ағаш дегеніміз не?
2-суретте көрсетілгендей, толық екілік ағаш соңғы деңгейден басқа ағаштың әрбір деңгейі толығымен толтырылған екілік ағаш болып табылады. Сондай-ақ, соңғы деңгейде түйіндерді ең сол жақтан бастап бекіту керек. Биіктігі h толық екілік ағаш келесі шарттарды қанағаттандырады:
– Түбірлік түйіннен соңғы деңгейден жоғары деңгей h-1 биіктіктегі толық екілік ағашты білдіреді
– Соңғы деңгейдегі бір немесе бірнеше түйінде 0 немесе 1 бала болуы мүмкін
– Егер a, b соңғы деңгейден жоғары деңгейде екі түйін болса, онда a, b-тің сол жағында орналасқан болса ғана, b-ден көп балаға ие болады
Толық екілік ағаш пен толық екілік ағаштың айырмашылығы неде?
Толық екілік ағаштар мен толық екілік ағаштар арасында айқын айырмашылық бар. Толық екілік ағаш әр түйінде нөл немесе екі бала болатын екілік ағаш болса, толық екілік ағаш соңғы деңгейден басқа екілік ағаштың әрбір деңгейі толығымен толтырылған екілік ағаш болып табылады. Үймелер сияқты кейбір арнайы деректер құрылымдары толық екілік ағаштар болуы керек, ал олардың толық екілік ағаштар болуы қажет емес. Толық екілік ағашта, егер сіз жалпы түйіндердің санын немесе таңбалардың санын немесе ішкі түйіндердің санын білсеңіз, қалған екеуін өте оңай таба аласыз. Бірақ толық екілік ағаштың үш атрибутқа қатысты арнайы қасиеті жоқ.
