Разлика между пълно бинарно дърво и пълно бинарно дърво

Цялостно бинарно дърво срещу пълно бинарно дърво

Двоичното дърво е дърво, при което всеки възел има едно или две деца. В двоично дърво възелът не може да има повече от две деца. В двоично дърво децата се назовават като деца вляво и вдясно. Детските възли съдържат препратка към своя родител. Пълното бинарно дърво е двоично дърво, в което всяко ниво на бинарното дърво е напълно запълнено, с изключение на последното ниво. В незапълнено ниво възлите са прикрепени, като се започне от най-лявата позиция. Пълно бинарно дърво е дърво, в което всеки възел в дървото има две деца, с изключение на листата на дървото.

Какво е пълно бинарно дърво?

Пълното бинарно дърво е двоично дърво, в което всеки възел в дървото има точно нула или две деца. С други думи, всеки възел в дървото, с изключение на листата, има точно две деца. Фигура 1 по-долу изобразява пълно бинарно дърво. В пълно бинарно дърво броят на възлите (n), броят на лавовете (l) и броят на вътрешните възли (i) е свързан по специален начин, така че ако знаете някой от тях, можете да определите другите два стойности, както следва:

1. Ако пълно двоично дърво има i вътрешни възли:

- Брой листа l = i + 1

- Общ брой възли n = 2 * i + 1

2. Ако пълно двоично дърво има n възли:

- Брой вътрешни възли i = (n-1) / 2

- Брой листа l = (n + 1) / 2

3. Ако пълно двоично дърво има l листа:

- Общ брой възли n = 2 * l-1

- Брой вътрешни възли i = l-1

Какво е пълно бинарно дърво?

Както е показано на фигура 2, пълно бинарно дърво е бинарно дърво, в което всяко ниво на дървото е напълно запълнено, с изключение на последното ниво. Също така, на последното ниво, възлите трябва да бъдат прикрепени, като се започне от най-лявата позиция. Пълно бинарно дърво с височина h удовлетворява следните условия:

- От коренния възел нивото над последното ниво представлява пълно бинарно дърво с височина h-1

- Един или повече възли в последното ниво може да имат 0 или 1 деца

- Ако a, b са два възела на нивото над последното ниво, тогава a има повече деца, отколкото b, ако и само ако a се намира вляво от b

Каква е разликата между Пълно бинарно дърво и Пълно бинарно дърво?

Пълните двоични дървета и пълните бинарни дървета имат явна разлика. Докато пълно бинарно дърво е двоично дърво, в което всеки възел има нула или две деца, пълно бинарно дърво е бинарно дърво, в което всяко ниво на бинарното дърво е напълно запълнено, с изключение на последното ниво. Някои специални структури от данни като купища трябва да бъдат пълни двоични дървета, докато не е необходимо да са пълни двоични дървета. В пълно двоично дърво, ако знаете броя на общите възли или броя на лавовете или броя на вътрешните възли, можете лесно да намерите другите два. Но пълно бинарно дърво няма специално свойство, свързано с тези три атрибута.