logo

TechCodeview

Trädgenomgångstekniker – handledningar om datastruktur och algoritmer

Trädpasseringstekniker inkluderar olika sätt att besöka alla noder i trädet. Till skillnad från linjära datastrukturer (Array, Linked List, Queue, Stacks, etc) som bara har ett logiskt sätt att korsa dem, kan träd korsas på olika sätt. I den här artikeln kommer vi att diskutera om alla trädgenomgångstekniker tillsammans med deras användningsområden.



Innehållsförteckning

Tree Traversal Betydelse:

Traversal av träd hänvisar till processen att besöka eller komma åt varje nod i trädet exakt en gång i en viss ordning. Algoritmer för trädgenomgång hjälper oss att besöka och bearbeta alla noder i trädet. Eftersom träd inte är en linjär datastruktur finns det flera noder som vi kan besöka efter att ha besökt en viss nod. Det finns flera trädtraverseringstekniker som bestämmer i vilken ordning trädets noder ska besökas.

Trädpasseringstekniker:



En träddatastruktur kan passeras på följande sätt:

  • Depth First Search eller DFS
    • Inorder Traversal
    • Förbeställ Traversal
    • Postorder Traversal
  • Level Order Traversal eller Breadth First Search eller BFS

Inorder Traversal :

Inorder-traversering besöker noden i följande ordning: Vänster -> Rot -> Höger




Algoritm för inorderövergång:

Inorder(träd)

  • Gå igenom det vänstra underträdet, d.v.s. anrop Inorder(vänster->underträd)
  • Besök roten.
  • Gå igenom höger underträd, d.v.s. anrop Inorder(höger->underträd)

Användningar av Inorder Traversal:

  • I fallet med binära sökträd (BST) ger Inorder-traversal noder i icke-minskande ordning.
  • För att få noder av BST i icke-ökande ordning, kan en variant av Inorder-traversal där Inorder-traversal är omvänd användas.
  • Inordersövergång kan användas för att utvärdera aritmetiska uttryck lagrade i uttrycksträd.

Kodavsnitt för inorderövergång:

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änster);  // Skriv sedan ut data för nod cout<< node->data<< ' ';  // Now recur on right child  printInorder(node->höger); }>
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änster);  // Skriv sedan ut data för node printf('%d ', node->data);  // Nu återkommande på höger underordnade printInorder(nod->höger); }>
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); }>
Produktion 
Inorder traversal of binary tree is 4 2 5 1 3>

Tidskomplexitet: PÅ)
Hjälputrymme: Om vi ​​inte tar hänsyn till stackens storlek för funktionsanrop så är O(1) annars O(h) där h är trädets höjd.

Förbeställ Traversal :

Genomgång av förbeställning besöker noden i följande ordning: Rot -> Vänster -> Höger

Algoritm för förbeställningstrafik:

Förbeställning (träd)

innehåller delsträng java
  • Besök roten.
  • Gå igenom det vänstra underträdet, d.v.s. anropa Preorder (vänster->underträd)
  • Gå igenom det högra underträdet, d.v.s. anropa Preorder (höger->underträd)

Användning av förbeställningstrafik:

  • Genomgång av förbeställning används för att skapa en kopia av trädet.
  • Genomgång av förbeställning används också för att få prefixuttryck på ett uttrycksträd.

Kodavsnitt för förbeställningstrafik:

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->data<< ' ';  // Then recur on left subtree  printPreorder(node->vänster);  // Nu återkommer på höger underträd printPreorder(nod->höger); }>
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->data);  // Återkommer sedan till vänster underträd printPreorder(nod->vänster);  // Nu återkommer på höger underträd printPreorder(nod->höger); }>
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); }>
Produktion 
Preorder traversal of binary tree is 1 2 4 5 3>

Tidskomplexitet: PÅ)
Hjälputrymme: Om vi ​​inte tar hänsyn till stackens storlek för funktionsanrop så är O(1) annars O(h) där h är trädets höjd.

Postorder Traversal :

Postorderpassering besöker noden i följande ordning: Vänster -> Höger -> Rot

Algorithm for Postorder Traversal:

Algorithm Postorder(tree)

  • Gå igenom det vänstra underträdet, d.v.s. anrop Postorder (vänster->underträd)
  • Gå igenom höger underträd, d.v.s. anrop Postorder (höger->underträd)
  • Besök roten

Uses of Postorder Traversal:

  • Postorder-traversering används för att ta bort trädet. Ser frågan om radering av ett träd för detaljer.
  • Postorder-traversal är också användbart för att få postfix-uttrycket för ett uttrycksträd.
  • Postorder-traversering kan hjälpa till med algoritmer för insamling av sopor, särskilt i system där manuell minneshantering används.

Code Snippet for Postorder Traversal:

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änster);  // Sedan återkommer på höger underträd printPostorder(nod->höger);  // Ta nu hand om nodcout<< node->data<< ' '; }>
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änster);  // Sedan återkommer på höger underträd printPostorder(nod->höger);  // Ta nu hand om noden printf('%d ', nod->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 + ' '); }>
Produktion 
Postorder traversal of binary tree is 4 5 2 3 1>

Nivå Order Traversal :

Nivå Order Traversal besöker alla noder som finns på samma nivå helt innan nästa nivå besöks.

vem är freddie mercury

Algoritm för genomgång av nivåorder:

LevelOrder(träd)

  • Skapa en tom kö Q
  • Ställ trädets rotnod i kö till Q
  • Slinga medan Q inte är tomt
    • Ta bort en nod från Q och besök den
    • Ställ den vänstra underordnade noden i kö om den finns
    • Ställ i kö höger underordnad till den urköade noden om den finns

Användning av nivåordning:

  • Level Order Traversal används huvudsakligen som Breadth First Search för att söka eller bearbeta noder nivå för nivå.
  • Nivåorderövergång används också för Serialisering och deserialisering av träd .

Kodavsnitt för genomgång av nivåorder:

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;  // Enqueue Root och initiera höjd q.push(root);  while (q.empty() == false) { // Skriv ut framsidan av kön och ta bort den från kön Node* node = q.front();  cout<< node->data<< ' ';  q.pop();  // Enqueue left child  if (node->vänster != NULL) q.push(nod->vänster);  // Enqueue right child if (nod->höger != NULL) q.push(nod->höger);  } }>
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->data);  // 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);  // Ta bort noden och gör den till 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() {  Queuekö = ny länkad lista();  queue.add(root);  medan (!queue.isEmpty()) { // poll() tar bort det aktuella huvudet.  Nod tempNode = queue.poll();  System.out.print(tempNode.data + ' ');  // Enqueue left child if (tempNode.left != null) { queue.add(tempNode.left);  } // Enqueue right child 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): # Skriv ut framför kön och # ta bort den från kön print(queue[0].data, end=' ') node = queue.pop(0) # Kön vänster underordnad om node.left inte är Ingen: queue.append(node.left) # Kö höger underordnad om node.right inte är Ingen: queue.append(node.right)>
C# 
// Given a binary tree. Print // its nodes in level order using // array for implementing queue void printLevelOrder() {  Queuekö = ny kö();  queue.Enqueue(root);  while (queue.Count != 0) { Node tempNode = queue.Dequeue();  Console.Write(tempNode.data + ' ');  // Enqueue left child if (tempNode.left != null) { queue.Enqueue(tempNode.left);  } // Enqueue right child 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);  }  } }>

Andra trädövergångar:

  1. Gränsöverskridande
  2. Diagonal genomgång

1. Gränsöverskridande :

Gränsöverskridande av ett träd inkluderar:

  • vänster gräns (noder till vänster exklusive bladnoder)
  • löv (består endast av lövnoderna)
  • höger gräns (noder till höger exklusive bladnoder)

Algoritm för gränsöverskridande:

BoundaryTraversal(träd)

  • Om root inte är null:
    • Skriv ut roots data
    • PrintLeftBoundary(root->left) // Skriv ut de vänstra gränsnoderna
    • PrintLeafNodes(root->left) // Skriv ut lövnoderna för vänster underträd
    • PrintLeafNodes(root->right) // Skriv ut lövnoderna i höger underträd
    • PrintRightBoundary(root->right) // Skriv ut de högra gränsnoderna

Användning av gränsöverskridande:

  • Gränsöverskridning hjälper till att visualisera den yttre strukturen av ett binärt träd, vilket ger insikter om dess form och gränser.
  • Övergång av gränser ger ett sätt att komma åt och modifiera dessa noder, vilket möjliggör operationer som beskärning eller ompositionering av gränsnoder.

2. Diagonal genomgång

I Diagonal Traversal of a Tree kommer alla noder i en enda diagonal att skrivas ut en efter en.

Algoritm för diagonal genomgång:

DiagonalTraversal(träd):

  • Om root inte är null:
    • Skapa en tom karta
    • DiagonalTraversalUtil(root, 0, M) // Ring hjälpfunktion med initial diagonalnivå 0
    • För varje nyckel-värdepar (diagonalLevel, noder) i M:
      • För varje nod i noder:
      • Skriv ut nodens data

DiagonalTraversalUtil(nod, diagonalLevel, M):

  • Om noden är null:
  • Lämna tillbaka
  • Om diagonalLevel inte finns i M:
    • Skapa en ny lista i M för diagonalLevel
  • Lägg till nodens data till listan på M[diagonalLevel]
  • DiagonalTraversalUtil(nod->vänster, diagonalLevel + 1, M) // Traversera vänster barn med ökad diagonalnivå
  • DiagonalTraversalUtil(nod->höger, diagonalLevel, M) // Traversera höger barn med samma diagonalnivå

Användning av diagonal traversering:

  • Diagonal traversering hjälper till att visualisera den hierarkiska strukturen hos binära träd, särskilt i trädbaserade datastrukturer som binära sökträd (BST) och heap trees.
  • Diagonal traversering kan användas för att beräkna bansummor längs diagonaler i ett binärt träd.

Vanliga frågor (FAQs) om trädpasseringstekniker:

1. Vad är trädtraverseringstekniker?

Trädtraverseringstekniker är metoder som används för att besöka och bearbeta alla noder i en träddatastruktur. De låter dig komma åt varje nod exakt en gång på ett systematiskt sätt.

2. Vilka är de vanligaste typerna av trädpassering?

De vanligaste typerna av trädpassering är: Inorder-traversal, Preorder-traversal, Postorder-traversal, Level Order-traversal (Bredth-First Search)

primärnyckel och sammansatt nyckel i sql

3. Vad är Inorder-traversal?

Inorder-traversal är en djup-först-traversal-metod där noder besöks i ordningen: vänster underträd, nuvarande nod, höger underträd.

4. Vad är förbeställningstraversal?

Preorder-traversal är en djup-först-traversal-metod där noder besöks i ordningen: aktuell nod, vänster underträd, höger underträd.

5. What is postorder traversal?

Postorder-traversal är en djup-först-traversalmetod där noder besöks i ordningen: vänster underträd, höger underträd, aktuell nod.

6. Vad är nivåorderövergång?

Nivåordningsgenomgång, även känd som Breadth-First Search (BFS), besöker noder nivå för nivå, med början från roten och flyttar till nästa nivå innan de går djupare.

7. När ska jag använda varje traverseringsteknik?

Inorder-traversal används ofta för binära sökträd för att få noder i sorterad ordning.

Genomgång av förbeställning är användbar för att skapa en kopia av trädet.

Postorder-traversering används vanligtvis i uttrycksträd för att utvärdera uttryck.

Genomgång av nivåordning är till hjälp för att hitta den kortaste vägen mellan noder.

8. Hur implementerar jag algoritmer för trädgenomgång?

Trädgenomgångsalgoritmer kan implementeras rekursivt eller iterativt, beroende på de specifika kraven och programmeringsspråket som används.

9. Kan trädtraversalalgoritmer tillämpas på andra trädliknande strukturer?

Ja, trädgenomgångsalgoritmer kan anpassas för att korsa andra trädliknande strukturer såsom binära högar, n-ära träd och grafer representerade som träd.

10. Finns det några prestationsöverväganden när man väljer en traverseringsteknik?

Prestandaöverväganden beror på faktorer som trädets storlek och form, tillgängligt minne och specifika operationer som utförs under genomkörning. I allmänhet kan valet av traverseringsteknik påverka effektiviteten av vissa operationer, så det är viktigt att välja den mest lämpliga metoden för ditt specifika användningsfall.

Några andra viktiga handledningar:

  • Handledning för DSA
  • Handledning för systemdesign
  • Färdkarta för mjukvaruutveckling
  • Färdplan för att bli produktchef
  • Lär dig SAP
  • Lär dig SEO