Двоичното дърво означава, че възелът може да има максимум две деца. Тук самото двоично име предполага, че 'две'; следователно всеки възел може да има 0, 1 или 2 деца.

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

tcp ip модел

Горното дърво е двоично дърво, тъй като всеки възел съдържа най-много две деца. Логическото представяне на горното дърво е дадено по-долу:

В горното дърво възел 1 съдържа два указателя, т.е. ляв и десен указател, сочещи съответно към левия и десния възел. Възел 2 съдържа и двата възела (ляв и десен възел); следователно има два указателя (ляв и десен). Възлите 3, 5 и 6 са листовите възли, така че всички тези възли съдържат НУЛА показалец върху лявата и дясната част.

Свойства на двоичното дърво

• На всяко ниво на i максималният брой възли е 2ⁱ.
• Височината на дървото се определя като най-дългия път от коренния възел до листовия възел. Дървото, което е показано по-горе, има височина, равна на 3. Следователно максималният брой възли на височина 3 е равен на (1+2+4+8) = 15. Като цяло максималният брой възли, възможен на височина h е (2⁰+ 2¹+ 2²+….2^ч) = 2^h+1-1.
• Минималният брой възможни възли на височина h е равен на h+1 .
• Ако броят на възлите е минимален, тогава височината на дървото ще бъде максимална. Обратно, ако броят на възлите е максимален, тогава височината на дървото ще бъде минимална.

Ако има 'n' брой възли в двоичното дърво.

Минималната височина може да се изчисли като:

Както знаем,

n = 2^h+1-1

n+1 = 2^h+1

Взимайки дневник от двете страни,

дневник₂(n+1) = log2(2^h+1)

дневник₂(n+1) = h+1

h = дневник₂(n+1) - 1

Максималната височина може да се изчисли като:

Както знаем,

n = h+1

h= n-1

заключване на приложение за Android

Видове двоично дърво

Има четири вида двоично дърво:

Пълно/ правилно/ строго двоично дърво Пълно двоично дърво Перфектно двоично дърво Изродено двоично дърво Балансирано двоично дърво

1. Пълно/ правилно/ строго двоично дърво

хибернация диалект

Пълното двоично дърво е известно също като строго двоично дърво. Дървото може да се счита за пълно двоично дърво само ако всеки възел трябва да съдържа 0 или 2 деца. Пълното двоично дърво може също да се дефинира като дърво, в което всеки възел трябва да съдържа 2 деца, с изключение на листовите възли.

Нека да разгледаме простия пример за пълното двоично дърво.

В горното дърво можем да наблюдаваме, че всеки възел съдържа или нула, или две деца; следователно, това е пълно двоично дърво.

Свойства на пълното двоично дърво

• Броят на листовите възли е равен на броя на вътрешните възли плюс 1. В горния пример броят на вътрешните възли е 5; следователно броят на листните възли е равен на 6.
• Максималният брой възли е същият като броя на възлите в двоичното дърво, т.е. 2^h+1-1.
• Минималният брой възли в пълното двоично дърво е 2*h-1.
• Минималната височина на пълното двоично дърво е дневник₂(n+1) - 1.
• Максималната височина на пълното двоично дърво може да се изчисли като:

n= 2*h - 1

n+1 = 2*h

h = n+1/2

Пълно двоично дърво

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

разлика между гигабайт и мегабайт

Нека създадем цялостно двоично дърво.

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

Свойства на пълното двоично дърво

• Максималният брой възли в пълното двоично дърво е 2^h+1- 1.
• Минималният брой възли в пълното двоично дърво е 2^ч.
• Минималната височина на пълното двоично дърво е дневник₂(n+1) - 1.
• Максималната височина на пълно двоично дърво е

Перфектно двоично дърво

Едно дърво е идеално двоично дърво, ако всички вътрешни възли имат 2 деца и всички листови възли са на едно и също ниво.

Нека да разгледаме прост пример за перфектно двоично дърво.

Дървото по-долу не е перфектно двоично дърво, защото всички листови възли не са на едно и също ниво.

Забележка: Всички перфектни двоични дървета са както пълните двоични дървета, така и пълните двоични дървета, но обратното не е вярно, т.е. всички пълни двоични дървета и пълните двоични дървета са перфектните двоични дървета.

Изродено двоично дърво

Изроденото двоично дърво е дърво, в което всички вътрешни възли имат само едно дете.

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

Горното дърво е изродено двоично дърво, тъй като всички възли имат само едно дете. Известно е също като дясно изкривено дърво, тъй като всички възли имат само дясно дете.

Горното дърво също е изродено двоично дърво, тъй като всички възли имат само едно дете. Известно е също като ляво изкривено дърво, тъй като всички възли имат само ляво дете.

Балансирано двоично дърво

Балансираното двоично дърво е дърво, в което лявото и дясното дърво се различават най-много с 1. Например, AVL и Червено-черни дървета са балансирано двоично дърво.

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

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

xdxd значение

Горното дърво не е балансирано двоично дърво, тъй като разликата между лявото и дясното поддърво е по-голяма от 1.

Реализация на двоично дърво

Двоичното дърво се реализира с помощта на указатели. Първият възел в дървото е представен от коренния указател. Всеки възел в дървото се състои от три части, т.е. данни, ляв указател и десен указател. За да създадем двоично дърво, първо трябва да създадем възела. Ще създадем потребителски възел, както е показано по-долу:

 struct node { int data, struct node *left, *right; } 

В горната структура, данни е стойността, ляв показалец съдържа адреса на левия възел и десен показалец съдържа адреса на десния възел.

Програма за двоично дърво на C

 #include struct node { int data; struct node *left, *right; } void main() { struct node *root; root = create(); } struct node *create() { struct node *temp; int data; temp = (struct node *)malloc(sizeof(struct node)); printf('Press 0 to exit'); printf('
Press 1 for new node'); printf('Enter your choice : '); scanf('%d', &choice); if(choice==0) { return 0; } else { printf('Enter the data:'); scanf('%d', &data); temp->data = data; printf('Enter the left child of %d', data); temp->left = create(); printf('Enter the right child of %d', data); temp->right = create(); return temp; } } 

Горният код извиква функцията create() рекурсивно и създава нов възел при всяко рекурсивно извикване. Когато всички възли са създадени, тогава се образува двоична дървовидна структура. Процесът на посещение на възлите е известен като обхождане на дърво. Има три типа обхождания, използвани за посещение на възел:

• Обхождане по ред
• Обхождане на предварителна поръчка
• Преминаване на пощенски поръчки