logo

TechCodeview

Techniky procházení stromu – Výukové programy pro datovou strukturu a algoritmus

Techniky procházení stromů zahrnují různé způsoby, jak navštívit všechny uzly stromu. Na rozdíl od lineárních datových struktur (Array, Linked List, Queues, Stacks atd.), které mají pouze jeden logický způsob, jak jimi procházet, lze stromy procházet různými způsoby. V tomto článku budeme diskutovat o všech technikách procházení stromů spolu s jejich použitím.

Obsah



Význam procházení stromu:

Procházení stromů odkazuje na proces návštěvy nebo přístupu ke každému uzlu stromu přesně jednou v určitém pořadí. Algoritmy procházení stromů nám pomáhají navštívit a zpracovat všechny uzly stromu. Protože strom není lineární datová struktura, existuje několik uzlů, které můžeme po návštěvě určitého uzlu navštívit. Existuje několik technik procházení stromem, které rozhodují o pořadí, ve kterém se mají navštívit uzly stromu.

Techniky procházení stromů:

Stromovou datovou strukturu lze procházet následujícími způsoby:

  • Depth First Search nebo DFS
    • Inorder Traversal
    • Předobjednávka Traversal
    • Přechod poštovní poukázkou
  • Level Order Traversal nebo Breadth First Search nebo BFS

Inorder Traversal :

Inorder traversal navštíví uzel v pořadí: Vlevo -> Kořen -> Vpravo


eol v pythonu

Algoritmus pro procházení Inorder Traversal:

Inorder (strom)

  • Projděte levý podstrom, tj. zavolejte Inorder(left->subtree)
  • Navštivte kořen.
  • Projděte pravý podstrom, tj. zavolejte Inorder(pravý->podstrom)

Použití Inorder Traversal:

  • V případě binárních vyhledávacích stromů (BST) dává Inorder traversal uzly v neklesajícím pořadí.
  • Pro získání uzlů BST v nerostoucím pořadí lze použít variantu Inorder traversal, kde je Inorder traversal obrácený.
  • Inorder traversal lze použít k vyhodnocení aritmetických výrazů uložených ve stromech výrazů.

Fragment kódu pro procházení řádků:

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->vlevo, odjet);  // Poté vytiskněte data uzlu cout<< node->data<< ' ';  // Now recur on right child  printInorder(node->že jo); }>
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->vlevo, odjet);  // Poté vytiskne data uzlu printf('%d ', node->data);  // Nyní se opakujte u pravého potomka printInorder(node->right); }>
Jáva 
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ýstup 
Inorder traversal of binary tree is 4 2 5 1 3>

Časová náročnost: NA)
Pomocný prostor: Pokud neuvažujeme velikost zásobníku pro volání funkcí, pak O(1) jinak O(h), kde h je výška stromu.

Předobjednávka Traversal :

Procházení předobjednávky navštíví uzel v pořadí: Root -> Left -> Right

Algoritmus pro přechod předobjednávky:

Předobjednávka (strom)

  • Navštivte kořen.
  • Projděte levý podstrom, tj. zavolejte Preorder(left->subtree)
  • Projděte pravý podstrom, tj. zavolejte Preorder (pravý->podstrom)

Použití předobjednávky Traversal:

  • Předobjednávka se používá k vytvoření kopie stromu.
  • Předobjednávka se také používá k získání předponových výrazů ve stromu výrazů.

Fragment kódu pro přechod předobjedná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->data<< ' ';  // Then recur on left subtree  printPreorder(node->vlevo, odjet);  // Nyní se opakujte na pravém podstromu 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);  // Poté se opakujte na levém podstromu printPreorder(node->left);  // Nyní se opakujte na pravém podstromu printPreorder(node->right); }>
Jáva 
// 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ýstup 
Preorder traversal of binary tree is 1 2 4 5 3>

Časová náročnost: NA)
Pomocný prostor: Pokud neuvažujeme velikost zásobníku pro volání funkcí, pak O(1) jinak O(h), kde h je výška stromu.

Přechod poštovní poukázkou :

Postorder traversal navštíví uzel v pořadí: Vlevo -> Vpravo -> Kořen

Algoritmus pro Postorder Traversal:

Algoritmus Poštovní poukázka (strom)

  • Projděte levý podstrom, tj. zavolejte Postorder(left->subtree)
  • Projděte pravý podstrom, tj. zavolejte Postorder(pravý->podstrom)
  • Navštivte kořen

Použití Mailorder Traversal:

  • Postorder traversal se používá k odstranění stromu. Vidět otázka na smazání stromu pro detaily.
  • Postorder traversal je také užitečný pro získání postfixového výrazu stromu výrazů.
  • Postorder traversal může pomoci v algoritmech garbage collection, zejména v systémech, kde se používá manuální správa paměti.

Fragment kódu pro procházení zásilkové 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->vlevo, odjet);  // Poté se opakujte na pravém podstromu printPostorder(node->right);  // Nyní se vypořádejte s uzlem 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->vlevo, odjet);  // Poté se opakujte na pravém podstromu printPostorder(node->right);  // Nyní se vypořádejte s uzlem printf('%d ', node->data); }>
Jáva 
// 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ýstup 
Postorder traversal of binary tree is 4 5 2 3 1>

Level Order Traversal :

Level Order Traversal úplně navštíví všechny uzly na stejné úrovni, než navštíví další úroveň.

s plnou formou

Algoritmus pro přechod na úrovni objednávky:

LevelPorder (strom)

  • Vytvořte prázdnou frontu Q
  • Zařaďte kořenový uzel stromu do fronty Q
  • Smyčka, zatímco Q není prázdné
    • Vyřaďte uzel z fronty Q a navštivte jej
    • Zařaďte do fronty levý podřízený uzel z fronty, pokud existuje
    • Zařaďte do fronty pravý podřízený uzel z fronty, pokud existuje

Použití pořadí úrovní:

  • Level Order Traversal se používá hlavně jako Breadth First Search k prohledávání nebo zpracování uzlů úroveň po úrovni.
  • Level Order traversal se také používá pro Serializace a deserializace stromu .

Fragment kódu pro procházení objednávky úrovně:

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;  // Zařadit kořen do fronty a inicializovat výšku q.push(root);  while (q.empty() == false) { // Tisk přední části fronty a její odstranění z fronty Uzel* node = q.front();  cout<< node->data<< ' ';  q.pop();  // Enqueue left child  if (node->vlevo != NULL) q.push(uzel->left);  // Zařadit 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->data);  // Zařadit do fronty levého potomka if (temp_node->left) enQueue(queue, &rear, temp_node->left);  // Zařadit do fronty pravého potomka if (temp_node->right) enQueue(queue, &rear, temp_node->right);  // Dequeue uzel a udělá z něj temp_node temp_node = deQueue(queue, &front);  } }>
Jáva 
// Given a binary tree. Print // its nodes in level order // using array for implementing queue void printLevelOrder() {  Queuefronta = nový LinkedList();  fronta.add(kořen);  while (!queue.isEmpty()) { // poll() odstraní současnou hlavičku.  Node tempNode = queue.poll();  System.out.print(tempNode.data + ' ');  // Zařadit levého potomka if (tempNode.left != null) { queue.add(tempNode.left);  } // Zařadit do fronty 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): # Vytisknout přední část fronty a # odstranit ji z fronty print(queue[0].data, end=' ') node = queue.pop(0) # Zařadit do fronty levé potomky, pokud node.left není Žádný: queue.append(node.left) # Zařadit do fronty pravého potomka, pokud node.right není Žádný: queue.append(node.right)>
C# 
// Given a binary tree. Print // its nodes in level order using // array for implementing queue void printLevelOrder() {  Queuefronta = nová fronta();  fronta.Enqueue(kořen);  while (queue.Count != 0) { Node tempNode = queue.Dequeue();  Console.Write(tempNode.data + ' ');  // Zařadit levého potomka if (tempNode.left != null) { queue.Enqueue(tempNode.left);  } // Zařadit do fronty 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);  }  } }>

Další průchody stromů:

  1. Přechod hranic
  2. Diagonální přechod

1. Přechod hranic :

Přechod hranic strom obsahuje:

  • levá hranice (uzly vlevo kromě listových uzlů)
  • listy (skládají se pouze z listových uzlů)
  • pravá hranice (uzly vpravo kromě listových uzlů)

Algoritmus pro přechod hranic:

BoundaryTraversal (strom)

  • Pokud root není null:
    • Vytiskněte data roota
    • PrintLeftBoundary(root->left) // Tisk uzlů levé hranice
    • PrintLeafNodes(root->left) // Tisk listových uzlů levého podstromu
    • PrintLeafNodes(root->right) // Tisk listových uzlů pravého podstromu
    • PrintRightBoundary(root->right) // Vytiskne pravé hraniční uzly

Použití hraničního přechodu:

  • Procházení hranic pomáhá vizualizovat vnější strukturu binárního stromu a poskytuje pohled na jeho tvar a hranice.
  • Boundary traversal poskytuje způsob, jak získat přístup k těmto uzlům a upravovat je, což umožňuje operace, jako je ořezávání nebo přemístění hraničních uzlů.

2. Diagonální přechod

V Diagonálním průchodu stromu budou všechny uzly v jedné diagonále vytištěny jeden po druhém.

Algoritmus pro diagonální přechod:

DiagonalTraversal(strom):

  • Pokud root není null:
    • Vytvořte prázdnou mapu
    • DiagonalTraversalUtil(root, 0, M) // Volání pomocné funkce s počáteční úrovní úhlopříčky 0
    • Pro každý pár klíč–hodnota (diagonalLevel, uzly) v M:
      • Pro každý uzel v uzlech:
      • Vytisknout data uzlu

DiagonalTraversalUtil(uzel, diagonalLevel, M):

  • Pokud je uzel null:
  • Vrátit se
  • Pokud diagonalLevel není přítomen v M:
    • Vytvořte nový seznam v M pro diagonalLevel
  • Připojit data uzlu do seznamu na M[diagonalLevel]
  • DiagonalTraversalUtil(node->left, diagonalLevel + 1, M) // Přechod levého potomka se zvýšenou úrovní úhlopříčky
  • DiagonalTraversalUtil(node->right, diagonalLevel, M) // Přechod vpravo podřízeného se stejnou úrovní úhlopříčky

Použití diagonálního přechodu:

  • Diagonální procházení pomáhá při vizualizaci hierarchické struktury binárních stromů, zejména ve stromových datových strukturách, jako jsou binární vyhledávací stromy (BST) a haldové stromy.
  • Diagonální procházení lze použít k výpočtu součtů cest podél diagonál v binárním stromu.

Často kladené otázky (FAQ) o technikách procházení stromů:

1. Jaké jsou techniky procházení stromů?

Techniky procházení stromů jsou metody používané k návštěvě a zpracování všech uzlů ve stromové datové struktuře. Umožňují vám systematickým způsobem přistupovat ke každému uzlu přesně jednou.

2. Jaké jsou běžné typy projíždění stromů?

Běžné typy procházení stromem jsou: Procházení v pořadí, Procházení před objednávkou, Procházení postorderu, Procházení podle pořadí (Breadth-First Search)

rozdíl mezi gigabajtem a megabajtem

3. Co je Inorder traversal?

Inorder traversal je metoda procházení do hloubky, kde jsou uzly navštěvovány v pořadí: levý podstrom, aktuální uzel, pravý podstrom.

4. Co je to předobjednávka?

Preorder traversal je metoda procházení do hloubky, kde jsou uzly navštěvovány v pořadí: aktuální uzel, levý podstrom, pravý podstrom.

5. Co je to průchod poštovní poukázkou?

Postorder traversal je metoda procházení do hloubky, kde jsou uzly navštěvovány v pořadí: levý podstrom, pravý podstrom, aktuální uzel.

6. Co je procházení řádem úrovně?

Procházení podle pořadí úrovní, známé také jako BFS (Breadth-First Search), navštěvuje uzly úroveň po úrovni, počínaje kořenem a přesouvá se na další úroveň, než projde hlouběji.

7. Kdy bych měl použít jednotlivé techniky procházení?

Inorder traversal se často používá pro binární vyhledávací stromy k získání uzlů v seřazeném pořadí.

Procházení předobjednávky je užitečné pro vytvoření kopie stromu.

Postorder traversal se běžně používá ve stromech výrazů k vyhodnocení výrazů.

Procházení pořadí úrovní je užitečné pro nalezení nejkratší cesty mezi uzly.

8. Jak implementuji algoritmy procházení stromů?

Algoritmy procházení stromu lze implementovat rekurzivně nebo iterativně, v závislosti na konkrétních požadavcích a použitém programovacím jazyce.

9. Lze algoritmy procházení stromů aplikovat na jiné stromové struktury?

Ano, algoritmy procházení stromů lze upravit tak, aby procházely jinými stromovými strukturami, jako jsou binární haldy, n-ární stromy a grafy reprezentované jako stromy.

10. Jsou při výběru traverzální techniky nějaké úvahy o výkonu?

Úvahy o výkonu závisí na faktorech, jako je velikost a tvar stromu, dostupná paměť a konkrétní operace prováděné během procházení. Obecně platí, že výběr techniky procházení může ovlivnit efektivitu určitých operací, takže je důležité zvolit nejvhodnější metodu pro váš konkrétní případ použití.

Některé další důležité tutoriály:

  • Výukový program DSA
  • Výukový program návrhu systému
  • Plán vývoje softwaru
  • Plán, jak se stát produktovým manažerem
  • Naučte se SAP
  • Naučte se SEO