Шта је пуно бинарно стабло?
Пуно бинарно стабло се може дефинисати као а бинарно дрво у којој сви чворови имају 0 или два детета. Другим речима, пуно бинарно стабло се може дефинисати као бинарно стабло у коме сви чворови имају два детета осим лисних чворова.
Доле стабло је потпуно бинарно стабло:
низ дужине
Горње стабло је пуно бинарно стабло јер сви чворови осим чворова листа имају два детета.
Пуна теорема о бинарном стаблу:
Сматрајте да је бинарно дрво Т непразно дрво:
- Нека су И унутрашњи чворови у стаблу и Л да је листни чвор у стаблу, тада би број лисних чворова био једнак:
Л = И + 1 - Ако Т има И број унутрашњих чворова и Н да је укупан број чворова, онда би укупан број чворова био једнак:
Н = 2И + 1 - Ако Т садржи 'Н' укупан број чворова и 'И' као број унутрашњих чворова, тада би број унутрашњих чворова био једнак:
И = (Н-1)/2 - Ако 'Т' има 'Н' укупан број чворова, а 'Л' је број листова чворова, тада би број листовних чворова био једнак:
Л = (Н+1)/2 - Ако 'Т' садржи 'Л' број листова чворова, онда би укупан број чворова био једнак:
Н = 2Л - 1 - Ако 'Т' има 'Л' број листова чворова, а 'И' је број унутрашњих чворова, тада би број унутрашњих чворова био једнак:
И = Л - 1
Шта је потпуно бинарно стабло?
За бинарно стабло се каже да је комплетно бинарно стабло када су сви нивои потпуно попуњени осим последњег нивоа који се попуњава са леве стране.
Доле стабло је комплетно бинарно стабло:
Комплетно бинарно стабло је слично пуном бинарном стаблу осим две разлике које су дате у наставку:
- Пуњење лисног чвора мора почети са крајње леве стране.
- Није обавезно да последњи чвор листа мора имати правог брата или сестру.
Хајде да разумемо горе наведене тачке кроз пример:
Размотрите следеће стабло:
Горње стабло је потпуно бинарно стабло, али не и пуно бинарно стабло јер чвор 6 нема свог правог брата.
Креирање комплетног бинарног стабла
Претпоставимо да имамо низ од 6 елемената приказаних у наставку:
Горњи низ садржи 6 елемената, тј. 1, 2, 3, 4, 5, 6. Следе кораци који ће се користити за креирање комплетног бинарног стабла:
Корак 1: Прво ћемо изабрати први елемент низа, тј. 1, и направити коријенски чвор стабла. Број доступних елемената на првом нивоу је 1.
Корак 2: Сада ћемо изабрати други и трећи елемент низа. Задржите други елемент и трећи елемент низа као лево и десно дете основног чвора, респективно, као што је приказано испод:
Као што можемо приметити изнад, број доступних елемената у другом нивоу је 2.
Корак 3: Сада ћемо изабрати следећа два елемента из низа, тј. 4 и 5. Задржите ова два елемента са леве и десне стране чвора 2 као што је приказано испод:
Као што можемо приметити изнад, чворови 4 и 5 су лево и десно дете чвора 2.
4. корак: Сада ћемо изабрати последњи елемент низа, тј., 6, и задржати га као лево дете чвора 3 пошто знамо да се у комплетном бинарном стаблу чворови попуњавају са леве стране као што је приказано испод:
Као што можемо приметити да други ниво садржи 3 елемента.
Хајде да кроз слике разумемо разлике између потпуног и пуног бинарног стабла.
шта је хибернација у Јави
- Бинарно стабло које је приказано испод није ни потпуно ни пуно бинарно стабло. То није пуно бинарно стабло јер чвор 3 има само једно дете. Такође није потпуно бинарно стабло јер чворови треба да се попуне са леве стране, али чвор 3 има десно дете и нема лево дете.
- Бинарно стабло, које је приказано испод, је пуно бинарно стабло, али не и потпуно бинарно стабло. То је пуно бинарно стабло јер сви чворови имају или 0 или 2 детета. То није комплетно бинарно стабло јер чвор 3 нема ниједну децу док чвор 2 има своју децу и знамо да чворове треба попунити са леве стране у потпуном бинарном стаблу.
- Бинарно стабло које је приказано испод је комплетно бинарно стабло, али не и пуно бинарно стабло. То је потпуно бинарно стабло јер су сви чворови остављени попуњени. То није пуно бинарно стабло јер чвор 2 има само једно дете.
- Бинарно стабло које је приказано у наставку је потпуно као и пуно бинарно стабло. То је потпуно бинарно стабло јер су сви чворови остављени попуњени. То је пуно бинарно стабло јер сви чворови имају или 0 или 2 деце.
