TechCodeview

Drzewo binarne oznacza, że ​​węzeł może mieć maksymalnie dwoje dzieci. Tutaj sama nazwa binarna sugeruje, że „dwa”; dlatego każdy węzeł może mieć 0, 1 lub 2 dzieci.

Przyjrzyjmy się drzewu binarnemu na przykładzie.

Powyższe drzewo jest drzewem binarnym, ponieważ każdy węzeł zawiera maksymalnie dwoje dzieci. Logiczna reprezentacja powyższego drzewa jest podana poniżej:

W powyższym drzewie węzeł 1 zawiera dwa wskaźniki, tj. lewy i prawy wskaźnik wskazujące odpowiednio lewy i prawy węzeł. Węzeł 2 zawiera oba węzły (węzeł lewy i prawy); dlatego ma dwa wskaźniki (lewy i prawy). Węzły 3, 5 i 6 to węzły liściowe, więc wszystkie te węzły zawierają ZERO wskaźnik po lewej i prawej stronie.

Właściwości drzewa binarnego

• Na każdym poziomie i maksymalna liczba węzłów wynosi 2^I.
• Wysokość drzewa definiuje się jako najdłuższą ścieżkę od węzła korzenia do węzła liścia. Drzewo pokazane powyżej ma wysokość równą 3. Zatem maksymalna liczba węzłów na wysokości 3 wynosi (1+2+4+8) = 15. Ogólnie rzecz biorąc, maksymalna liczba węzłów możliwa na wysokości h jest (2⁰+ 2¹+ 2²+….2^H) = 2^h+1-1.
• Minimalna liczba węzłów możliwa na wysokości h jest równa h+1 .
• Jeśli liczba węzłów jest minimalna, wysokość drzewa będzie maksymalna. I odwrotnie, jeśli liczba węzłów jest maksymalna, wówczas wysokość drzewa będzie minimalna.

Jeśli w drzewie binarnym znajduje się liczba „n” węzłów.

Minimalną wysokość można obliczyć jako:

Jak to wiemy,

n = 2^h+1-1

n+1 = 2^h+1

Biorąc kłodę z obu stron,

dziennik₂(n+1) = log2(2^h+1)

wartość logiczna na ciąg

dziennik₂(n+1) = h+1

h = log₂(n+1) - 1

Maksymalną wysokość można obliczyć jako:

Jak to wiemy,

n = h+1

h= n-1

Rodzaje drzew binarnych

Istnieją cztery typy drzew binarnych:

Pełne/właściwe/ścisłe drzewo binarne Kompletne drzewo binarne Idealne drzewo binarne Zdegenerowane drzewo binarne Zrównoważone drzewo binarne

1. Pełne/właściwe/ścisłe drzewo binarne

Pełne drzewo binarne jest również znane jako ścisłe drzewo binarne. Drzewo można uznać za pełne drzewo binarne tylko wtedy, gdy każdy węzeł musi zawierać 0 lub 2 dzieci. Pełne drzewo binarne można również zdefiniować jako drzewo, w którym każdy węzeł musi zawierać 2 dzieci, z wyjątkiem węzłów liści.

Spójrzmy na prosty przykład drzewa pełnego binarnego.

W powyższym drzewie możemy zaobserwować, że każdy węzeł zawiera zero lub dwoje dzieci; dlatego jest to drzewo w pełni binarne.

Właściwości pełnego drzewa binarnego

Java przesyła ciąg znaków do int

• Liczba węzłów liściowych jest równa liczbie węzłów wewnętrznych plus 1. W powyższym przykładzie liczba węzłów wewnętrznych wynosi 5; dlatego liczba węzłów liściowych jest równa 6.
• Maksymalna liczba węzłów jest taka sama, jak liczba węzłów w drzewie binarnym, tj. 2^h+1-1.
• Minimalna liczba węzłów w pełnym drzewie binarnym wynosi 2*h-1.
• Minimalna wysokość pełnego drzewa binarnego wynosi dziennik₂(n+1) - 1.
• Maksymalną wysokość pełnego drzewa binarnego można obliczyć jako:

n= 2*h - 1

n+1 = 2*h

h = n+1/2

Kompletne drzewo binarne

Kompletne drzewo binarne to drzewo, w którym wszystkie węzły są całkowicie wypełnione, z wyjątkiem ostatniego poziomu. Na ostatnim poziomie wszystkie węzły muszą pozostać jak najbardziej pozostawione. W pełnym drzewie binarnym węzły należy dodawać od lewej strony.

Python zapisz json do pliku

Stwórzmy kompletne drzewo binarne.

Powyższe drzewo jest kompletnym drzewem binarnym, ponieważ wszystkie węzły są całkowicie wypełnione, a wszystkie węzły na ostatnim poziomie są dodawane najpierw po lewej stronie.

Właściwości kompletnego drzewa binarnego

• Maksymalna liczba węzłów w pełnym drzewie binarnym wynosi 2^h+1- 1.
• Minimalna liczba węzłów w pełnym drzewie binarnym wynosi 2^H.
• Minimalna wysokość pełnego drzewa binarnego wynosi dziennik₂(n+1) - 1.
• Maksymalna wysokość pełnego drzewa binarnego wynosi

Idealne drzewo binarne

Drzewo jest idealnym drzewem binarnym, jeśli wszystkie węzły wewnętrzne mają 2 dzieci, a wszystkie węzły liściowe znajdują się na tym samym poziomie.

Spójrzmy na prosty przykład doskonałego drzewa binarnego.

Poniższe drzewo nie jest idealnym drzewem binarnym, ponieważ wszystkie węzły liściowe nie znajdują się na tym samym poziomie.

Uwaga: wszystkie doskonałe drzewa binarne są zarówno kompletnymi drzewami binarnymi, jak i pełnymi drzewami binarnymi, ale odwrotnie nie jest to prawdą, tj. wszystkie kompletne drzewa binarne i pełne drzewa binarne są doskonałymi drzewami binarnymi.

Zdegenerowane drzewo binarne

Zdegenerowane drzewo binarne to drzewo, w którym wszystkie węzły wewnętrzne mają tylko jednego potomka.

Rozumiemy zdegenerowane drzewo binarne na przykładach.

Powyższe drzewo jest zdegenerowanym drzewem binarnym, ponieważ wszystkie węzły mają tylko jedno dziecko. Nazywa się je również drzewem prawostronnym, ponieważ wszystkie węzły mają tylko prawe dziecko.

Powyższe drzewo jest również zdegenerowanym drzewem binarnym, ponieważ wszystkie węzły mają tylko jedno dziecko. Nazywa się je również drzewem przekrzywionym w lewo, ponieważ wszystkie węzły mają tylko lewe dziecko.

Zrównoważone drzewo binarne

Zrównoważone drzewo binarne to drzewo, w którym zarówno lewe, jak i prawe drzewo różnią się co najwyżej o 1. Na przykład: AVL I Drzewa czerwono-czarne są zrównoważonym drzewem binarnym.

Rozumiemy zrównoważone drzewo binarne na przykładach.

Powyższe drzewo jest zrównoważonym drzewem binarnym, ponieważ różnica między lewym i prawym poddrzewem wynosi zero.

Powyższe drzewo nie jest zrównoważonym drzewem binarnym, ponieważ różnica między lewym i prawym poddrzewem jest większa niż 1.

Implementacja drzewa binarnego

Drzewo binarne jest implementowane za pomocą wskaźników. Pierwszy węzeł drzewa jest reprezentowany przez wskaźnik korzenia. Każdy węzeł w drzewie składa się z trzech części, tj. danych, lewego i prawego wskaźnika. Aby utworzyć drzewo binarne, musimy najpierw utworzyć węzeł. Stworzymy węzeł zdefiniowany przez użytkownika, jak pokazano poniżej:

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

W powyższej strukturze dane jest wartością, lewy wskaźnik zawiera adres lewego węzła oraz prawy wskaźnik zawiera adres prawego węzła.

mnożenie macierzy w c

Program drzewa binarnego w 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; } } 

Powyższy kod wywołuje funkcję create() rekurencyjnie i tworzy nowy węzeł przy każdym wywołaniu rekurencyjnym. Po utworzeniu wszystkich węzłów tworzy się binarna struktura drzewa. Proces odwiedzania węzłów nazywany jest przechodzeniem przez drzewo. Istnieją trzy typy przejść używanych do odwiedzania węzła:

• Przeprawa nieuporządkowana
• Przejście w przedsprzedaży
• Przebieg przekazu pocztowego