PREORDENA TRAVERSAL OF BINARY TREE

Recorregut de comanda prèvia es defineix com un tipus de travessa d'arbres que segueix la política Arrel-Esquerra-Dreta on:

Primer es visita el node arrel del subarbre.

Aleshores es recorre el subarbre esquerre.

Finalment, es recorre el subarbre dret.

Travessa de comanda prèvia

Algoritme per a la preordre de travessia de l'arbre binari

L'algoritme per al recorregut de la comanda prèvia es mostra de la següent manera:

Comanda prèvia (arrel):

Seguiu els passos 2 a 4 fins que root != NULL

Escriu arrel -> dades

Reserva prèvia (arrel -> esquerra)

Reserva prèvia (arrel -> dreta)

Bucle final

Com funciona la preordre Traversal de l'arbre binari?

Considereu l'arbre següent:

Exemple d'arbre binari

Si realitzem un recorregut de preordre en aquest arbre binari, el recorregut serà el següent:

Pas 1: Al principi es visitarà l'arrel, és a dir, el node 1.

Es visita el node 1

Pas 2: Després d'això, travessa pel subarbre esquerre. Ara es visita l'arrel del subarbre esquerre, és a dir, es visita el node 2.

Es visita el node 2

Pas 3: De nou es recorre el subarbre esquerre del node 2 i es visita l'arrel d'aquest subarbre, és a dir, el node 4.

Es visita el node 4

Pas 4: No hi ha cap subarbre de 4 i es visita el subarbre esquerre del node 2. Així que ara es recorrerà el subarbre dret del node 2 i es visitarà l'arrel d'aquest subarbre, és a dir, el node 5.

Es visita el node 5

Pas 5: Es visita el subarbre esquerre del node 1. Així que ara es recorrerà el subarbre dret del node 1 i es visitarà el node arrel, és a dir, el node 3.

Es visita el node 3

Pas 6: El node 3 no té cap subarbre esquerre. Així, es recorrerà el subarbre dret i es visitarà l'arrel del subarbre, és a dir, el node 6. Després d'això, no hi ha cap node que encara no estigui travessat. Així s'acaba el recorregut.

Es visita l'arbre complet

Per tant, l'ordre de recorregut dels nodes és 1 -> 2 -> 4 -> 5 -> 3 -> 6 .

Programa per implementar el recorregut de preordre de l'arbre binari

A continuació es mostra la implementació del codi del recorregut de la comanda prèvia:

C++

  // C++ program for preorder traversals #include  using namespace std; // Structure of a Binary Tree Node struct Node {  int data;  struct Node *left, *right;  Node(int v)  {  data = v;  left = right = NULL;  } }; // Function to print preorder traversal void printPreorder(struct Node* node) {  if (node == NULL)  return;  // Deal with the node  cout  < < node->dades < < ' ';  // Recur on left subtree  printPreorder(node->esquerra);  // Es repeteix al subarbre dret printPreorder(node->right); } // Codi del controlador int main() { struct Node* root = new Node (1);  arrel->esquerra = nou Node (2);  arrel->dreta = nou Node (3);  arrel->esquerra->esquerra = nou Node (4);  arrel->esquerra->dreta = nou Node (5);  arrel->dreta->dreta = nou Node (6);  // Crida a la funció cout < < 'Preorder traversal of binary tree is: 
';  printPreorder(root);  return 0; }

Java

  // Java program for preorder traversals class Node {  int data;  Node left, right;  public Node(int item) {  data = item;  left = right = null;  } } class BinaryTree {  Node root;  BinaryTree() {  root = null;  }  // Function to print preorder traversal  void printPreorder(Node node) {  if (node == null)  return;  // Deal with the node  System.out.print(node.data + ' ');  // Recur on left subtree  printPreorder(node.left);  // Recur on right subtree  printPreorder(node.right);  }  // Driver code  public static void main(String[] args) {  BinaryTree tree = new BinaryTree();  // Constructing the binary tree  tree.root = new Node(1);  tree.root.left = new Node(2);  tree.root.right = new Node(3);  tree.root.left.left = new Node(4);  tree.root.left.right = new Node(5);  tree.root.right.right = new Node(6);  // Function call  System.out.println('Preorder traversal of binary tree is: ');  tree.printPreorder(tree.root);  } }

Python 3

  # Python program for preorder traversals # Structure of a Binary Tree Node class Node: def __init__(self, v): self.data = v self.left = None self.right = None # Function to print preorder traversal def printPreorder(node): if node is None: return # Deal with the node print(node.data, end=' ') # Recur on left subtree printPreorder(node.left) # Recur on right subtree printPreorder(node.right) # Driver code if __name__ == '__main__': root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.right = Node(6) # Function call print('Preorder traversal of binary tree is:') printPreorder(root)

  // C# program for preorder traversals using System; // Structure of a Binary Tree Node public class Node {  public int data;  public Node left, right;  public Node(int v)  {  data = v;  left = right = null;  } } // Class to print preorder traversal public class BinaryTree {  // Function to print preorder traversal  public static void printPreorder(Node node)  {  if (node == null)  return;  // Deal with the node  Console.Write(node.data + ' ');  // Recur on left subtree  printPreorder(node.left);  // Recur on right subtree  printPreorder(node.right);  }  // Driver code  public static void Main()  {  Node root = new Node(1);  root.left = new Node(2);  root.right = new Node(3);  root.left.left = new Node(4);  root.left.right = new Node(5);  root.right.right = new Node(6);  // Function call  Console.WriteLine(  'Preorder traversal of binary tree is: ');  printPreorder(root);  } } // This code is contributed by Susobhan Akhuli

Javascript

  // Structure of a Binary Tree Node class Node {  constructor(v) {  this.data = v;  this.left = null;  this.right = null;  } } // Function to print preorder traversal function printPreorder(node) {  if (node === null) {  return;  }  // Deal with the node  console.log(node.data);  // Recur on left subtree  printPreorder(node.left);  // Recur on right subtree  printPreorder(node.right); } // Driver code function main() {  const root = new Node(1);  root.left = new Node(2);  root.right = new Node(3);  root.left.left = new Node(4);  root.left.right = new Node(5);  root.right.right = new Node(6);  // Function call  console.log('Preorder traversal of binary tree is:');  printPreorder(root); } main();

Sortida

Preorder traversal of binary tree is: 1 2 4 5 3 6

Explicació:

Com funciona el recorregut de la comanda prèvia

Anàlisi de complexitat:

Complexitat temporal: O(N) on N és el nombre total de nodes. Perquè travessa tots els nodes almenys una vegada.
Espai auxiliar:

O(1) si no es considera cap espai de pila de recursivitat.
D'una altra manera, O(h) on h és l'alçada de l'arbre
En el pitjor dels casos, h pot ser el mateix que N (quan l'arbre és un arbre esbiaixat)
En el millor dels casos, h pot ser el mateix que calma (quan l'arbre és un arbre complet)

Casos d'ús de Traversal de comanda prèvia:

Alguns casos d'ús del recorregut de pre-ordre són:

Això s'utilitza sovint per crear una còpia d'un arbre.
També és útil obtenir l'expressió del prefix d'un arbre d'expressions.

Articles relacionats:

Tipus de travessa d'arbres
Travessia iterativa de preordre
Comproveu si la matriu donada pot representar el recorregut de la comanda prèvia de BST
Preordre a partir de recorreguts inordre i postordre
Trobeu el node nè en el recorregut de preordre d'un arbre binari
Travessa prèvia d'un arbre N-ari