Menu

Drzewa w C ++: podstawowa terminologia, techniki przechodzenia i typy drzew w C ++

  • Główny
  • Inny
  • Drzewa w C ++: podstawowa terminologia, techniki przechodzenia i typy drzew w C ++

trees c basic terminology

Ten szczegółowy samouczek dotyczący drzew w języku C ++ wyjaśnia typy drzew, techniki przechodzenia po drzewach i podstawową terminologię z obrazami i przykładowymi programami:



W tej serii C ++ do tej pory widzieliśmy liniową strukturę danych zarówno o charakterze statycznym, jak i dynamicznym. Teraz przejdziemy do nieliniowej struktury danych. Pierwsza struktura danych w tej kategorii to „Drzewa”.



Drzewa to nieliniowe hierarchiczne struktury danych. Drzewo to zbiór węzłów połączonych ze sobą „krawędziami”, które są skierowane lub nieukierunkowane. Jeden z węzłów jest oznaczony jako „Węzeł główny”, a pozostałe nazywane są węzłami potomnymi lub węzłami-liśćmi węzła głównego.

Ogólnie każdy węzeł może mieć tyle samo dzieci, ale tylko jeden węzeł nadrzędny.



=> Sprawdź całą serię szkoleń C ++

Drzewo w C ++



Węzły drzewa znajdują się na tym samym poziomie, zwanym węzłami siostrzanymi, albo mogą mieć relację rodzic-dziecko. Węzły z tym samym rodzicem są węzłami siostrzanymi.

Czego się nauczysz:

Drzewa w C ++

Poniżej podano przykładowe drzewo z różnymi częściami.

Drzewo w C ++ z różnymi częściami

Przejdźmy przez definicje niektórych podstawowych terminów, których używamy w odniesieniu do drzew.

  • Węzeł główny: To jest najwyższy węzeł w hierarchii drzewa. Na powyższym diagramie węzeł A jest węzłem głównym. Zwróć uwagę, że węzeł główny nie ma żadnego rodzica.
  • Węzeł liścia: Jest to najniższy węzeł w hierarchii drzewa. Węzły liści to węzły, które nie mają żadnych węzłów podrzędnych. Nazywane są również węzłami zewnętrznymi. Węzły E, F, G, H i C w powyższym drzewie to wszystkie węzły liściowe.
  • Poddrzewo: Poddrzewo reprezentuje różnych potomków węzła, gdy korzeń nie jest pusty. Drzewo zwykle składa się z węzła głównego i jednego lub więcej poddrzew. Na powyższym diagramie (B-E, B-F) i (D-G, D-H) są poddrzewami.
  • Węzeł nadrzędny: Dowolny węzeł z wyjątkiem węzła głównego, który ma węzeł podrzędny i krawędź skierowaną w górę w kierunku rodzica.
  • Węzeł przodek: Jest to dowolny poprzedni węzeł na ścieżce od katalogu głównego do tego węzła. Zwróć uwagę, że root nie ma żadnych przodków. Na powyższym schemacie A i B są przodkami E.
  • Klucz: Reprezentuje wartość węzła.
  • Poziom: Reprezentuje generację węzła. Węzeł główny jest zawsze na poziomie 1. Węzły potomne katalogu głównego znajdują się na poziomie 2, wnuki katalogu głównego na poziomie 3 i tak dalej. Ogólnie każdy węzeł jest na wyższym poziomie niż jego rodzic.
  • Ścieżka: Ścieżka to sekwencja kolejnych krawędzi. Na powyższym schemacie ścieżka do E to A => B-> E.
  • Stopień: Stopień węzła wskazuje liczbę dzieci, które ma węzeł. Na powyższym diagramie stopień B i D wynosi 2, a stopień C wynosi 0.

Rodzaje drzew C ++

Drzewiastą strukturę danych można podzielić na następujące podtypy, jak pokazano na poniższym diagramie.

Rodzaje drzewa w C ++

1) Drzewo ogólne

Drzewo ogólne jest podstawową reprezentacją drzewa. Ma węzeł i co najmniej jeden węzeł podrzędny. Węzeł najwyższego poziomu, tj. Węzeł główny, znajduje się na poziomie 1, a wszystkie inne węzły mogą znajdować się na różnych poziomach.

Drzewo ogólne pokazano na poniższym rysunku.

Drzewo ogólne

Jak pokazano na powyższym rysunku, drzewo ogólne może zawierać dowolną liczbę poddrzew. Węzły B, C i D są obecne na poziomie 2 i są węzłami siostrzanymi. Podobnie, węzły E, F, G i H są również węzłami rodzeńskimi.

Węzły obecne na różnych poziomach mogą wykazywać relację rodzic-dziecko. Na powyższym rysunku węzły B, C i D są dziećmi A. Węzły E i F są dziećmi B, podczas gdy węzły G i H są dziećmi D.

Ogólne drzewo przedstawiono poniżej przy użyciu implementacji C ++:

#include using namespace std; //declaration for new tree node struct node { int data; struct node *left; struct node *right; }; //allocates new node struct node* newNode(int data) { // declare and allocate new node struct node* node = new struct node(); node->data = data; // Assign data to this node // Initialize left and right children as NULL node->left = NULL; node->right = NULL; return(node); } int main() { /*create root node*/ struct node *rootNode = newNode(10); cout<<'General tree created is as follows:'<data<left = newNode(20); rootNode->right = newNode(30); cout<<' '<left->data<<' '<right->data; cout<left->left = newNode(40); cout<<' '<<'/'<left->left->data; return 0; }

Wynik:

Utworzone drzewo ogólne wygląda następująco:

10

/

20 30

/

40

# 2) Lasy

Za każdym razem, gdy usuwamy węzeł główny z drzewa i krawędzie łączące elementy następnego poziomu z korzeniem, otrzymujemy rozłączne zbiory drzew, jak pokazano poniżej.

Lasy

Na powyższym rysunku uzyskaliśmy dwa lasy, usuwając węzeł główny A i trzy krawędzie, które łączyły węzeł główny z węzłami B, C i D.

# 3) Drzewo binarne

Drzewiasta struktura danych, w której każdy węzeł ma co najwyżej dwa węzły potomne, nazywana jest drzewem binarnym. Drzewo binarne jest najpopularniejszą strukturą danych drzewiastych i jest używane w wielu aplikacjach, takich jak ocena wyrażeń, bazy danych itp.

Poniższy rysunek przedstawia drzewo binarne.

Drzewo binarne

Na powyższym rysunku widzimy, że węzły A, B i D mają po dwoje dzieci. Drzewo binarne, w którym każdy węzeł ma dokładnie zero lub dwoje dzieci, nazywane jest pełnym drzewem binarnym. W tym drzewie nie ma węzłów, które mają jedno dziecko.

Kompletne drzewo binarne ma drzewo binarne, które jest całkowicie wypełnione, z wyjątkiem najniższego poziomu, który jest wypełniony od lewej do prawej. Drzewo binarne pokazane powyżej jest pełnym drzewem binarnym.

Poniżej znajduje się prosty program do zademonstrowania drzewa binarnego. Zauważ, że wynikiem drzewa jest wewnętrzna sekwencja przechodzenia drzewa wejściowego.

#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

4.Binarne drzewo wyszukiwania

Uporządkowane drzewo binarne nazywane jest drzewem wyszukiwania binarnego. W drzewie wyszukiwania binarnego węzły po lewej stronie są mniejsze niż węzeł główny, podczas gdy węzły po prawej stronie są większe lub równe węzłowi głównemu.

Poniżej pokazano przykład drzewa wyszukiwania binarnego.

Drzewo wyszukiwania binarnego

Na powyższym rysunku widzimy, że wszystkie lewe węzły mają mniej niż 20, co jest elementem głównym. Z drugiej strony, prawe węzły są większe niż węzeł główny. Binarne drzewo wyszukiwania jest używane w technikach wyszukiwania i sortowania.

co to jest plik torrent i jak go otworzyć

# 5) Drzewo wyrażeń

Drzewo binarne, które służy do oceny prostych wyrażeń arytmetycznych, nazywane jest drzewem wyrażeń.

Poniżej pokazano proste drzewo wyrażeń.

Drzewo wyrażeń

W powyższym przykładowym drzewie wyrażeń reprezentujemy wyrażenie (a + b) / (a-b). Jak pokazano na powyższym rysunku, węzły nie będące liśćmi drzewa reprezentują operatory wyrażenia, podczas gdy węzły liści reprezentują operandy.

Drzewa wyrażeń są używane głównie do rozwiązywania wyrażeń algebraicznych.

Techniki przechodzenia po drzewie

Widzieliśmy liniowe struktury danych, takie jak tablice, połączone listy, stosy, kolejki itp. Wszystkie te struktury danych mają wspólną technikę przechodzenia, która przechodzi przez strukturę tylko w jeden sposób, tj. Liniowo.

Ale w przypadku drzew mamy różne techniki przechodzenia, wymienione poniżej:

# 1) W kolejności: W tej technice przechodzenia najpierw przechodzimy przez lewe poddrzewo, aż nie będzie już żadnych węzłów w lewym poddrzewie. Następnie odwiedzamy węzeł główny, a następnie przechodzimy do przejścia przez prawe poddrzewo, aż nie będzie już żadnych węzłów do przejścia w prawym poddrzewie. Tak więc kolejność przechodzenia inOrder to left-> root-> right.

# 2) Przedsprzedaż: W przypadku techniki przechodzenia przed zamówieniem najpierw przetwarzamy węzeł główny, następnie przechodzimy przez całe lewe poddrzewo i na koniec przechodzimy przez prawe poddrzewo. Stąd kolejność przechodzenia przed zamówieniem jest następująca: root-> left-> right.

# 3) Zamówienie końcowe: W technice przechodzenia po zamówieniu przechodzimy przez lewe poddrzewo, następnie prawe poddrzewo i na końcu węzeł główny. Kolejność przechodzenia w technice zamówienia pocztowego to left-> right-> root.

Jeśli n jest węzłem głównym, a „l” i „r” są odpowiednio lewym i prawym węzłem drzewa, to algorytmy przechodzenia po drzewie są następujące:

W kolejności (lnr) algorytm:

  1. Przejdź przez lewe poddrzewo za pomocą inOrder (lewe poddrzewo).
  2. Odwiedź węzeł główny (n).
  3. Przejdź przez prawe poddrzewo za pomocą inOrder (prawe poddrzewo).

Algorytm zamówienia w przedsprzedaży (nlr):

  1. Odwiedź węzeł główny (n).
  2. Przechodzenie przez lewe poddrzewo przy użyciu zamówienia w przedsprzedaży (lewe poddrzewo).
  3. Przejdź przez prawe poddrzewo za pomocą zamówienia przedpremierowego (prawe poddrzewo).

Algorytm zamówienia pocztowego (lrn):

  1. Przejdź przez lewe poddrzewo za pomocą postOrder (lewe poddrzewo).
  2. Przejdź przez prawe poddrzewo za pomocą postOrder (prawe poddrzewo).
  3. Odwiedź węzeł główny (n).

Z powyższych algorytmów technik przechodzenia widzimy, że techniki te można zastosować do danego drzewa w sposób rekurencyjny, aby uzyskać pożądany wynik.

Rozważmy następujące drzewo.

Algorytm zamówienia pocztowego (lrn)

Korzystając z powyższych technik przechodzenia, sekwencję przechodzenia dla powyższego drzewa podano poniżej:

  1. Przechodzenie w ramach zamówienia: 2 3 5 6 10
  2. Przechodzenie przed zamówieniem: 6 3 2 5 10
  3. Przechodzenie przez PostOrder: 2 5 3 10 6

Wniosek

Drzewa to nieliniowa hierarchiczna struktura danych, która jest używana w wielu aplikacjach w dziedzinie oprogramowania.

W przeciwieństwie do liniowych struktur danych, które mają tylko jeden sposób przechodzenia przez listę, możemy przemierzać drzewa na różne sposoby. W tym samouczku szczegółowo przeanalizowaliśmy techniki przechodzenia i różne typy drzew.

=> Zapoznaj się z przewodnikiem C ++ dla początkujących tutaj

rekomendowane lektury

^