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

Пълното двоично дърво може да се дефинира като a двоично дърво в който всички възли имат 0 или две деца. С други думи, пълното двоично дърво може да се дефинира като двоично дърво, в което всички възли имат две деца, с изключение на листовите възли.

Дървото по-долу е пълно двоично дърво:

Горното дърво е пълно двоично дърво, тъй като всички възли с изключение на листовите възли имат две деца.

Пълна теорема за двоично дърво:

как да разберете размера на дисплея

Помислете за двоично дърво T като непразно дърво, тогава:

• Нека аз съм вътрешни възли в дърво и L да е листен възел в дърво, тогава броят на листовите възли ще бъде равен на:
  L = I + 1
• Ако T има I брой вътрешни възли и N е общият брой възли, тогава общият брой възли ще бъде равен на:
  N = 2I + 1
• Ако T съдържа 'N' общ брой възли и 'I' е брой вътрешни възли, тогава броят на вътрешните възли ще бъде равен на:
  I = (N-1)/2
• Ако 'T' има 'N' общ брой възли и 'L' е брой листови възли, тогава броят на листовите възли ще бъде равен на:
  L = (N+1)/2
• Ако 'T' съдържа 'L' брой листови възли, тогава общият брой възли ще бъде равен на:
  N = 2L - 1
• Ако „T“ има „L“ брой листови възли и „I“ е брой вътрешни възли, тогава броят на вътрешните възли ще бъде равен на:
  I = L - 1

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

Двоичното дърво се нарича пълно двоично дърво, когато всички нива са напълно запълнени с изключение на последното ниво, което се запълва отляво.

Дървото по-долу е пълно двоично дърво:

Пълното двоично дърво е подобно на пълното двоично дърво с изключение на двете разлики, които са дадени по-долу:

• Запълването на листния възел трябва да започне от най-лявата страна.
• Не е задължително последният листов възел да има правилния брат.

Нека разберем горните точки чрез пример:

mvc в пролетна рамка

Помислете за дървото по-долу:

Горното дърво е пълно двоично дърво, но не и пълно двоично дърво, тъй като възел 6 няма правилния брат.

преименуване на папка в linux

Създаване на пълно двоично дърво

Да предположим, че имаме масив от 6 елемента, показан по-долу:

Горният масив съдържа 6 елемента, т.е. 1, 2, 3, 4, 5, 6. Следните са стъпките, които трябва да се използват за създаване на цялостно двоично дърво:

Етап 1: Първо ще изберем първия елемент от масива, т.е. 1, и ще направим основен възел на дървото. Броят налични елементи в първото ниво е 1.

Стъпка 2: Сега ще изберем втория и третия елемент от масива. Запазете втория елемент и третия елемент от масива като ляво и дясно дете на коренния възел съответно, както е показано по-долу:

Както можем да видим по-горе, броят на наличните елементи във второто ниво е 2.

Стъпка 3: Сега ще изберем следващите два елемента от масива, т.е. 4 и 5. Запазете тези два елемента отляво и отдясно на възел 2, както е показано по-долу:

Както можем да забележим по-горе, възли 4 и 5 са ​​ляво и дясно дъщерно дете на възел 2 съответно.

Стъпка 4: Сега ще изберем последния елемент от масива, т.е. 6, и ще го запазим като ляво дете на възел 3, тъй като знаем, че в пълно двоично дърво възлите се запълват от лявата страна, както е показано по-долу:

как да стартирате скрипт на linux

Както можем да видим, че второто ниво съдържа 3 елемента.

Нека разберем разликите между пълното и пълното двоично дърво чрез изображенията.

1. Двоичното дърво, което е показано по-долу, не е нито пълно, нито пълно двоично дърво. Това не е пълно двоично дърво, защото възел 3 има само едно дете. Това също не е пълно двоично дърво, тъй като възлите трябва да се запълват от лявата страна, но възел 3 има дясно дете и няма ляво дете.
   
2. Двоичното дърво, което е показано по-долу, е пълно двоично дърво, но не и пълно двоично дърво. Това е пълно двоично дърво, защото всички възли имат 0 или 2 деца. Това не е пълно двоично дърво, тъй като възел 3 няма деца, докато възел 2 има своите деца и знаем, че възлите трябва да се попълват от лявата страна в пълно двоично дърво.
   
3. Двоичното дърво, което е показано по-долу, е пълно двоично дърво, но не и пълно двоично дърво. Това е пълно двоично дърво, тъй като всички възли са оставени попълнени. Това не е пълно двоично дърво, тъй като възел 2 има само едно дете.
   
4. Двоичното дърво, което е показано по-долу, е както пълно, така и пълно двоично дърво. Това е пълно двоично дърво, тъй като всички възли са оставени попълнени. Това е пълно двоично дърво, тъй като всички възли имат 0 или 2 деца.