logo

TechCodeview

Trægennemføringsteknikker – Datastruktur og algoritme-vejledninger

Trægennemløbsteknikker omfatte forskellige måder at besøge alle træets noder på. I modsætning til lineære datastrukturer (Array, Linked List, Queue, Stacks osv.), som kun har én logisk måde at krydse dem på, kan træer krydses på forskellige måder. I denne artikel vil vi diskutere om alle trægennemløbsteknikker sammen med deres anvendelser.

arraylist sortering

Indholdsfortegnelse



Trægennemgang betyder:

Trægennemgang refererer til processen med at besøge eller få adgang til hver knude i træet nøjagtigt én gang i en bestemt rækkefølge. Trægennemløbsalgoritmer hjælper os med at besøge og behandle alle træets noder. Da træet ikke er en lineær datastruktur, er der flere noder, som vi kan besøge efter at have besøgt en bestemt node. Der er flere trægennemløbsteknikker, som bestemmer rækkefølgen, hvori træets noder skal besøges.

Trægennemløbsteknikker:

En trædatastruktur kan krydses på følgende måder:

  • Depth First Search eller DFS
    • Inorder Traversal
    • Forudbestil gennemkørsel
    • Postordregennemgang
  • Level Order Traversal eller Breadth First Search eller BFS

Inorder Traversal :

Inorder-gennemgang besøger noden i rækkefølgen: Venstre -> Rod -> Højre


Algoritme for Inorder Traversal:

Inorder (træ)

  • Gå gennem det venstre undertræ, dvs. kald Inorder(venstre->undertræ)
  • Besøg roden.
  • Gå gennem det højre undertræ, dvs. kald Inorder(højre->undertræ)

Anvendelser af Inorder Traversal:

  • I tilfælde af binære søgetræer (BST), giver Inorder traversal noder i ikke-faldende rækkefølge.
  • For at få noder af BST i ikke-stigende rækkefølge, kan en variation af Inorder traversal, hvor Inorder traversal er reverseret, bruges.
  • Inorder-gennemgang kan bruges til at evaluere aritmetiske udtryk gemt i udtrykstræer.

Kodestykke til gennemkørsel af ordrer:

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->venstre);  // Udskriv derefter dataene for node cout<< node->data<< ' ';  // Now recur on right child  printInorder(node->højre); }>
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->venstre);  // Udskriv derefter dataene for node printf('%d ', node->data);  // Gentager nu på højre underordnede 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); }>
Produktion 
Inorder traversal of binary tree is 4 2 5 1 3>

Tidskompleksitet: PÅ)
Hjælpeplads: Hvis vi ikke overvejer størrelsen af ​​stakken for funktionskald, så O(1) ellers O(h), hvor h er højden af ​​træet.

Forudbestil gennemkørsel :

Gennemgang af forudbestilling besøger noden i rækkefølgen: Rod -> Venstre -> Højre

Algoritme for Preorder Traversal:

Forudbestil (træ)

  • Besøg roden.
  • Gå gennem det venstre undertræ, dvs. kald Preorder (venstre->undertræ)
  • Gå gennem det højre undertræ, dvs. kald Preorder (højre->undertræ)

Brug af Preorder Traversal:

  • Preorder traversal bruges til at oprette en kopi af træet.
  • Preorder traversal bruges også til at få præfiksudtryk på et udtrykstræ.

Kodestykke til gennemkørsel af forudbestilling:

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->venstre);  // Nu igen på højre undertræ 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->data);  // Gentag derefter i venstre undertræ printPreorder(node->venstre);  // Nu igen på højre undertræ 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); }>
Produktion 
Preorder traversal of binary tree is 1 2 4 5 3>

Tidskompleksitet: PÅ)
Hjælpeplads: Hvis vi ikke overvejer størrelsen af ​​stakken for funktionskald, så O(1) ellers O(h), hvor h er højden af ​​træet.

Postordregennemgang :

Postordre-gennemgang besøger noden i rækkefølgen: Venstre -> Højre -> Rod

Algoritme for postordergennemgang:

Algoritme Postordre (træ)

  • Gå gennem det venstre undertræ, dvs. kald Postorder(venstre->undertræ)
  • Gå gennem det højre undertræ, dvs. kald Postorder (højre->undertræ)
  • Besøg roden

Anvendelser af Mailorder Traversal:

  • Postordre-gennemgang bruges til at slette træet. Se spørgsmålet om sletning af et træ for detaljer.
  • Postorder-gennemgang er også nyttig for at få postfix-udtrykket for et udtrykstræ.
  • Postordre-gennemkørsel kan hjælpe med algoritmer til indsamling af affald, især i systemer, hvor manuel hukommelsesstyring bruges.

Kodestykke til postordregennemgang:

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->venstre);  // Så går igen på højre undertræ printPostorder(node->højre);  // Håndter nu nodecout<< 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->venstre);  // Så går igen på højre undertræ printPostorder(node->højre);  // Håndter nu noden 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 + ' '); }>
Produktion 
Postorder traversal of binary tree is 4 5 2 3 1>

Level Order Traversal :

Level Order Traversal besøger alle noder, der er til stede på samme niveau, fuldstændigt, før du besøger det næste niveau.

Algoritme for niveauordregennemgang:

LevelOrder(træ)

  • Opret en tom kø Q
  • Sæt træets rodknude i kø til Q
  • Loop mens Q ikke er tom
    • Sæt en node i kø fra Q og besøg den
    • Sæt det venstre underordnede knude i kø, hvis det findes
    • Sæt det rigtige underordnede knudepunkt i kø, hvis det findes

Brug af niveaurækkefølge:

  • Level Order Traversal bruges hovedsageligt som Breadth First Search til at søge eller behandle noder niveau-for-niveau.
  • Level Order traversal bruges også til Træserialisering og deserialisering .

Kodestykke til niveauordregennemgang:

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;  // Sæt Root i kø og initialiser højden q.push(root);  while (q.empty() == false) { // Udskriv forsiden af ​​køen og fjern den fra køen Node* node = q.front();  cout<< node->data<< ' ';  q.pop();  // Enqueue left child  if (node->venstre != NULL) q.push(node->venstre);  // Enqueue right child 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->data);  // Enqueue left child if (temp_node->left) enQueue(queue, &rear, temp_node->venstre);  // Enqueue right child if (temp_node->right) enQueue(queue, &rear, temp_node->right);  // Dequeue node og gør den 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 LinkedList();  queue.add(rod);  mens (!queue.isEmpty()) { // poll() fjerner det nuværende hoved.  Node 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): # Udskriv forrest i køen og # fjern det fra køen print(queue[0].data, end=' ') node = queue.pop(0) # Sæt venstre underordnet i kø, hvis node.left ikke er Ingen: queue.append(node.left) # Sæt højre underord i kø, hvis node.right ikke er 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ø();  kø.Enqueue(rod);  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);  }  } }>

Andre trægennemgange:

  1. Grænseoverskridelse
  2. Diagonal gennemkørsel

1. Grænseoverskridelse :

Grænseoverskridelse af et træ inkluderer:

  • venstre grænse (knuder til venstre ekskl. bladknuder)
  • blade (består kun af bladknuderne)
  • højre grænse (knuder til højre ekskl. bladknuder)

Algoritme for grænseoverskridelse:

BoundaryTraversal(træ)

  • Hvis root ikke er null:
    • Udskriv roots data
    • PrintLeftBoundary(rod->venstre) // Udskriv de venstre grænseknuder
    • PrintLeafNodes(rod->venstre) // Udskriv bladknuderne i venstre undertræ
    • PrintLeafNodes(root->right) // Udskriv bladknuderne i højre undertræ
    • PrintRightBoundary(root->right) // Udskriv de rigtige grænseknuder

Brug af grænseoverskridelse:

  • Grænseoverskridelse hjælper med at visualisere den ydre struktur af et binært træ, hvilket giver indsigt i dets form og grænser.
  • Grænseoverskridelse giver mulighed for at få adgang til og ændre disse knudepunkter, hvilket muliggør operationer såsom beskæring eller omplacering af grænseknuder.

2. Diagonal gennemkørsel

I den diagonale gennemgang af et træ vil alle noderne i en enkelt diagonal blive udskrevet én efter én.

Algoritme for diagonal gennemløb:

DiagonalTraversal(træ):

  • Hvis root ikke er null:
    • Opret et tomt kort
    • DiagonalTraversalUtil(rod, 0, M) // Kaldhjælperfunktion med indledende diagonalniveau 0
    • For hvert nøgle-værdi-par (diagonalt niveau, noder) i M:
      • For hver node i noder:
      • Udskriv nodens data

DiagonalTraversalUtil(node, diagonalLevel, M):

  • Hvis noden er null:
  • Vend tilbage
  • Hvis diagonalLevel ikke er til stede i M:
    • Opret en ny liste i M for diagonalLevel
  • Føj nodens data til listen på M[diagonalLevel]
  • DiagonalTraversalUtil(node->venstre, diagonalLevel + 1, M) // Kør venstre barn med øget diagonalniveau
  • DiagonalTraversalUtil(node->right, diagonalLevel, M) // Kør højre barn med samme diagonale niveau

Anvendelser af diagonal gennemkørsel:

  • Diagonal traversal hjælper med at visualisere den hierarkiske struktur af binære træer, især i træbaserede datastrukturer som binære søgetræer (BST'er) og heap trees.
  • Diagonal traversering kan bruges til at beregne stisummer langs diagonaler i et binært træ.

Ofte stillede spørgsmål (FAQ) om trægennemføringsteknikker:

1. Hvad er trægennemløbsteknikker?

Trægennemløbsteknikker er metoder, der bruges til at besøge og behandle alle noder i en trædatastruktur. De giver dig mulighed for at få adgang til hver node nøjagtigt én gang på en systematisk måde.

2. Hvad er de almindelige typer af trækrydsning?

De almindelige typer af trægennemgang er: Inorder traversal, Preorder traversal, Postorder traversal, Level order traversal (Bredth-First Search)

efterfølgende datatyper

3. Hvad er Inorder traversal?

Inorder traversal er en dybde-først traversal metode, hvor noder besøges i rækkefølgen: venstre undertræ, nuværende knudepunkt, højre undertræ.

4. Hvad er preorder traversal?

Preorder traversal er en dybde-først traversal metode, hvor noder besøges i rækkefølgen: nuværende node, venstre undertræ, højre undertræ.

5. Hvad er postordregennemkørsel?

Postorder traversal er en dybde-først traversal metode, hvor noder besøges i rækkefølgen: venstre undertræ, højre undertræ, nuværende knude.

6. Hvad er niveauordregennemgang?

Gennemgang af niveaurækkefølge, også kendt som Breadth-First Search (BFS), besøger noder niveau for niveau, startende fra roden og bevæger sig til næste niveau, før du krydser dybere.

7. Hvornår skal jeg bruge hver traversalteknik?

Inorder traversal bruges ofte til binære søgetræer for at få noder i sorteret rækkefølge.

Gennemgang af forudbestilling er nyttig til at oprette en kopi af træet.

Postorder traversal bruges almindeligvis i udtrykstræer til at evaluere udtryk.

Gennemgang af niveaurækkefølge er nyttig til at finde den korteste vej mellem noder.

8. Hvordan implementerer jeg trægennemløbsalgoritmer?

Trægennemløbsalgoritmer kan implementeres rekursivt eller iterativt, afhængigt af de specifikke krav og programmeringssprog, der bruges.

9. Kan trægennemløbsalgoritmer anvendes på andre trælignende strukturer?

Ja, trægennemløbsalgoritmer kan tilpasses til at krydse andre trælignende strukturer såsom binære dynger, n-ære træer og grafer repræsenteret som træer.

10. Er der nogen præstationsovervejelser, når man vælger en traversalteknik?

Ydeevneovervejelser afhænger af faktorer såsom træets størrelse og form, tilgængelig hukommelse og specifikke handlinger, der udføres under gennemkøring. Generelt kan valget af gennemløbsteknik påvirke effektiviteten af ​​visse operationer, så det er vigtigt at vælge den bedst egnede metode til din specifikke brug.

Nogle andre vigtige tutorials:

  • DSA Tutorial
  • Tutorial til systemdesign
  • Softwareudvikling køreplan
  • Køreplan for at blive produktchef
  • Lær SAP
  • Lær SEO