Menu

Struktura danych drzewa binarnego w C ++

binary tree data structure c

Wypróbuj Nasz Instrument Do Eliminowania Problemów

Ten szczegółowy samouczek dotyczący drzewa binarnego w C ++ wyjaśnia typy, reprezentację, przemierzanie, aplikacje i implementację drzew binarnych w C ++:

Drzewo binarne to szeroko stosowana struktura danych drzewiastych. Gdy każdy węzeł drzewa ma co najwyżej dwa węzły potomne, wówczas drzewo nazywane jest drzewem binarnym.

Tak więc typowe drzewo binarne będzie miało następujące komponenty:

  • Lewe poddrzewo
  • Węzeł główny
  • Właściwe poddrzewo

=> Obejrzyj pełną listę samouczków C ++ z tej serii.

Drzewo binarne w C ++

Czego się nauczysz:

Drzewo binarne w C ++

Obrazowe przedstawienie drzewa binarnego pokazano poniżej:

Graficzne przedstawienie drzewa binarnego

W danym drzewie binarnym maksymalna liczba węzłów na dowolnym poziomie to 2l-1gdzie „l” to numer poziomu.

Zatem w przypadku węzła głównego na poziomie 1 maksymalna liczba węzłów = 21-1= 20= 1

Ponieważ każdy węzeł w drzewie binarnym ma co najwyżej dwa węzły, maksymalna liczba węzłów na następnym poziomie będzie wynosić 2 * 2l-1.

najlepszy darmowy program do pobierania filmów z YouTube na system Windows 10

Biorąc pod uwagę drzewo binarne o głębokości lub wysokości h, maksymalna liczba węzłów w drzewie binarnym o wysokości h = 2godz- 1.

Stąd w drzewie binarnym o wysokości 3 (pokazane powyżej) maksymalna liczba węzłów = 23-1 = 7.

Omówmy teraz różne typy drzew binarnych.

Rodzaje drzew binarnych

Poniżej przedstawiono najpopularniejsze typy drzew binarnych.

# 1) Pełne drzewo binarne

Drzewo binarne, w którym każdy węzeł ma 0 lub 2 dzieci, jest określane jako pełne drzewo binarne.

Pełne drzewo binarne

Powyżej pokazano pełne drzewo binarne, w którym widzimy, że wszystkie jego węzły z wyjątkiem węzłów liści mają dwoje dzieci. Jeśli L to liczba węzłów liściowych, a „l” to liczba węzłów wewnętrznych lub innych niż liście, to dla pełnego drzewa binarnego L = l + 1.

# 2) Pełne drzewo binarne

Kompletne drzewo binarne ma wypełnione wszystkie poziomy z wyjątkiem ostatniego poziomu, a ostatni poziom ma wszystkie węzły po lewej stronie.

Kompletne drzewo binarne

Drzewo pokazane powyżej jest kompletnym drzewem binarnym. Typowym przykładem pełnego drzewa binarnego jest stos binarny, który omówimy w późniejszych tutorialach.

# 3) Doskonałe drzewo binarne

Drzewo binarne określa się jako idealne, gdy wszystkie jego wewnętrzne węzły mają dwoje dzieci, a wszystkie węzły liści są na tym samym poziomie.

Idealne drzewo binarne

Pokazany powyżej przykład drzewa binarnego jest doskonałym drzewem binarnym, ponieważ każdy z jego węzłów ma dwoje dzieci, a wszystkie węzły liści są na tym samym poziomie.

Idealne drzewo binarne o wysokości h ma 2godz- 1 liczba węzłów.

# 4) Zdegenerowane drzewo

Drzewo binarne, w którym każdy węzeł wewnętrzny ma tylko jedno dziecko, nazywane jest drzewem zdegenerowanym.

Zdegenerowane drzewo

Drzewo pokazane powyżej jest drzewem zdegenerowanym. Jeśli chodzi o wydajność tego drzewa, zdegenerowane drzewa są takie same jak połączone listy.

# 5) Zrównoważone drzewo binarne

Drzewo binarne, w którym głębokość dwóch poddrzew każdego węzła nigdy nie różni się o więcej niż 1, nazywane jest zrównoważonym drzewem binarnym.

Zrównoważone drzewo binarne

Drzewo binarne pokazane powyżej jest zrównoważonym drzewem binarnym, ponieważ głębokość dwóch poddrzew każdego węzła nie przekracza 1. Drzewa AVL, które będziemy omawiać w naszych kolejnych samouczkach, są wspólnym drzewem zrównoważonym.

Reprezentacja drzewa binarnego

Drzewo binarne ma przydzieloną pamięć na dwa sposoby.

# 1) Reprezentacja sekwencyjna

Jest to najprostsza technika przechowywania drzewiastej struktury danych. Tablica służy do przechowywania węzłów drzewa. Liczba węzłów w drzewie określa rozmiar tablicy. Węzeł główny drzewa jest przechowywany w pierwszym indeksie tablicy.

Ogólnie rzecz biorąc, jeśli węzeł jest przechowywany w ithlokalizacja to lewe i prawe dziecko jest przechowywane odpowiednio w lokalizacji 2i i 2i + 1.

Rozważmy następujące drzewo binarne.

Przykładowe drzewo binarne

Sekwencyjna reprezentacja powyższego drzewa binarnego jest następująca:

sekwencyjna reprezentacja drzewa binarnego

W powyższej reprezentacji widzimy, że lewe i prawe dziecko każdego węzła jest przechowywane odpowiednio w lokalizacjach 2 * (lokalizacja_węzła) i 2 * (lokalizacja_węzła) +1.

Na przykład, lokalizacja węzła 3 w tablicy to 3. Więc jego lewe dziecko zostanie umieszczone w 2 * 3 = 6. Jego prawe dziecko będzie w lokalizacji 2 * 3 +1 = 7. Jak widać na tablicy, dzieci z 3, czyli 6 i 7, są umieszczane w miejscach 6 i 7 w szyku.

Sekwencyjna reprezentacja drzewa jest nieefektywna, ponieważ tablica używana do przechowywania węzłów drzewa zajmuje dużo miejsca w pamięci. W miarę wzrostu drzewa reprezentacja ta staje się nieefektywna i trudna w zarządzaniu.

Wadę tę można wyeliminować, przechowując węzły drzewa na połączonej liście. Zwróć uwagę, że jeśli drzewo jest puste, pierwsza lokalizacja przechowująca węzeł główny zostanie ustawiona na 0.

# 2) Reprezentacja listy powiązanej

W tego typu reprezentacji do przechowywania węzłów drzewa używana jest połączona lista. Kilka węzłów jest rozproszonych w pamięci w nieciągłych lokalizacjach, a węzły są połączone za pomocą relacji rodzic-dziecko, jak drzewo.

Poniższy diagram przedstawia połączoną reprezentację listy dla drzewa.

Reprezentacja listy połączonej

najlepszy darmowy program do pobierania filmów z YouTube na system Windows 10

Jak pokazano na powyższej ilustracji, każdy połączony węzeł listy ma trzy komponenty:

  • Lewy wskaźnik
  • Część danych
  • Prawy wskaźnik

Lewy wskaźnik ma wskaźnik do lewego dziecka węzła; prawy wskaźnik ma wskaźnik do prawego dziecka węzła, podczas gdy część danych zawiera rzeczywiste dane węzła. Jeśli nie ma dzieci dla danego węzła (węzła liścia), wówczas lewy i prawy wskaźnik dla tego węzła są ustawiane na null, jak pokazano na powyższym rysunku.

Implementacja drzewa binarnego w C ++

Następnie tworzymy program drzewa binarnego, używając połączonej reprezentacji listy w C ++. Używamy struktury do zadeklarowania pojedynczego węzła, a następnie za pomocą klasy opracowujemy połączoną listę węzłów.

#include using namespace std; struct bintree_node{ bintree_node *left; bintree_node *right; int data; } ; class bst{ bintree_node *root; public: bst(){ root=NULL; } int isempty() { return(root==NULL); } void insert(int item); void displayBinTree(); void printBinTree(bintree_node *); }; void bst::insert(int item){ bintree_node *p=new bintree_node; bintree_node *parent; p->data=item; p->left=NULL; p->right=NULL; parent=NULL; if(isempty()) root=p; else{ bintree_node *ptr; ptr=root; while(ptr!=NULL){ parent=ptr; if(item>ptr->data) ptr=ptr->right; else ptr=ptr->left; } if(itemdata) parent->left=p; else parent->right=p; } } void bst::displayBinTree(){ printBinTree(root); } void bst::printBinTree(bintree_node *ptr){ if(ptr!=NULL){ printBinTree(ptr->left); cout<<' '<data<<' '; printBinTree(ptr->right); } } int main(){ bst b; b.insert(20); b.insert(10); b.insert(5); b.insert(15); b.insert(40); b.insert(45); b.insert(30); cout<<'Binary tree created: '<

Wynik:

Utworzono drzewo binarne:

5 10 15 20 30 40 45

Przechodzenie po drzewie binarnym

Omówiliśmy już przemierzanie w naszym podstawowym samouczku dotyczącym drzew. W tej sekcji zaimplementujmy program, który wstawia węzły do ​​drzewa binarnego, a także demonstruje wszystkie trzy przejścia, tj. Inorder, preorder i postorder, dla drzewa binarnego.

#include using namespace std; //binary tree node declaration struct bintree_node{ bintree_node *left; bintree_node *right; char data; } ; class bintree_class{ bintree_node *root; public: bintree_class(){ root=NULL; } int isempty() { return(root==NULL); } void insert_node(int item); void inorder_seq(); void inorder(bintree_node *); void postorder_seq(); void postorder(bintree_node *); void preorder_seq(); void preorder(bintree_node *); }; void bintree_class::insert_node(int item){ bintree_node *p=new bintree_node; bintree_node *parent; p->data=item; p->left=NULL; p->right=NULL; parent=NULL; if(isempty()) root=p; else{ bintree_node *ptr; ptr=root; while(ptr!=NULL) { parent=ptr; if(item>ptr->data) ptr=ptr->right; else ptr=ptr->left; } if(itemdata) parent->left=p; else parent->right=p; } } void bintree_class::inorder_seq() { inorder(root); } void bintree_class::inorder(bintree_node *ptr) { if(ptr!=NULL){ inorder(ptr->left); cout<<' '<data<<' '; inorder(ptr->right); } } void bintree_class::postorder_seq() { postorder(root); } void bintree_class::postorder(bintree_node *ptr) { if(ptr!=NULL){ postorder(ptr->left); postorder(ptr->right); cout<<' '<data<<' '; } } void bintree_class::preorder_seq() { preorder(root); } void bintree_class::preorder(bintree_node *ptr) { if(ptr!=NULL){ cout<<' '<data<<' '; preorder(ptr->left); preorder(ptr->right); } } int main() { bintree_class bintree; bintree.insert_node('A'); bintree.insert_node('B'); bintree.insert_node('C'); bintree.insert_node('D'); bintree.insert_node('E'); bintree.insert_node('F'); bintree.insert_node('G'); cout<<'Inorder traversal:'<

Wynik:

Przechodzenie w kolejności:

A B C D E F G.

Przechodzenie do zamówień pocztowych:

G F E D C B A

Przechodzenie w przedsprzedaży:

A B C D E F G.

Zastosowania drzewa binarnego

Drzewo binarne jest używane w wielu aplikacjach do przechowywania danych.

Poniżej wymieniono niektóre z ważnych zastosowań drzew binarnych:

  • Binarne drzewa wyszukiwania: Drzewa binarne są używane do konstruowania binarnego drzewa wyszukiwania, które jest używane w wielu aplikacjach do wyszukiwania, takich jak zbiory i mapy w wielu bibliotekach językowych.
  • Hash Drzewa: Służy do weryfikacji skrótów głównie w wyspecjalizowanych aplikacjach do podpisywania obrazów.
  • Stosy: Sterty są używane do implementowania kolejek priorytetowych, które są używane przez routery, procesory planowania w systemie operacyjnym itp.
  • Kodowanie Huffmana: Drzewo kodowania Huffmana jest wykorzystywane w algorytmach kompresji (takich jak kompresja obrazu), a także w zastosowaniach kryptograficznych.
  • Drzewo składniowe: Kompilatory często konstruują drzewa składniowe, które są niczym innym jak drzewami binarnymi do analizowania wyrażeń używanych w programie.

Wniosek

Drzewa binarne są szeroko stosowanymi strukturami danych w branży oprogramowania. Drzewa binarne to drzewa, których węzły mają co najwyżej dwa węzły potomne. Widzieliśmy różne typy drzew binarnych, takie jak pełne drzewo binarne, pełne drzewo binarne, doskonałe drzewo binarne, zdegenerowane drzewo binarne, zrównoważone drzewo binarne itp.

Dane drzew binarnych można również przemierzać przy użyciu technik przechodzenia w kolejności, zamówienia przed i po zamówieniu, które widzieliśmy w naszym poprzednim samouczku. W pamięci drzewo binarne można przedstawić za pomocą połączonej listy (nieciągłej pamięci) lub tablic (reprezentacja sekwencyjna).

Reprezentacja listy połączonej jest bardziej wydajna w porównaniu z tablicami, ponieważ zajmują dużo miejsca.

=> Sprawdź najlepsze samouczki szkoleniowe C ++ tutaj.

rekomendowane lektury

^