PRECOMANDĂ TRAVERSAREA ARBORELUI BINAR

Precomandă traversare este definit ca un tip de traversarea copacilor care urmează politica Root-Left-Right unde:

Nodul rădăcină al subarborelui este vizitat mai întâi.
Apoi se parcurge subarborele din stânga.
În cele din urmă, subarborele din dreapta este străbătut.

Precomandă traversare

Algoritm pentru traversarea precomandă a arborelui binar

Algoritmul pentru parcurgerea precomenzii este prezentat după cum urmează:

Precomandă (rădăcină):

Urmați pașii de la 2 la 4 până la root != NULL
Scrieți rădăcină -> date
Precomandă (rădăcină -> stânga)
Precomandă (rădăcină -> dreapta)
Sfârșit bucla

Cum funcționează Precomanda Traversal of Binary Tree?

Luați în considerare următorul arbore:

Exemplu de arbore binar

Dacă efectuăm o traversare precomandă în acest arbore binar, atunci traversarea va fi după cum urmează:

Pasul 1: La început va fi vizitată rădăcina, adică nodul 1.

Nodul 1 este vizitat

Pasul 2: După aceasta, traversați în subarborele din stânga. Acum este vizitată rădăcina subarborelui din stânga, adică este vizitat nodul 2.

Nodul 2 este vizitat

Pasul 3: Din nou, subarborele din stânga al nodului 2 este parcurs și rădăcina acelui subarbore, adică nodul 4, este vizitată.

Nodul 4 este vizitat

Pasul 4: Nu există subarborele 4 și este vizitat subarborele din stânga al nodului 2. Deci acum va fi traversat subarborele drept al nodului 2 și va fi vizitată rădăcina acelui subarbore, adică nodul 5.
matrice de șiruri

Nodul 5 este vizitat

Pasul 5: Este vizitat subarborele din stânga al nodului 1. Deci acum va fi traversat subarborele din dreapta al nodului 1 și nodul rădăcină, adică nodul 3, este vizitat.

Nodul 3 este vizitat

Pasul 6: Nodul 3 nu are un subarboresc stâng. Deci subarborele din dreapta va fi parcurs și rădăcina subarborelui, adică nodul 6, va fi vizitată. După aceea, nu mai există niciun nod care să nu fie încă traversat. Deci traversarea se termină.

Se vizitează arborele complet

Deci ordinea de parcurgere a nodurilor este 1 -> 2 -> 4 -> 5 -> 3 -> 6 .

Program de implementare a precomenzii traversării arborelui binar

Mai jos este implementarea codului a traversării precomenzii:

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->date<< ' ';  // Recur on left subtree  printPreorder(node->stânga);  // Recură pe subarborele din dreapta printPreorder(nod->right); } // Cod driver int main() { struct Node* root = new Node(1);  root->left = nou Nod(2);  root->right = nou Nod(3);  rădăcină->stânga->stânga = nou Nod(4);  rădăcină->stânga->dreapta = nou Nod(5);  root->right->right = Nod nou(6);  // Apelul funcției 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);  } }>

Python3

 # 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();>

Ieșire

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

Explicaţie:

Cum funcționează traversarea precomenzilor

Analiza complexității:

Complexitatea timpului: O(N) unde N este numărul total de noduri. Pentru că străbate toate nodurile cel puțin o dată.
Spațiu auxiliar:

O(1) dacă nu se ia în considerare spațiul stivei recursive.
In caz contrar, Oh) unde h este înălțimea copacului
În cel mai rău caz, h poate fi la fel ca N (când copacul este un copac înclinat)
În cel mai bun caz, h poate fi la fel ca calm (când copacul este un copac complet)

Cazuri de utilizare ale traversării precomenzilor:

Unele cazuri de utilizare ale traversării precomenzilor sunt:

Acesta este adesea folosit pentru a crea o copie a unui arbore.
De asemenea, este util să obțineți expresia prefix dintr-un arbore de expresii.

Articole similare:

Tipuri de traversare a copacilor
Parcurs iterativ de precomandă
Verificați dacă matricea dată poate reprezenta traversarea precomandă a BST
Precomandă din traversări în ordine și postcomandă
Găsiți al n-lea nod în parcurgerea precomanda a unui arbore binar
Parcurgerea precomandă a unui arbore N-ary