logo

TechCodeview

Techniki przechodzenia przez drzewa - samouczki dotyczące struktury danych i algorytmów

Techniki przechodzenia przez drzewa obejmują różne sposoby odwiedzania wszystkich węzłów drzewa. W przeciwieństwie do liniowych struktur danych (tablica, lista połączona, kolejki, stosy itp.), które mają tylko jeden logiczny sposób przechodzenia przez nie, drzewa można przemierzać na różne sposoby. W tym artykule omówimy wszystkie techniki przechodzenia przez drzewa wraz z ich zastosowaniami.



Spis treści

Znaczenie przechodzenia przez drzewo:

Przejście przez drzewo odnosi się do procesu odwiedzania lub uzyskiwania dostępu do każdego węzła drzewa dokładnie raz w określonej kolejności. Algorytmy przechodzenia przez drzewo pomagają nam odwiedzać i przetwarzać wszystkie węzły drzewa. Ponieważ drzewo nie jest liniową strukturą danych, istnieje wiele węzłów, które możemy odwiedzić po odwiedzeniu określonego węzła. Istnieje wiele technik przechodzenia przez drzewo, które decydują o kolejności odwiedzania węzłów drzewa.

Techniki przechodzenia przez drzewa:



Strukturę danych drzewa można przeglądać na następujące sposoby:

Java wykonaj while
  • Głębokość pierwszego wyszukiwania lub DFS
    • Przeprawa nieuporządkowana
    • Zamów w przedsprzedaży
    • Przesyłka pocztowa
  • Przechodzenie według kolejności poziomów lub przeszukiwanie wszerz lub BFS

Przeprawa nieuporządkowana :

Inorder Traversal odwiedza węzeł w kolejności: Lewo -> Korzeń -> Prawo




Algorytm przejścia nieuporządkowanego:

Nieporządek (drzewo)

  • Przejdź przez lewe poddrzewo, tj. wywołaj Inorder(left->subtree)
  • Odwiedź korzeń.
  • Przejdź przez prawe poddrzewo, tj. wywołaj Inorder(right->subtree)

Zastosowania Inorder Traversal:

  • W przypadku drzew wyszukiwania binarnego (BST) przechodzenie Inorder daje węzły w kolejności niemalejącej.
  • Aby uzyskać węzły BST w porządku nierosnącym, można zastosować odmianę przechodzenia Inorder, w której przechodzenie Inorder jest odwrócone.
  • Przechodzenie w kolejności może być użyte do oceny wyrażeń arytmetycznych przechowywanych w drzewach wyrażeń.

Fragment kodu dla przechodzenia w kolejności:

C++ 
// Given a binary tree, print its nodes in inorder void printInorder(struct Node* node) {  if (node == NULL)  return;  // First recur on left child  printInorder(node->lewy);  // Następnie wydrukuj dane węzła cout<< node->dane<< ' ';  // Now recur on right child  printInorder(node->Prawidłowy); }>
C 
// Given a binary tree, print its nodes in inorder void printInorder(struct node* node) {  if (node == NULL)  return;  // First recur on left child  printInorder(node->lewy);  // Następnie wypisz dane węzła printf('%d ', węzeł->dane);  // Teraz powtórz prawe dziecko printInorder(node->right); }>
Jawa 
void printInorder(Node node) {  if (node == null)  return;  // First recur on left child  printInorder(node.left);  // Then print the data of node  System.out.print(node.key + ' ');  // Now recur on right child  printInorder(node.right); }>
Python3 
# A function to do inorder tree traversal def printInorder(root): if root: # First recur on left child printInorder(root.left) # Then print the data of node print(root.val, end=' '), # Now recur on right child printInorder(root.right)>
C# 
// Given a binary tree, print // its nodes in inorder void printInorder(Node node) {  if (node == null)  return;  // First recur on left child  printInorder(node.left);  // Then print the data of node  Console.Write(node.key + ' ');  // Now recur on right child  printInorder(node.right); }>
JavaScript 
// Given a binary tree, print its nodes in inorder function printInorder(node) {  if (node == null)  return;  // First recur on left child */  printInorder(node.left);  // Then print the data of node  console.log(node.key + ' ');  // Now recur on right child  printInorder(node.right); }>
Wyjście 
Inorder traversal of binary tree is 4 2 5 1 3>

Złożoność czasowa: NA)
Przestrzeń pomocnicza: Jeśli nie bierzemy pod uwagę rozmiaru stosu dla wywołań funkcji, to O(1) w przeciwnym razie O(h), gdzie h jest wysokością drzewa.

Zamów w przedsprzedaży :

Przejście w przedsprzedaży odwiedza węzeł w kolejności: Korzeń -> Lewy -> Prawy

gimp zapisuje jako JPEG

Algorytm przeglądania zamówień w przedsprzedaży:

Zamów w przedsprzedaży (drzewo)

  • Odwiedź korzeń.
  • Przejdź przez lewe poddrzewo, tj. wywołaj Preorder(left->subtree)
  • Przejdź przez prawe poddrzewo, tj. wywołaj Preorder(right->poddrzewo)

Zastosowania przeglądania zamówień w przedsprzedaży:

  • Przechodzenie w przedsprzedaży służy do tworzenia kopii drzewa.
  • Przechodzenie w przedsprzedaży służy również do uzyskiwania wyrażeń przedrostkowych w drzewie wyrażeń.

Fragment kodu umożliwiający przeglądanie zamówień w przedsprzedaży:

C++ 
// Given a binary tree, print its nodes in preorder void printPreorder(struct Node* node) {  if (node == NULL)  return;  // First print data of node  cout << node->dane<< ' ';  // Then recur on left subtree  printPreorder(node->lewy);  // Teraz powtórz w prawym poddrzewie printPreorder(node->right); }>
C 
// Given a binary tree, print its nodes in preorder void printPreorder(struct node* node) {  if (node == NULL)  return;  // First print data of node  printf('%d ', node->dane);  // Następnie powtórz w lewym poddrzewie printPreorder(node->left);  // Teraz powtórz w prawym poddrzewie printPreorder(node->right); }>
Jawa 
// Given a binary tree, print its nodes in preorder void printPreorder(Node node) {  if (node == null)  return;  // First print data of node  System.out.print(node.key + ' ');  // Then recur on left subtree  printPreorder(node.left);  // Now recur on right subtree  printPreorder(node.right); }>
Python3 
# A function to do preorder tree traversal def printPreorder(root): if root: # First print the data of node print(root.val, end=' '), # Then recur on left child printPreorder(root.left) # Finally recur on right child printPreorder(root.right)>
C# 
// Given a binary tree, print // its nodes in preorder void printPreorder(Node node) {  if (node == null)  return;  // First print data of node  Console.Write(node.key + ' ');  // Then recur on left subtree  printPreorder(node.left);  // Now recur on right subtree  printPreorder(node.right); }>
JavaScript 
// Given a binary tree, print its nodes in preorder function printPreorder(node) {  if (node == null)  return;  // First print data of node  document.write(node.key + ' ');  // Then recur on left subtree  printPreorder(node.left);  // Now recur on right subtree  printPreorder(node.right); }>
Wyjście 
Preorder traversal of binary tree is 1 2 4 5 3>

Złożoność czasowa: NA)
Przestrzeń pomocnicza: Jeśli nie bierzemy pod uwagę rozmiaru stosu dla wywołań funkcji, to O(1) w przeciwnym razie O(h), gdzie h jest wysokością drzewa.

Przesyłka pocztowa :

Przechodzenie postordera odwiedza węzeł w kolejności: Lewo -> Prawo -> Korzeń

Algorytm przechodzenia przekazem pocztowym:

Algorytm Przekaz pocztowy (drzewo)

  • Przejdź przez lewe poddrzewo, tj. wywołaj Postorder(left->subtree)
  • Przejdź przez prawe poddrzewo, tj. wywołaj Postorder(prawe->poddrzewo)
  • Odwiedź korzeń

Zastosowania przeglądania przesyłek pocztowych:

  • Przechodzenie postordera służy do usuwania drzewa. Widzieć pytanie o usunięcie drzewa dla szczegółów.
  • Przechodzenie postordera jest również przydatne do uzyskania wyrażenia postfiksowego drzewa wyrażeń.
  • Przechodzenie po zamówieniu może pomóc w algorytmach usuwania śmieci, szczególnie w systemach, w których stosowane jest ręczne zarządzanie pamięcią.

Fragment kodu umożliwiający przeglądanie przesyłek pocztowych:

C++ 
// Given a binary tree, print its nodes according to the // 'bottom-up' postorder traversal. void printPostorder(struct Node* node) {  if (node == NULL)  return;  // First recur on left subtree  printPostorder(node->lewy);  // Następnie powtórz w prawym poddrzewie printPostorder(node->right);  // Teraz zajmij się węzłem cout<< node->dane<< ' '; }>
C 
// Given a binary tree, print its nodes according to the // 'bottom-up' postorder traversal. void printPostorder(struct node* node) {  if (node == NULL)  return;  // First recur on left subtree  printPostorder(node->lewy);  // Następnie powtórz w prawym poddrzewie printPostorder(node->right);  // Teraz zajmij się węzłem printf('%d ', węzeł->dane); }>
Jawa 
// Given a binary tree, print its nodes according to the // 'bottom-up' postorder traversal. void printPostorder(Node node) {  if (node == null)  return;  // First recur on left subtree  printPostorder(node.left);  // Then recur on right subtree  printPostorder(node.right);  // Now deal with the node  System.out.print(node.key + ' '); }>
Python3 
# A function to do postorder tree traversal def printPostorder(root): if root: # First recur on left child printPostorder(root.left) # The recur on right child printPostorder(root.right) # Now print the data of node print(root.val, end=' '),>
C# 
// Given a binary tree, print its nodes according to // the 'bottom-up' postorder traversal. void printPostorder(Node node) {  if (node == null)  return;  // First recur on left subtree  printPostorder(node.left);  // Then recur on right subtree  printPostorder(node.right);  // Now deal with the node  Console.Write(node.key + ' '); }>
JavaScript 
// Given a binary tree, print its nodes according  // to the 'bottom-up' postorder traversal function printPostorder(node) {  if (node == null)  return;  // First recur on left subtree  printPostorder(node.left);  // Then recur on right subtree  printPostorder(node.right);  // Now deal with the node  console.log(node.key + ' '); }>
Wyjście 
Postorder traversal of binary tree is 4 5 2 3 1>

Przechodzenie przez poziom zamówienia :

Przechodzenie przez poziom zamówienia odwiedza w całości wszystkie węzły obecne na tym samym poziomie przed odwiedzeniem następnego poziomu.

Algorytm przechodzenia przez kolejność poziomów:

PoziomZamówienie(drzewo)

  • Utwórz pustą kolejkę Q
  • Kolejkuj węzeł główny drzewa do Q
  • Zapętlaj, gdy Q nie jest puste
    • Usuń z kolejki węzeł z Q i odwiedź go
    • Umieść w kolejce lewe dziecko usuniętego węzła, jeśli istnieje
    • Umieść w kolejce prawe dziecko usuniętego węzła, jeśli istnieje

Zastosowania kolejności poziomów:

  • Przeszukiwanie kolejności poziomów jest używane głównie jako przeszukiwanie wszerz w celu przeszukiwania lub przetwarzania węzłów poziom po poziomie.
  • Przechodzenie przez kolejność poziomów jest również wykorzystywane do Serializacja i deserializacja drzewa .

Fragment kodu umożliwiający przechodzenie przez kolejność poziomów:

C++ 
// Iterative method to find height of Binary Tree void printLevelOrder(Node* root) {  // Base Case  if (root == NULL)  return;  // Create an empty queue for level order traversal  queueQ;  // Umieść w kolejce katalog główny i zainicjuj wysokość q.push(root);  while (q.empty() == false) { // Wydrukuj początek kolejki i usuń go z kolejki Węzeł* węzeł = q.front();  cout<< node->dane<< ' ';  q.pop();  // Enqueue left child  if (node->lewo != NULL) q.push(węzeł->lewo);  // Umieść w kolejce prawe dziecko if (node->right != NULL) q.push(node->right);  } }>
C 
// Given a binary tree, print its nodes in level order // using array for implementing queue void printLevelOrder(struct node* root) {  int rear, front;  struct node** queue = createQueue(&front, &rear);  struct node* temp_node = root;  while (temp_node) {  printf('%d ', temp_node->dane);  // Umieść w kolejce lewe dziecko if (temp_node->left) enQueue(queue, &rear, temp_node->left);  // Umieść w kolejce prawe dziecko if (temp_node->right) enQueue(queue, &rear, temp_node->right);  // Usuń węzeł z kolejki i ustaw go jako temp_node temp_node = deQueue(queue, &front);  } }>
Jawa 
// Given a binary tree. Print // its nodes in level order // using array for implementing queue void printLevelOrder() {  Queuekolejka = nowa lista połączona();  kolejka.add(root);  while (!queue.isEmpty()) { // poll() usuwa bieżący nagłówek.  Węzeł tempNode = kolejka.poll();  System.out.print(tempNode.data + ' ');  // Umieść w kolejce lewe dziecko if (tempNode.left != null) { kolejka.add(tempNode.left);  } // Umieść w kolejce prawe dziecko if (tempNode.right != null) { kolejka.add(tempNode.right);  } } }>
Python3 
# Iterative Method to print the # height of a binary tree def printLevelOrder(root): # Base Case if root is None: return # Create an empty queue # for level order traversal queue = [] # Enqueue Root and initialize height queue.append(root) while(len(queue)>0): # Wydrukuj początek kolejki i # usuń go z kolejki print(queue[0].data, end=' ') node = kolejka.pop(0) # Umieść w kolejce lewe dziecko, jeśli node.left nie jest Brak: kolejka.append(node.left) # Umieść w kolejce prawe dziecko, jeśli node.right nie ma wartości Brak: kolejka.append(node.right)>
C# 
// Given a binary tree. Print // its nodes in level order using // array for implementing queue void printLevelOrder() {  Queuekolejka = nowa kolejka();  kolejka.Enqueue(root);  while (queue.Count != 0) { Węzeł tempNode = kolejka.Dequeue();  Console.Write(tempNode.data + ' ');  // Umieść w kolejce lewe dziecko if (tempNode.left != null) { kolejka.Enqueue(tempNode.left);  } // Umieść w kolejce prawe dziecko if (tempNode.right != null) { kolejka.Enqueue(tempNode.right);  } } }>
JavaScript 
// Function to perform level order traversal of a binary tree function printLevelOrder(root) {  // Create a deque to store nodes for traversal  const queue = new Deque();  // Add the root node to the queue  queue.enqueue(root);  // Continue traversal until the queue is empty  while (!queue.isEmpty()) {  // Remove and get the first node from the queue  const tempNode = queue.dequeue();  // Print the data of the current node  console.log(tempNode.data + ' ');  // Enqueue the left child if it exists  if (tempNode.left !== null) {  queue.enqueue(tempNode.left);  }  // Enqueue the right child if it exists  if (tempNode.right !== null) {  queue.enqueue(tempNode.right);  }  } }>

Inne przejścia przez drzewa:

  1. Przekroczenie granicy
  2. Przejście po przekątnej

1. Przekroczenie granicy :

Przekroczenie granicy drzewa obejmuje:

  • lewa granica (węzły po lewej stronie, z wyłączeniem węzłów liściowych)
  • liście (składają się tylko z węzłów liściowych)
  • prawa granica (węzły po prawej stronie, z wyłączeniem węzłów liściowych)

Algorytm przekraczania granicy:

Przejście granicy (drzewo)

sformatuj datę na ciąg
  • Jeśli root nie ma wartości null:
    • Wydrukuj dane roota
    • PrintLeftBoundary(root->left) // Wydrukuj lewe węzły graniczne
    • PrintLeafNodes(root->left) // Wydrukuj węzły liści lewego poddrzewa
    • PrintLeafNodes(root->right) // Wydrukuj węzły-liście prawego poddrzewa
    • PrintRightBoundary(root->right) // Wydrukuj prawe węzły graniczne

Zastosowania przekraczania granic:

  • Przechodzenie przez granice pomaga w wizualizacji zewnętrznej struktury drzewa binarnego, zapewniając wgląd w jego kształt i granice.
  • Przechodzenie przez granicę umożliwia dostęp do tych węzłów i ich modyfikowanie, umożliwiając operacje takie jak przycinanie lub zmiana położenia węzłów granicznych.

2. Przejście po przekątnej

W przypadku przechodzenia drzewa po przekątnej wszystkie węzły na jednej przekątnej zostaną wydrukowane jeden po drugim.

Algorytm przejścia po przekątnej:

Przejście po przekątnej(drzewo):

  • Jeśli root nie ma wartości null:
    • Utwórz pustą mapę
    • DiagonalTraversalUtil(root, 0, M) // Wywołanie funkcji pomocniczej z początkowym poziomem przekątnej 0
    • Dla każdej pary klucz-wartość (diagonalLevel, węzły) w M:
      • Dla każdego węzła w węzłach:
      • Wydrukuj dane węzła

DiagonalTraversalUtil(węzeł, diagonalLevel, M):

  • Jeśli węzeł ma wartość null:
  • Powrót
  • Jeśli diagonalLevel nie występuje w M:
    • Utwórz nową listę w M dla diagonalLevel
  • Dołącz dane węzła do listy na M[diagonalLevel]
  • DiagonalTraversalUtil(node->left, diagonalLevel + 1, M) // Przemierzaj lewe dziecko ze zwiększonym poziomem przekątnej
  • DiagonalTraversalUtil(node->right, diagonalLevel, M) // Przemierzaj prawe dziecko z tym samym poziomem przekątnej

Zastosowania przechodzenia po przekątnej:

  • Przechodzenie po przekątnej pomaga w wizualizacji hierarchicznej struktury drzew binarnych, szczególnie w strukturach danych opartych na drzewach, takich jak drzewa wyszukiwania binarnego (BST) i drzewa sterty.
  • Przechodzenie po przekątnej można wykorzystać do obliczenia sum ścieżek wzdłuż przekątnych w drzewie binarnym.

Często zadawane pytania (FAQ) dotyczące technik przechodzenia przez drzewa:

1. Jakie są techniki przechodzenia przez drzewa?

Techniki przechodzenia przez drzewo to metody używane do odwiedzania i przetwarzania wszystkich węzłów w drzewiastej strukturze danych. Umożliwiają one dostęp do każdego węzła dokładnie raz, w sposób systematyczny.

2. Jakie są najczęstsze rodzaje przechodzenia przez drzewa?

Typowe typy przechodzenia przez drzewo to: przechodzenie w kolejności, przechodzenie w kolejności wstępnej, przechodzenie w kolejności późniejszej, przechodzenie w kolejności poziomów (przeszukiwanie wszerz)

3. Czym jest przejście Inorder?

Przechodzenie w kolejności to metoda przechodzenia w głąb, w której węzły odwiedzane są w kolejności: lewe poddrzewo, bieżący węzeł, prawe poddrzewo.

4. Na czym polega przeglądanie zamówień w przedsprzedaży?

Przechodzenie w przedsprzedaży to metoda przechodzenia w głąb, w której węzły są odwiedzane w kolejności: bieżący węzeł, lewe poddrzewo, prawe poddrzewo.

5. Na czym polega obieg przekazu pocztowego?

Przechodzenie postorderowe to metoda przechodzenia w głąb, w której węzły są odwiedzane w kolejności: lewe poddrzewo, prawe poddrzewo, bieżący węzeł.

6. Na czym polega przechodzenie przez poziomy?

Przechodzenie według kolejności poziomów, znane również jako przeszukiwanie wszerz (BFS), odwiedza węzły poziom po poziomie, zaczynając od korzenia i przechodząc do następnego poziomu, zanim przejdzie się głębiej.

ciąg java

7. Kiedy powinienem zastosować każdą technikę przejścia?

Przechodzenie w kolejności jest często używane w drzewach wyszukiwania binarnego, aby uzyskać posortowane węzły.

Przeglądanie zamówień w przedsprzedaży jest przydatne do tworzenia kopii drzewa.

Przechodzenie postorderowe jest powszechnie stosowane w drzewach wyrażeń do oceny wyrażeń.

Przechodzenie według kolejności poziomów jest pomocne w znajdowaniu najkrótszej ścieżki między węzłami.

8. Jak zaimplementować algorytmy przechodzenia przez drzewo?

Algorytmy przechodzenia przez drzewo można implementować rekurencyjnie lub iteracyjnie, w zależności od konkretnych wymagań i używanego języka programowania.

9. Czy algorytmy przechodzenia przez drzewa można zastosować do innych struktur drzewiastych?

Tak, algorytmy przechodzenia przez drzewa można dostosować do przechodzenia przez inne struktury drzewiaste, takie jak kopce binarne, drzewa n-arne i wykresy reprezentowane jako drzewa.

10. Czy przy wyborze techniki przemierzania brane są pod uwagę jakieś parametry?

Kwestie dotyczące wydajności zależą od takich czynników, jak rozmiar i kształt drzewa, dostępna pamięć i określone operacje wykonywane podczas przechodzenia. Ogólnie rzecz biorąc, wybór techniki przechodzenia może mieć wpływ na wydajność niektórych operacji, dlatego ważne jest, aby wybrać metodę najbardziej odpowiednią dla konkretnego przypadku użycia.

Kilka innych ważnych samouczków:

  • Poradnik DSA
  • Samouczek projektowania systemu
  • Plan rozwoju oprogramowania
  • Plan działania, aby zostać Menedżerem Produktu
  • Naucz się SAPa
  • Naucz się SEO