logo

TechCodeview

Tree Traversal Techniques – Datastruktur og algoritmeopplæring

Tree Traversal-teknikker inkludere ulike måter å besøke alle nodene i treet. I motsetning til lineære datastrukturer (Array, Linked List, Queue, Stacks, etc) som bare har én logisk måte å krysse dem på, kan trær krysses på forskjellige måter. I denne artikkelen vil vi diskutere om alle trekryssingsteknikkene sammen med deres bruk.



arraylist sortering

Innholdsfortegnelse

Tree Traversal Betydning:

Traversering av tre refererer til prosessen med å besøke eller få tilgang til hver node i treet nøyaktig én gang i en bestemt rekkefølge. Algoritmer for tregjennomgang hjelper oss med å besøke og behandle alle nodene til treet. Siden treet ikke er en lineær datastruktur, er det flere noder som vi kan besøke etter å ha besøkt en bestemt node. Det er flere tregjennomgangsteknikker som bestemmer rekkefølgen som nodene til treet skal besøkes i.

Traverseringsteknikker for tre:



En tredatastruktur kan krysses på følgende måter:

  • Depth First Search eller DFS
    • Inorder Traversal
    • Forhåndsbestill Traversal
    • Postordregjennomgang
  • Level Order Traversal eller Breadth First Search eller BFS

Inorder Traversal :

Inorder-gjennomgang besøker noden i rekkefølgen: Venstre -> Rot -> Høyre




Algoritme for Inorder Traversal:

Inorder(tre)

  • Gå gjennom det venstre undertreet, dvs. ring Inorder(venstre->undertre)
  • Besøk roten.
  • Gå gjennom høyre undertre, dvs. ring Inorder (høyre->undertre)

Bruk av Inorder Traversal:

  • Når det gjelder binære søketrær (BST), gir Inorder-traversal noder i ikke-avtagende rekkefølge.
  • For å få noder av BST i ikke-økende rekkefølge, kan en variant av Inorder-traversal hvor Inorder-traversal er reversert, brukes.
  • Inorder-gjennomgang kan brukes til å evaluere aritmetiske uttrykk lagret i uttrykkstrær.

Kodebit for bestillingsgjennomgang:

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);  // Skriv deretter ut dataene til node cout<< node->data<< ' ';  // Now recur on right child  printInorder(node->Ikke sant); }>
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);  // Skriv deretter ut dataene til node printf('%d ', node->data);  // Nå gjentakelse på høyre 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); }>
Produksjon 
Inorder traversal of binary tree is 4 2 5 1 3>

Tidskompleksitet: PÅ)
Hjelpeplass: Hvis vi ikke vurderer størrelsen på stabelen for funksjonskall, så O(1) ellers O(h) hvor h er høyden på treet.

Forhåndsbestill Traversal :

Forhåndsbestillingsgjennomgang besøker noden i rekkefølgen: Rot -> Venstre -> Høyre

Algoritme for forhåndsbestillingsgjennomgang:

Forhåndsbestilling (tre)

  • Besøk roten.
  • Gå gjennom det venstre undertreet, dvs. ring Preorder (venstre->undertre)
  • Gå gjennom høyre undertre, dvs. ring Preorder (høyre->undertre)

Bruk av forhåndsbestillingsgjennomgang:

  • Forhåndsbestillingsgjennomgang brukes til å lage en kopi av treet.
  • Forhåndsbestillingsgjennomgang brukes også for å få prefiksuttrykk på et uttrykkstre.

Kodebit for forhåndsbestilling:

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);  // Nå gjentakelse på høyre undertre printPreorder(node->høyre); }>
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);  // Deretter gjentas på venstre undertre printPreorder(node->venstre);  // Nå gjentakelse på høyre undertre printPreorder(node->høyre); }>
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); }>
Produksjon 
Preorder traversal of binary tree is 1 2 4 5 3>

Tidskompleksitet: PÅ)
Hjelpeplass: Hvis vi ikke vurderer størrelsen på stabelen for funksjonskall, så O(1) ellers O(h) hvor h er høyden på treet.

Postordregjennomgang :

Postordre-gjennomgang besøker noden i rekkefølgen: Venstre -> Høyre -> Rot

Algoritme for postordreovergang:

Algoritme Postordre (tre)

  • Gå gjennom det venstre undertreet, dvs. ring Postorder(venstre->undertre)
  • Gå gjennom høyre undertre, dvs. ring Postorder (høyre->undertre)
  • Besøk roten

Bruk av postordregjennomgang:

  • Postordre-traversering brukes til å slette treet. Se spørsmålet om sletting av et tre for detaljer.
  • Postordre-traversal er også nyttig for å få postfix-uttrykket til et uttrykkstre.
  • Postordre-traversering kan hjelpe i søppelinnsamlingsalgoritmer, spesielt i systemer der manuell minnebehandling brukes.

Kodebit for postordregjennomgang:

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);  // Deretter gjentas på høyre undertre printPostorder(node->høyre);  // Nå håndtere node cout<< 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);  // Deretter gjentas på høyre undertre printPostorder(node->høyre);  // Håndter nå 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 + ' '); }>
Produksjon 
Postorder traversal of binary tree is 4 5 2 3 1>

Nivå ordregjennomgang :

Nivå ordregjennomgang besøker alle noder som er tilstede på samme nivå før du besøker neste nivå.

Algoritme for gjennomgang av nivåordre:

LevelOrder(tre)

  • Opprett en tom kø Q
  • Sett rotnoden til treet i kø til Q
  • Sløyfe mens Q ikke er tom
    • Sett en node i kø fra Q og besøk den
    • Sett det venstre underordnet i køen til noden hvis det finnes
    • Sett det riktige underordnede av noden i kø hvis det finnes

Bruk av nivårekkefølge:

  • Level Order Traversal brukes hovedsakelig som Breadth First Search for å søke eller behandle noder nivå for nivå.
  • Nivå Ordregjennomgang brukes også til Treserialisering og deserialisering .

Kodebit for nivåbestillingsgjennomgang:

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 og initialiser høyde q.push(root);  while (q.empty() == false) { // Skriv ut forsiden av 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->venstre) enQueue(queue, &rear, temp_node->venstre);  // Enqueue right child if (temp_node->right) enQueue(queue, &rear, temp_node->right);  // Dequeue node og gjø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(root);  mens (!queue.isEmpty()) { // poll() fjerner det nåværende hodet.  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): # Skriv ut foran køen og # fjern den fra køen print(queue[0].data, end=' ') node = queue.pop(0) # Enqueue left child hvis node.left ikke er Ingen: queue.append(node.left) # Sett i kø høyre underordnet 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ø.Kø(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);  }  } }>

Andre trekryssinger:

  1. Grensegjennomgang
  2. Diagonal traversering

1. Grensegjennomgang :

Grensegjennomgang av et tre inkluderer:

  • venstre grense (noder til venstre unntatt bladnoder)
  • blader (består bare av bladnodene)
  • høyre grense (noder til høyre unntatt bladnoder)

Algoritme for grenseovergang:

BoundaryTraversal(tre)

  • Hvis root ikke er null:
    • Skriv ut rotens data
    • PrintLeftBoundary(root->venstre) // Skriv ut de venstre grensenodene
    • PrintLeafNodes(root->venstre) // Skriv ut bladnodene til venstre undertre
    • PrintLeafNodes(root->right) // Skriv ut bladnodene til høyre undertre
    • PrintRightBoundary(root->right) // Skriv ut de høyre grensenodene

Bruk av grenseovergang:

  • Grenseoverskridelse hjelper til med å visualisere den ytre strukturen til et binært tre, og gir innsikt i dets form og grenser.
  • Grensekryssing gir en måte å få tilgang til og modifisere disse nodene, og muliggjør operasjoner som beskjæring eller reposisjonering av grensenoder.

2. Diagonal traversering

I Diagonal Traversal of a Tree vil alle nodene i en enkelt diagonal bli skrevet ut én etter én.

Algoritme for diagonal traversering:

DiagonalTraversal(tre):

  • Hvis root ikke er null:
    • Lag et tomt kart
    • DiagonalTraversalUtil(root, 0, M) // Ring hjelpefunksjon med innledende diagonalnivå 0
    • For hvert nøkkel-verdi-par (diagonalLevel, noder) i M:
      • For hver node i noder:
      • Skriv ut nodens data

DiagonalTraversalUtil(node, diagonalLevel, M):

  • Hvis noden er null:
  • Komme tilbake
  • Hvis diagonalLevel ikke er til stede i M:
    • Opprett en ny liste i M for diagonalLevel
  • Legg til nodens data til listen på M[diagonalLevel]
  • DiagonalTraversalUtil(node->venstre, diagonalLevel + 1, M) // Traverser venstre barn med økt diagonalnivå
  • DiagonalTraversalUtil(node->høyre, diagonalLevel, M) // Traverser høyre barn med samme diagonalnivå

Bruk av diagonal traversering:

  • Diagonal traversering hjelper til med å visualisere den hierarkiske strukturen til binære trær, spesielt i trebaserte datastrukturer som binære søketrær (BST) og haugtrær.
  • Diagonal traversering kan brukes til å beregne banesummer langs diagonaler i et binært tre.

Ofte stilte spørsmål (FAQs) om trevandringsteknikker:

1. Hva er tretraverseringsteknikker?

Teknikker for tregjennomgang er metoder som brukes til å besøke og behandle alle noder i en tredatastruktur. De lar deg få tilgang til hver node nøyaktig én gang på en systematisk måte.

2. Hva er de vanlige typene trekryssing?

De vanlige typene trekryssing er: Inorder-traversal, Preorder-traversal, Postorder-traversal, Nivåordre-traversal (Bredth-First Search)

innsettingspyton

3. Hva er Inorder-traversal?

Inorder-traversal er en dybde-først-traversal-metode der noder besøkes i rekkefølgen: venstre undertre, gjeldende node, høyre undertre.

4. Hva er preorder traversal?

Preorder-traversal er en dybde-først-traversal-metode der noder besøkes i rekkefølgen: gjeldende node, venstre undertre, høyre undertre.

5. Hva er postordregjennomgang?

Postorder-traversal er en dybde-først-traversalmetode der noder besøkes i rekkefølgen: venstre undertre, høyre undertre, gjeldende node.

6. Hva er nivåordregjennomgang?

Nivårekkefølgegjennomgang, også kjent som Breadth-First Search (BFS), besøker noder nivå for nivå, starter fra roten og flytter til neste nivå før de krysser dypere.

7. Når bør jeg bruke hver traverseringsteknikk?

Inorder-traversering brukes ofte for binære søketrær for å få noder i sortert rekkefølge.

Forhåndsbestilling er nyttig for å lage en kopi av treet.

Postorder-traversering brukes ofte i uttrykkstrær for å evaluere uttrykk.

Nivårekkefølgegjennomgang er nyttig for å finne den korteste veien mellom noder.

8. Hvordan implementerer jeg tregjennomgangsalgoritmer?

Tretraversalalgoritmer kan implementeres rekursivt eller iterativt, avhengig av de spesifikke kravene og programmeringsspråket som brukes.

9. Kan tretraversalalgoritmer brukes på andre trelignende strukturer?

Ja, tretraversalalgoritmer kan tilpasses for å krysse andre trelignende strukturer som binære hauger, n-ære trær og grafer representert som trær.

10. Er det noen ytelseshensyn ved valg av traverseringsteknikk?

Ytelseshensyn avhenger av faktorer som størrelsen og formen på treet, tilgjengelig minne og spesifikke operasjoner som utføres under kryssing. Generelt kan valg av traverseringsteknikk påvirke effektiviteten til visse operasjoner, så det er viktig å velge den mest passende metoden for din spesifikke brukssituasjon.

Noen andre viktige opplæringsprogrammer:

  • DSA veiledning
  • Opplæring i systemdesign
  • Veikart for programvareutvikling
  • Veikart for å bli produktsjef
  • Lær SAP
  • Lær SEO