logo

TechCodeview

Technieken voor het doorlopen van bomen – Tutorials voor gegevensstructuur en algoritmen

Boomtraversale technieken omvatten verschillende manieren om alle knooppunten van de boom te bezoeken. In tegenstelling tot lineaire datastructuren (array, gekoppelde lijst, wachtrijen, stapels, enz.) die slechts één logische manier hebben om ze te doorlopen, kunnen bomen op verschillende manieren worden doorlopen. In dit artikel zullen we alle technieken voor het doorkruisen van bomen bespreken, samen met hun toepassingen.



Inhoudsopgave

Boomtraversal Betekenis:

Boomdoortocht verwijst naar het proces waarbij elk knooppunt van de boom precies één keer in een bepaalde volgorde wordt bezocht of geopend. Boomtraversal-algoritmen helpen ons alle knooppunten van de boom te bezoeken en te verwerken. Omdat boom geen lineaire datastructuur is, zijn er meerdere knooppunten die we kunnen bezoeken nadat we een bepaald knooppunt hebben bezocht. Er zijn meerdere technieken voor het doorlopen van bomen die bepalen in welke volgorde de knooppunten van de boom moeten worden bezocht.

Technieken voor het doorkruisen van bomen:



Een boomgegevensstructuur kan op de volgende manieren worden doorlopen:

  • Diepte eerst zoeken of DFS
    • Inorder-traversal
    • Traversal vooraf bestellen
    • Traversatie van postorders
  • Level Order Traversal of Breadth First Search of BFS

Inorder-traversal :

Inorder-traversal bezoekt het knooppunt in de volgorde: Links -> Wortel -> Rechts




Algoritme voor inorder-traversal:

Inorde(boom)

  • Doorloop de linker deelboom, d.w.z. roep Inorder(linker->subboom) aan
  • Bezoek de wortel.
  • Doorloop de rechter deelboom, d.w.z. roep Inorder(right->subboom) aan

Gebruik van inorder-traversal:

1 miljoen nummer
  • In het geval van binaire zoekbomen (BST) geeft Inorder-traversal knooppunten in niet-afnemende volgorde.
  • Om knooppunten van BST in niet-oplopende volgorde te krijgen, kan een variant van Inorder-traversal worden gebruikt, waarbij de Inorder-traversal wordt omgekeerd.
  • Inorder-traversal kan worden gebruikt om rekenkundige uitdrukkingen te evalueren die zijn opgeslagen in expressiebomen.

Codefragment voor in-order-traversal:

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->links);  // Druk vervolgens de gegevens van node cout af<< node->gegevens<< ' ';  // Now recur on right child  printInorder(node->rechts); }>
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->links);  // Druk vervolgens de gegevens van knooppunt printf('%d ', node->data) af;  // Herhaal dit nu op het rechter kind 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); }>
Uitvoer 
Inorder traversal of binary tree is 4 2 5 1 3>

Tijdcomplexiteit: OP)
Hulpruimte: Als we geen rekening houden met de grootte van de stapel voor functieaanroepen, dan is O(1) anders O(h) waarbij h de hoogte van de boom is.

Traversal vooraf bestellen :

Pre-order traversal bezoekt het knooppunt in de volgorde: Wortel -> Links -> Rechts

Algoritme voor pre-order traversal:

Voorbestellen(boom)

  • Bezoek de wortel.
  • Doorloop de linker subboom, d.w.z. roep Preorder(linker->subboom) aan
  • Doorloop de rechter subboom, d.w.z. roep Preorder(right->subtree) aan

Gebruik van Preorder Traversal:

  • Pre-order traversal wordt gebruikt om een ​​kopie van de boom te maken.
  • Preorder-traversal wordt ook gebruikt om prefix-expressies in een expressieboom te krijgen.

Codefragment voor pre-order traversal:

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->gegevens<< ' ';  // Then recur on left subtree  printPreorder(node->links);  // Kom nu terug in de rechtersubboom 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->gegevens);  // Herhaal vervolgens de linker subboom printPreorder(node->left);  // Kom nu terug in de rechtersubboom 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); }>
Uitvoer 
Preorder traversal of binary tree is 1 2 4 5 3>

Tijdcomplexiteit: OP)
Hulpruimte: Als we geen rekening houden met de grootte van de stapel voor functieaanroepen, dan is O(1) anders O(h) waarbij h de hoogte van de boom is.

Traversatie van postorders :

Postorder traversal bezoekt het knooppunt in de volgorde: Links -> Rechts -> Wortel

Algoritme voor postordertransaltie:

Algoritme Postwissel(boom)

  • Doorloop de linker subboom, d.w.z. roep Postorder(linker->subboom) aan
  • Doorloop de rechter subboom, d.w.z. roep Postorder(right->subtree) aan
  • Bezoek de wortel

Gebruik van postordertransaltie:

  • Postorder traversal wordt gebruikt om de boom te verwijderen. Zien de vraag voor het verwijderen van een boom voor details.
  • Postorder-traversal is ook nuttig om de postfix-expressie van een expressieboom te verkrijgen.
  • Postorder traversal kan helpen bij algoritmen voor het verzamelen van afval, vooral in systemen waar handmatig geheugenbeheer wordt gebruikt.

Codefragment voor postordertransaltie:

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->links);  // Ga vervolgens terug naar de rechtersubboom printPostorder(node->right);  // Behandel nu het knooppunt<< node->gegevens<< ' '; }>
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->links);  // Ga vervolgens terug naar de rechtersubboom printPostorder(node->right);  // Behandel nu het knooppunt printf('%d ', node->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 + ' '); }>
Uitvoer 
Postorder traversal of binary tree is 4 5 2 3 1>

Traversatie van niveauorders :

Traversatie van niveauorders bezoekt alle knooppunten op hetzelfde niveau volledig voordat hij naar het volgende niveau gaat.

10 1 miljoen

Algoritme voor het doorlopen van niveauorders:

Niveauvolgorde(boom)

  • Maak een lege wachtrij Q
  • Plaats het hoofdknooppunt van de boom in Q
  • Lus terwijl Q niet leeg is
    • Haal een knooppunt uit Q uit de wachtrij en bezoek het
    • Zet het linkerkind van het uit de wachtrij geplaatste knooppunt in de wachtrij, als dit bestaat
    • Zet het rechterkind van het uit de wachtrij geplaatste knooppunt in de wachtrij, als dit bestaat

Gebruik van niveauvolgorde:

  • Level Order Traversal wordt voornamelijk gebruikt als Breadth First Search om knooppunten niveau voor niveau te zoeken of te verwerken.
  • Er wordt ook gebruik gemaakt van Level Order Traversal Boomserialisatie en deserialisatie .

Codefragment voor het doorlopen van niveauorders:

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;  // Zet root in de wachtrij en initialiseer de hoogte q.push(root);  while (q.empty() == false) {// Druk de voorkant van de wachtrij af en verwijder deze uit de wachtrij Knooppunt* knooppunt = q.front();  uit<< node->gegevens<< ' ';  q.pop();  // Enqueue left child  if (node->links != NULL) q.push(knooppunt->links);  // Plaats het juiste kind in de wachtrij 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->gegevens);  // Enqueue left child if (temp_node->left) enQueue(queue, &rear, temp_node->left);  // Enqueue right child if (temp_node->right) enQueue(queue, &rear, temp_node->right);  // Haal het knooppunt uit de wachtrij en maak het 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() {  Queuewachtrij = nieuwe LinkedList();  wachtrij.toevoegen(root);  while (!queue.isEmpty()) {// poll() verwijdert het huidige hoofd.  Knooppunt tempNode = wachtrij.poll();  Systeem.out.print(tempNode.data + '');  // Zet het linker kind in de wachtrij if (tempNode.left != null) { wachtrij.add(tempNode.left);  } // Rechts kind in wachtrij plaatsen if (tempNode.right != null) { wachtrij.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): # Druk de voorkant van de wachtrij af en # verwijder deze uit de wachtrij print(queue[0].data, end=' ') node = wachtrij.pop(0) # Zet het linker kind in de wachtrij als node.left niet Geen is: wachtrij.append(node.left) # Plaats het rechter kind in de wachtrij als node.right niet Geen is: wachtrij.append(node.right)>
C# 
// Given a binary tree. Print // its nodes in level order using // array for implementing queue void printLevelOrder() {  Queuewachtrij = nieuwe wachtrij();  wachtrij.Enqueue(root);  while (queue.Count != 0) { Knooppunt tempNode = wachtrij.Dequeue();  Console.Write(tempNode.data + '');  // Enqueue left child if (tempNode.left != null) { wachtrij.Enqueue(tempNode.left);  } // Rechts kind in wachtrij plaatsen if (tempNode.right != null) { wachtrij.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);  }  } }>

Andere boomtraversals:

  1. Grensoverschrijding
  2. Diagonale doorgang

1. Grensoverschrijding :

Grensoverschrijding van een boom omvat:

  • linkergrens (knopen aan de linkerkant exclusief bladknopen)
  • bladeren (bestaan ​​alleen uit de bladknopen)
  • rechtergrens (knopen aan de rechterkant exclusief bladknopen)

Algoritme voor het overschrijden van grenzen:

GrensTraversal(boom)

  • Als root niet nul is:
    • Print root-gegevens
    • PrintLeftBoundary(root->left) // Druk de linker grensknooppunten af
    • PrintLeafNodes(root->left) // Druk de bladknooppunten van de linker subboom af
    • PrintLeafNodes(root->right) // Druk de bladknooppunten van de rechter subboom af
    • PrintRightBoundary(root->right) // Druk de juiste grensknooppunten af

Gebruik van grensovergang:

  • Grensovergang helpt bij het visualiseren van de uiterlijke structuur van een binaire boom, waardoor inzicht wordt verkregen in de vorm en grenzen ervan.
  • Grensovergang biedt een manier om toegang te krijgen tot deze knooppunten en deze te wijzigen, waardoor bewerkingen zoals het snoeien of herpositioneren van grensknooppunten mogelijk worden.

2. Diagonale doorgang

Bij de diagonale doorgang van een boom worden alle knooppunten in een enkele diagonaal één voor één afgedrukt.

Algoritme voor diagonale verplaatsing:

DiagonaleTraversal(boom):

  • Als root niet nul is:
    • Maak een lege kaart
    • DiagonalTraversalUtil(root, 0, M) // Roep de helperfunctie op met initieel diagonaalniveau 0
    • Voor elk sleutelwaardepaar (diagonalLevel, knooppunten) in M:
      • Voor elk knooppunt in knooppunten:
      • Print de gegevens van het knooppunt

DiagonalTraversalUtil(knooppunt, diagonaalniveau, M):

  • Als het knooppunt nul is:
  • Opbrengst
  • Als diagonalLevel niet aanwezig is in M:
    • Maak een nieuwe lijst in M ​​voor diagonalLevel
  • Voeg de gegevens van het knooppunt toe aan de lijst op M[diagonalLevel]
  • DiagonalTraversalUtil(node->left, diagonalLevel + 1, M) // Beweeg het linker kind met verhoogd diagonaalniveau
  • DiagonalTraversalUtil(node->right, diagonalLevel, M) // Beweeg het rechter kind met hetzelfde diagonale niveau

Gebruik van diagonale verplaatsing:

  • Diagonale doorgang helpt bij het visualiseren van de hiërarchische structuur van binaire bomen, met name in op bomen gebaseerde datastructuren zoals binaire zoekbomen (BST's) en heap-bomen.
  • Diagonale verplaatsing kan worden gebruikt om padsommen langs diagonalen in een binaire boom te berekenen.

Veelgestelde vragen (FAQ's) over boomtraversale technieken:

1. Wat zijn technieken voor het doorkruisen van bomen?

Tree Traversal-technieken zijn methoden die worden gebruikt om alle knooppunten in een boomdatastructuur te bezoeken en te verwerken. Hiermee kunt u elk knooppunt precies één keer op een systematische manier benaderen.

2. Wat zijn de meest voorkomende soorten boomtraversal?

De meest voorkomende soorten boom-traversal zijn: In-order-traversal, Pre-order-traversal, Post-order-traversal, Level-order-traversal (Breadth-First Search)

powershell-beheerder

3. Wat is inorder-traversal?

Inorder-traversal is een diepte-eerst-traversal-methode waarbij knooppunten worden bezocht in de volgorde: linker subboom, huidig ​​knooppunt, rechter subboom.

4. Wat is pre-order traversal?

Preorder-traversal is een diepte-eerst-traversal-methode waarbij knooppunten worden bezocht in de volgorde: huidig ​​knooppunt, linker subboom, rechter subboom.

5. Wat is postwisseltransactie?

Postorder-traversal is een diepte-eerst-traversal-methode waarbij knooppunten worden bezocht in de volgorde: linker subboom, rechter subboom, huidig ​​knooppunt.

6. Wat is het doorlopen van niveauorders?

Level Order Traversal, ook bekend als Breadth-First Search (BFS), bezoekt knooppunten niveau voor niveau, beginnend bij de root en gaat naar het volgende niveau voordat er dieper wordt doorkruist.

7. Wanneer moet ik elke verplaatsingstechniek gebruiken?

Inorder traversal wordt vaak gebruikt voor binaire zoekbomen om knooppunten in gesorteerde volgorde te krijgen.

Voorbestelling doorlopen is handig voor het maken van een kopie van de stamboom.

Postorder traversal wordt vaak gebruikt in expressiebomen om expressies te evalueren.

Het doorlopen van niveauvolgorde is nuttig voor het vinden van het kortste pad tussen knooppunten.

8. Hoe implementeer ik algoritmen voor het doorlopen van bomen?

Algoritmen voor het doorlopen van bomen kunnen recursief of iteratief worden geïmplementeerd, afhankelijk van de specifieke vereisten en de gebruikte programmeertaal.

9. Kunnen algoritmen voor het doorlopen van bomen worden toegepast op andere boomachtige structuren?

Ja, algoritmen voor het doorkruisen van bomen kunnen worden aangepast om andere boomachtige structuren te doorkruisen, zoals binaire heaps, n-aire bomen en grafieken die worden weergegeven als bomen.

10. Zijn er prestatieoverwegingen bij het kiezen van een traversaltechniek?

Prestatieoverwegingen zijn afhankelijk van factoren zoals de grootte en vorm van de boom, het beschikbare geheugen en specifieke bewerkingen die tijdens de traversal worden uitgevoerd. Over het algemeen kan de keuze van de traversal-techniek de efficiëntie van bepaalde bewerkingen beïnvloeden. Het is dus belangrijk om de meest geschikte methode voor uw specifieke gebruikssituatie te kiezen.

Enkele andere belangrijke tutorials:

  • DSA-zelfstudie
  • Systeemontwerp-tutorial
  • Routekaart voor softwareontwikkeling
  • Roadmap om Product Manager te worden
  • Leer SAP
  • Leer SEO