logo

TechCodeview

Techniky prechádzania stromami – Štruktúra údajov a návody na algoritmy

Techniky prechodu cez strom zahŕňajú rôzne spôsoby, ako navštíviť všetky uzly stromu. Na rozdiel od lineárnych dátových štruktúr (Array, Linked List, Queues, Stacks, atď.), ktoré majú len jeden logický spôsob, ako nimi prejsť, stromy sa dajú prechádzať rôznymi spôsobmi. V tomto článku budeme diskutovať o všetkých technikách prechodu cez strom spolu s ich použitím.



Obsah

Význam prechodu cez strom:

Prechádzanie stromom označuje proces návštevy alebo prístupu ku každému uzlu stromu presne raz v určitom poradí. Algoritmy prechodu cez strom nám pomáhajú navštíviť a spracovať všetky uzly stromu. Keďže strom nie je lineárna dátová štruktúra, existuje viacero uzlov, ktoré môžeme navštíviť po návšteve určitého uzla. Existuje viacero techník prechodu cez strom, ktoré rozhodujú o poradí, v ktorom sa majú navštíviť uzly stromu.

Techniky prechádzania stromami:



Stromovú dátovú štruktúru možno prechádzať nasledujúcimi spôsobmi:

  • Hĺbkové prvé vyhľadávanie alebo DFS
    • Inorder Traversal
    • Preorder Traversal
    • Prenos poštovej poukážky
  • Level Order Traversal alebo Breadth First Search alebo BFS

Inorder Traversal :

Inorder traversal navštívi uzol v poradí: Vľavo -> Koreň -> Vpravo




Algoritmus pre prechod v poradí:

Inorder (strom)

  • Prejdite ľavým podstromom, t.j. zavolajte Inorder(vľavo->podstrom)
  • Navštívte koreň.
  • Prejdite pravým podstromom, t.j. zavolajte Inorder(pravý->podstrom)

Použitie Inorder Traversal:

môže android hrať gamepigeon
  • V prípade binárnych vyhľadávacích stromov (BST), Inorder traversal dáva uzly v neklesajúcom poradí.
  • Na získanie uzlov BST v nezvyšujúcom sa poradí možno použiť variant prechodu Inorder, kde je Inorder traversal obrátený.
  • Inorder traversal možno použiť na vyhodnotenie aritmetických výrazov uložených v stromoch výrazov.

Úryvok kódu pre prechod v poradí:

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->vľavo);  // Potom vytlačte údaje uzla cout<< node->údajov<< ' ';  // Now recur on right child  printInorder(node->správny); }>
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->vľavo);  // Potom vytlačíme údaje uzla printf('%d ', node->data);  // Teraz sa opakujte na pravom potomkovi printInorder(node->right); }>
Java 
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); }>
Výkon 
Inorder traversal of binary tree is 4 2 5 1 3>

Časová zložitosť: O(N)
Pomocný priestor: Ak neberieme do úvahy veľkosť zásobníka pre volania funkcií, potom O(1), inak O(h), kde h je výška stromu.

Preorder Traversal :

Prechod predobjednávky navštívi uzol v poradí: Koreň -> Vľavo -> Vpravo

android proces acore

Algoritmus na prechod predobjednávky:

Predobjednávka (strom)

  • Navštívte koreň.
  • Prejdite ľavým podstromom, t. j. zavolajte Predobjednávku (vľavo->podstrom)
  • Prejdite pravým podstromom, t.j. zavolajte Predobjednávku (vpravo->podstrom)

Použitie prechodu predobjednávky:

  • Prechod predobjednávky sa používa na vytvorenie kópie stromu.
  • Prechod predobjednávky sa používa aj na získanie výrazov predpony v strome výrazov.

Úryvok kódu pre prechod predobjednávky:

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->údajov<< ' ';  // Then recur on left subtree  printPreorder(node->vľavo);  // Teraz sa opakujte v pravom podstrome 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->údaje);  // Potom sa opakujte v ľavom podstrome printPreorder(node->left);  // Teraz sa opakujte v pravom podstrome printPreorder(node->right); }>
Java 
// 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); }>
Výkon 
Preorder traversal of binary tree is 1 2 4 5 3>

Časová zložitosť: O(N)
Pomocný priestor: Ak neberieme do úvahy veľkosť zásobníka pre volania funkcií, potom O(1), inak O(h), kde h je výška stromu.

Prenos poštovej poukážky :

Postorder traversal navštívi uzol v poradí: Vľavo -> Vpravo -> Koreň

Algoritmus pre prechod postorderom:

Algoritmus Poštová poukážka (strom)

  • Prejdite ľavým podstromom, t.j. zavolajte Postorder(vľavo->podstrom)
  • Prejdite pravým podstromom, t. j. zavolajte Postorder (vpravo->podstrom)
  • Navštívte koreň

Využitie Mailorder Traversal:

  • Postorder traversal sa používa na odstránenie stromu. Pozri otázka na vymazanie stromu pre podrobnosti.
  • Postorder traversal je tiež užitočný na získanie postfixového výrazu stromu výrazov.
  • Postorder traversal môže pomôcť pri algoritmoch zberu odpadu, najmä v systémoch, kde sa používa manuálna správa pamäte.

Úryvok kódu pre prechod poštovej objednávky:

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->vľavo);  // Potom sa opakujte v pravom podstrome printPostorder(node->right);  // Teraz sa vysporiadajte s uzlom cout<< node->údajov<< ' '; }>
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->vľavo);  // Potom sa opakujte v pravom podstrome printPostorder(node->right);  // Teraz sa vysporiadajte s uzlom printf('%d ', uzol->data); }>
Java 
// 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 + ' '); }>
Výkon 
Postorder traversal of binary tree is 4 5 2 3 1>

Prechádzanie objednávky úrovne :

Prechádzanie objednávky úrovne úplne navštívi všetky uzly prítomné na rovnakej úrovni pred návštevou ďalšej úrovne.

Algoritmus pre prechod na úrovni objednávky:

Level Order (strom)

  • Vytvorte prázdny front Q
  • Zaraďte koreňový uzol stromu do frontu Q
  • Slučka, kým Q nie je prázdne
    • Vyraďte uzol z Q a navštívte ho
    • Zaraďte ľavý potomok uzla vyradeného z frontu, ak existuje
    • Zaradiť do frontu pravý potomok vyradeného uzla, ak existuje

Použitie poradia úrovní:

  • Prechádzanie poradia úrovní sa používa hlavne ako vyhľadávanie podľa šírky na vyhľadávanie alebo spracovanie uzlov úroveň po úrovni.
  • Level Order traversal sa používa aj na Serializácia a deserializácia stromu .

Úryvok kódu pre prechod objednávky úrovne:

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;  // Zaradiť koreň a inicializovať výšku q.push(root);  while (q.empty() == false) { // Tlač prednej časti frontu a jeho odstránenie z frontu Node* node = q.front();  cout<< node->údajov<< ' ';  q.pop();  // Enqueue left child  if (node->vľavo != NULL) q.push(uzol->vľavo);  // Zaradiť pravého potomka 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->údaje);  // Zaradiť ľavý potomok if (temp_node->left) enQueue(queue, &rear, temp_node->left);  // Zaradenie pravého potomka if (temp_node->right) enQueue(queue, &rear, temp_node->right);  // Dequeue node a urobte z neho temp_node temp_node = deQueue(queue, &front);  } }>
Java 
// Given a binary tree. Print // its nodes in level order // using array for implementing queue void printLevelOrder() {  Queuefront = nový LinkedList();  queue.add(root);  while (!queue.isEmpty()) { // poll() odstráni súčasnú hlavičku.  Node tempNode = queue.poll();  System.out.print(tempNode.data + ' ');  // Zaradiť ľavého potomka if (tempNode.left != null) { queue.add(tempNode.left);  } // Zaradenie pravého potomka if (tempNode.right != null) { queue.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): # Vytlačiť prednú časť frontu a # odstrániť ju z frontu print(queue[0].data, end=' ') node = queue.pop(0) # Zaradiť ľavý potomok, ak node.left nie je Žiadne: queue.append(node.left) # Zaradiť pravé dieťa, ak node.right nie je Žiadne: queue.append(node.right)>
C# 
// Given a binary tree. Print // its nodes in level order using // array for implementing queue void printLevelOrder() {  Queuefront = nový front();  queue.Enqueue(root);  while (queue.Count != 0) { Node tempNode = queue.Dequeue();  Console.Write(tempNode.data + ' ');  // Zaradiť ľavého potomka if (tempNode.left != null) { queue.Enqueue(tempNode.left);  } // Zaradenie pravého potomka if (tempNode.right != null) { queue.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);  }  } }>

Ďalšie prechody stromov:

  1. Prechod hraníc
  2. Diagonálny prechod

1. Prechod hraníc :

Prechod hraníc strom obsahuje:

  • ľavá hranica (uzly vľavo okrem uzlov listu)
  • listy (pozostávajú len z uzlín listov)
  • pravá hranica (uzly vpravo s výnimkou listových uzlov)

Algoritmus pre prechod hranice:

BoundaryTraversal (strom)

faktoriál v c
  • Ak root nie je null:
    • Vytlačte údaje používateľa root
    • PrintLeftBoundary(root->left) // Vytlačí ľavé hraničné uzly
    • PrintLeafNodes(root->left) // Vytlačí listové uzly ľavého podstromu
    • PrintLeafNodes(root->right) // Vytlačí listové uzly pravého podstromu
    • PrintRightBoundary(root->right) // Tlač pravých hraničných uzlov

Použitie prechodu hraníc:

  • Prechod hraníc pomáha vizualizovať vonkajšiu štruktúru binárneho stromu a poskytuje pohľad na jeho tvar a hranice.
  • Prechod hraníc poskytuje spôsob prístupu a úpravy týchto uzlov, čo umožňuje operácie, ako je orezanie alebo premiestnenie hraničných uzlov.

2. Diagonálny prechod

V Diagonálnom prechode stromu budú všetky uzly v jednej diagonále vytlačené jeden po druhom.

Algoritmus pre diagonálny prechod:

DiagonalTraversal(strom):

  • Ak root nie je null:
    • Vytvorte prázdnu mapu
    • DiagonalTraversalUtil(root, 0, M) // Volanie pomocnej funkcie s počiatočnou úrovňou uhlopriečky 0
    • Pre každý pár kľúč – hodnota (diagonalLevel, uzly) v M:
      • Pre každý uzol v uzloch:
      • Vytlačte údaje uzla

DiagonalTraversalUtil(node, diagonalLevel, M):

  • Ak je uzol null:
  • Návrat
  • Ak diagonalLevel nie je prítomný v M:
    • Vytvorte nový zoznam v M pre diagonalLevel
  • Pripojte údaje uzla do zoznamu na M[diagonalLevel]
  • DiagonalTraversalUtil(node->left, diagonalLevel + 1, M) // Prechádzať ľavé dieťa so zvýšenou úrovňou uhlopriečky
  • DiagonalTraversalUtil(node->right, diagonalLevel, M) // Prechádzať vpravo potomka s rovnakou úrovňou uhlopriečky

Použitie diagonálneho prechodu:

  • Diagonálne prechádzanie pomáha pri vizualizácii hierarchickej štruktúry binárnych stromov, najmä v stromových dátových štruktúrach, ako sú binárne vyhľadávacie stromy (BST) a haldové stromy.
  • Diagonálny prechod možno použiť na výpočet súčtu ciest pozdĺž uhlopriečok v binárnom strome.

Často kladené otázky (FAQ) o technikách prechodu stromov:

1. Čo sú techniky prechodu cez strom?

Techniky prechodu cez strom sú metódy používané na návštevu a spracovanie všetkých uzlov v stromovej dátovej štruktúre. Umožňujú vám systematicky pristupovať ku každému uzlu presne raz.

2. Aké sú bežné typy prechodu cez stromy?

Bežné typy prechodu cez strom sú: prechod v poradí, prechod pred poradím, prechod po postordere, prechod v poradí podľa úrovne (vyhľadávanie do šírky)

3. Čo je Inorder traversal?

Inorder traversal je metóda prechodu do hĺbky, kde sa uzly navštevujú v poradí: ľavý podstrom, aktuálny uzol, pravý podstrom.

4. Čo je prechod predobjednávky?

Preorder traversal je metóda prechodu do hĺbky, kde sa uzly navštevujú v poradí: aktuálny uzol, ľavý podstrom, pravý podstrom.

5. Čo je to prechod poštových poukážok?

Postorder traversal je metóda prechodu do hĺbky, kde sa uzly navštevujú v poradí: ľavý podstrom, pravý podstrom, aktuálny uzol.

6. Čo je to prechod úrovňového poriadku?

Prechádzanie podľa poradia úrovní, známe aj ako vyhľadávanie na prvom mieste (BFS), navštevuje uzly úroveň po úrovni, počnúc od koreňa a prechádza na ďalšiu úroveň, kým prejde hlbšie.

7. Kedy by som mal použiť jednotlivé techniky prechodu?

Inorder traversal sa často používa pre binárne vyhľadávacie stromy na získanie uzlov v zoradenom poradí.

Prechod predobjednávky je užitočný na vytvorenie kópie stromu.

Postorder traversal sa bežne používa v stromoch výrazov na vyhodnotenie výrazov.

Prechod podľa poradia úrovní je užitočný pri hľadaní najkratšej cesty medzi uzlami.

8. Ako implementujem algoritmy prechodu cez strom?

Algoritmy prechodu cez strom môžu byť implementované rekurzívne alebo iteratívne v závislosti od špecifických požiadaviek a použitého programovacieho jazyka.

9. Môžu byť algoritmy prechodu cez strom aplikované na iné stromové štruktúry?

Áno, algoritmy prechodu cez strom môžu byť prispôsobené tak, aby prechádzali inými stromovými štruktúrami, ako sú binárne haldy, n-árne stromy a grafy reprezentované ako stromy.

prečiarknutie

10. Existujú nejaké výkonnostné hľadiská pri výbere techniky prechodu?

Úvahy o výkone závisia od faktorov, ako je veľkosť a tvar stromu, dostupná pamäť a špecifické operácie vykonávané počas prechodu. Vo všeobecnosti môže výber techniky prechodu ovplyvniť efektivitu určitých operácií, preto je dôležité zvoliť najvhodnejšiu metódu pre váš konkrétny prípad použitia.

Niektoré ďalšie dôležité návody:

  • Príručka DSA
  • Návod na návrh systému
  • Plán vývoja softvéru
  • Plán stať sa produktovým manažérom
  • Naučte sa SAP
  • Naučte sa SEO