logo

TechCodeview

Tècniques de travessa d'arbres - Estructura de dades i tutorials d'algorisme

Tècniques de travessa d'arbres inclou diverses maneres de visitar tots els nodes de l'arbre. A diferència de les estructures de dades lineals (array, llista enllaçada, cues, piles, etc.) que només tenen una manera lògica de recórrer-les, els arbres es poden recórrer de diferents maneres. En aquest article, parlarem de totes les tècniques de travessa d'arbres juntament amb els seus usos.



Taula de contingut

Significat de la travessa d'arbres:

Travessa d'arbres fa referència al procés de visitar o accedir a cada node de l'arbre exactament una vegada en un ordre determinat. Els algorismes de recorregut de l'arbre ens ajuden a visitar i processar tots els nodes de l'arbre. Com que l'arbre no és una estructura de dades lineal, hi ha múltiples nodes que podem visitar després de visitar un node determinat. Hi ha múltiples tècniques de recorregut d'arbres que decideixen l'ordre en què s'han de visitar els nodes de l'arbre.

Tècniques de travessa d'arbres:



Una estructura de dades d'arbre es pot recórrer de les maneres següents:

  • Cerca en profunditat o DFS
    • Travessia de l'ordre
    • Reserva Traversal
    • Travessia postal
  • Travessament de l'ordre de nivell o cerca en primer lloc o BFS

Travessia de l'ordre :

El recorregut en ordre visita el node en l'ordre: Esquerra -> Arrel -> Dreta




Algoritme per al desplaçament de l'ordre:

Inorde (arbre)

  • Travessa el subarbre esquerre, és a dir, crida a Inorder(esquerra->subarbre)
  • Visita l'arrel.
  • Travessa el subarbre dret, és a dir, crida a Inorder (dreta->subarbre)

Usos de la travessa en ordre:

  • En el cas dels arbres de cerca binaris (BST), el recorregut Inorder dóna nodes en ordre no decreixent.
  • Per obtenir els nodes de BST en ordre no creixent, es pot utilitzar una variació del recorregut Inorder on s'inverteix el recorregut Inorder.
  • El recorregut en ordre es pot utilitzar per avaluar expressions aritmètiques emmagatzemades en arbres d'expressions.

Fragment de codi per a la transmissió en ordre:

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->esquerra);  // A continuació, imprimiu les dades del node cout<< node->dades<< ' ';  // Now recur on right child  printInorder(node->dret); }>>>Cdata);  // Ara es repeteix al fill dret printInorder(node->right); }>>>Java
Python 3 
# 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); }>
Sortida 
Inorder traversal of binary tree is 4 2 5 1 3>

Complexitat temporal: O(N)
Espai auxiliar: Si no tenim en compte la mida de la pila per a les crides de funció, aleshores O(1) en cas contrari O(h) on h és l'alçada de l'arbre.

Reserva Traversal :

El recorregut de la comanda prèvia visita el node en l'ordre: Arrel -> Esquerra -> Dreta

Algoritme per a la pre-ordre transversal:

Comanda prèvia (arbre)

  • Visita l'arrel.
  • Travessa el subarbre esquerre, és a dir, crida a Preorder(esquerra->subarbre)
  • Travessa el subarbre dret, és a dir, crida a Preorder (dreta->subarbre)

Usos del trajecte de comanda prèvia:

  • El recorregut de la comanda prèvia s'utilitza per crear una còpia de l'arbre.
  • El recorregut de preordre també s'utilitza per obtenir expressions de prefix en un arbre d'expressions.

Fragment de codi per a la reserva prèvia:

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->dades<< ' ';  // Then recur on left subtree  printPreorder(node->esquerra);  // Ara es repeteix al subarbre dret printPreorder(node->right); }>>>Cdades);  // Després es repeteix al subarbre esquerre printPreorder(node->esquerra);  // Ara es repeteix al subarbre dret printPreorder(node->right); }>>>Java
Python 3 
# 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); }>
Sortida 
Preorder traversal of binary tree is 1 2 4 5 3>

Complexitat temporal: O(N)
Espai auxiliar: Si no tenim en compte la mida de la pila per a les crides de funció, aleshores O(1) en cas contrari O(h) on h és l'alçada de l'arbre.

Travessia postal :

El recorregut posterior a la comanda visita el node en l'ordre: Esquerra -> Dreta -> Arrel

Algoritme per a la travessia posterior a la comanda:

Algoritme Ordre postal (arbre)

  • Travessa el subarbre esquerre, és a dir, crida a Postorder(esquerra->subarbre)
  • Travessa el subarbre dret, és a dir, crida a Postorder (dreta->subarbre)
  • Visita l'arrel

Usos de Mailorder Traversal:

  • El recorregut posterior a la comanda s'utilitza per eliminar l'arbre. Mireu la pregunta per a la supressió d'un arbre per als detalls.
  • El recorregut posterior a l'ordre també és útil per obtenir l'expressió postfix d'un arbre d'expressions.
  • El recorregut posterior a la comanda pot ajudar en els algorismes de recollida d'escombraries, especialment en sistemes on s'utilitza la gestió manual de la memòria.

Fragment de codi per a Mailorder 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->esquerra);  // Després es repeteix al subarbre dret printPostorder(node->right);  // Ara tracteu amb el node cout<< node->dades<< ' '; }>
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->esquerra);  // Després es repeteix al subarbre dret printPostorder(node->right);  // Ara tracteu amb el node printf('%d', node->data); }>>>Java
Python 3 
# 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 + ' '); }>
Sortida 
Postorder traversal of binary tree is 4 5 2 3 1>

Travessament de l'ordre de nivell :

Travessament de l'ordre de nivell visita tots els nodes presents al mateix nivell completament abans de visitar el següent nivell.

Algoritme per a la transmissió de l'ordre de nivell:

LevelOrder (arbre)

  • Creeu una cua buida Q
  • Posa a la cua el node arrel de l'arbre a Q
  • Bucle mentre Q no estigui buit
    • Deixeu de cua un node de Q i visiteu-lo
    • Posa a la cua el fill esquerre del node retirat de la cua si existeix
    • Posa a la cua el fill dret del node retirat de la cua si existeix

Usos de l'ordre de nivell:

  • La travessa de l'ordre de nivell s'utilitza principalment com a Breadth First Search per cercar o processar nodes nivell per nivell.
  • També s'utilitza el recorregut de l'ordre de nivell Serialització i deserialització d'arbres .

Fragment de codi per al desplaçament de l'ordre de nivell:

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;  // Col·loqueu l'arrel a la cua i inicialitzeu l'alçada q.push(arrel);  while (q.empty() == false) { // Imprimeix la part davantera de la cua i elimina-la de la cua Node* node = q.front();  cout<< node->dades<< ' ';  q.pop();  // Enqueue left child  if (node->esquerra != NULL) q.push(node->esquerra);  // Posa a la cua el fill dret si (node->right != NULL) q.push(node->right);  } }>>>Cdades);  // Posa a la cua el fill esquerre si (temp_node->esquerra) enQueue(queue, &rear, temp_node->left);  // Posa a la cua fill dret if (temp_node->right) enQueue(queue, &rear, temp_node->right);  // Treu el node de cua i fes-lo temp_node temp_node = deQueue(queue, &front);  } }>>>Java>>Python 3
C# 
// Given a binary tree. Print // its nodes in level order using // array for implementing queue void printLevelOrder() {  Queuequeue = cua nova();  queue.Enqueue(arrel);  while (queue.Count!= 0) { Node tempNode = queue.Dequeue();  Console.Write(tempNode.data + ' ');  // Posa a la cua el fill esquerre si (tempNode.left != null) { queue.Enqueue (tempNode.left);  } // Posa a la cua fill dret si (tempNode.right != null) { queue.Enqueue (tempNode.right);  } } }>>>JavaScript

Altres travessaments d'arbres:

  1. Travessia de límits
  2. Travessia Diagonal

1. Travessia de límits :

Travessia de límits d'un arbre inclou:

  • límit esquerre (nodes de l'esquerra, excepte els nodes de fulla)
  • fulles (consten només dels nodes de les fulles)
  • límit dret (nodes a la dreta exclosos els nodes fulla)

Algorisme per a la travessia de límits:

Travessia límit (arbre)

  • Si l'arrel no és nul·la:
    • Imprimeix les dades de l'arrel
    • PrintLeftBoundary(arrel->esquerra) // Imprimeix els nodes del límit esquerre
    • PrintLeafNodes(root->left) // Imprimeix els nodes full del subarbre esquerre
    • PrintLeafNodes(root->right) // Imprimeix els nodes full del subarbre dret
    • PrintRightBoundary(arrel->right) // Imprimeix els nodes de límit dret

Usos de la travessia de límits:

  • El recorregut de límits ajuda a visualitzar l'estructura exterior d'un arbre binari, proporcionant informació sobre la seva forma i límits.
  • El recorregut de límits proporciona una manera d'accedir i modificar aquests nodes, permetent operacions com ara la poda o el reposicionament dels nodes de límit.

2. Travessia Diagonal

A la Travessia Diagonal d'un Arbre, tots els nodes d'una única diagonal s'imprimiran un a un.

Algorisme per a la travessia diagonal:

Travessia diagonal (arbre):

llista de programes python
  • Si l'arrel no és nul·la:
    • Crea un mapa buit
    • DiagonalTraversalUtil(arrel, 0, M) // Crida a la funció d'ajuda amb el nivell diagonal inicial 0
    • Per a cada parell clau-valor (nivell diagonal, nodes) a M:
      • Per a cada node en nodes:
      • Imprimeix les dades del node

DiagonalTraversalUtil(node, diagonalLevel, M):

  • Si el node és nul:
  • Tornar
  • Si diagonalLevel no està present a M:
    • Creeu una llista nova a M per a diagonalLevel
  • Afegiu les dades del node a la llista a M[diagonalLevel]
  • DiagonalTraversalUtil(node->esquerra, diagonalLevel + 1, M) // Travessa el fill esquerre amb un nivell diagonal augmentat
  • DiagonalTraversalUtil(node->right, diagonalLevel, M) // Travessa el nen dret amb el mateix nivell diagonal

Usos de la travessia diagonal:

  • El recorregut en diagonal ajuda a visualitzar l'estructura jeràrquica dels arbres binaris, especialment en estructures de dades basades en arbres com els arbres de cerca binaris (BST) i els arbres de pila.
  • El recorregut en diagonal es pot utilitzar per calcular les sumes de camins al llarg de les diagonals d'un arbre binari.

Preguntes freqüents (FAQ) sobre tècniques de travessa d'arbres:

1. Què són les tècniques de travessa d'arbres?

Les tècniques de recorregut d'arbres són mètodes utilitzats per visitar i processar tots els nodes d'una estructura de dades d'arbre. Us permeten accedir a cada node exactament una vegada de manera sistemàtica.

2. Quins són els tipus habituals de travessa d'arbres?

Els tipus habituals de travessa d'arbres són: travessa per ordre, travessa per preordre, travessa per postorde, travessa per ordre de nivell (Breadth-First Search)

3. Què és Inorder traversal?

La travessa en ordre és un mètode de travessa en profunditat on els nodes es visiten en l'ordre: subarbre esquerre, node actual, subarbre dret.

4. Què és el recorregut de preordre?

El recorregut de preordre és un mètode de travessa en profunditat on els nodes es visiten en l'ordre: node actual, subarbre esquerre, subarbre dret.

5. Què és el recorregut de mandat postal?

El recorregut posterior a l'ordre és un mètode de travessa en profunditat on els nodes es visiten en l'ordre: subarbre esquerre, subarbre dret, node actual.

6. Què és el recorregut per ordre de nivell?

El recorregut per ordre de nivell, també conegut com a Breadth-First Search (BFS), visita els nodes nivell per nivell, començant des de l'arrel i passant al següent nivell abans d'anar més a fons.

7. Quan he d'utilitzar cada tècnica de recorregut?

El recorregut en ordre s'utilitza sovint per als arbres de cerca binaris per obtenir nodes ordenats.

El recorregut de la comanda prèvia és útil per crear una còpia de l'arbre.

El recorregut posterior a l'ordre s'utilitza habitualment als arbres d'expressions per avaluar expressions.

El recorregut per ordre de nivell és útil per trobar el camí més curt entre els nodes.

8. Com implemento els algorismes de recorregut d'arbres?

Els algorismes de recorregut d'arbres es poden implementar de manera recursiva o iterativa, depenent dels requisits específics i del llenguatge de programació que s'utilitzi.

9. Es poden aplicar algorismes de travessa d'arbres a altres estructures semblants a arbres?

Sí, els algorismes de travessa d'arbres es poden adaptar per travessar altres estructures semblants a arbres, com ara munts binaris, arbres n-aris i gràfics representats com a arbres.

10. Hi ha alguna consideració de rendiment a l'hora d'escollir una tècnica de recorregut?

Les consideracions de rendiment depenen de factors com ara la mida i la forma de l'arbre, la memòria disponible i les operacions específiques que s'estan realitzant durant el recorregut. En general, l'elecció de la tècnica de recorregut pot afectar l'eficiència de determinades operacions, per la qual cosa és important triar el mètode més adequat per al vostre cas d'ús específic.

Alguns altres tutorials importants:

  • Tutorial DSA
  • Tutorial de disseny de sistemes
  • Full de ruta de desenvolupament de programari
  • Full de ruta per convertir-se en Product Manager
  • Aprèn SAP
  • Aprèn SEO