PREORDINA L'ATTRAVERSAMENTO DELL'ALBERO BINARIO - TECHCODEVIEW.COM

Attraversamento del preordine è definito come un tipo di attraversamento degli alberi che segue la politica Root-Left-Right dove:

Il nodo radice del sottoalbero viene visitato per primo.

Quindi viene attraversato il sottoalbero sinistro.

Alla fine viene attraversato il sottoalbero destro.

Attraversamento del preordine

Algoritmo per l'attraversamento del preordine dell'albero binario

L'algoritmo per l'attraversamento del preordine è mostrato come segue:

Preordine(radice):

Seguire i passaggi da 2 a 4 fino a root != NULL

Scrivi root -> dati

Preordine (radice -> sinistra)

Preordine (root -> destra)

Fine del ciclo

Come funziona l'attraversamento del preordine dell'albero binario?

Consideriamo il seguente albero:

Esempio di albero binario

Se eseguiamo un attraversamento del preordine in questo albero binario, l'attraversamento sarà il seguente:

Passo 1: Inizialmente verrà visitata la root, ovvero il nodo 1.

Il nodo 1 viene visitato

Passo 2: Successivamente, attraversa il sottoalbero di sinistra. Ora viene visitata la radice del sottoalbero sinistro, ovvero viene visitato il nodo 2.

Viene visitato il nodo 2

Passaggio 3: Anche in questo caso viene attraversato il sottoalbero sinistro del nodo 2 e viene visitata la radice di quel sottoalbero, ovvero il nodo 4.

Viene visitato il nodo 4

Passaggio 4: Non esiste un sottoalbero di 4 e viene visitato il sottoalbero sinistro del nodo 2. Quindi ora verrà attraversato il sottoalbero destro del nodo 2 e verrà visitata la radice di quel sottoalbero, ovvero il nodo 5.

Viene visitato il nodo 5

Passaggio 5: Viene visitato il sottoalbero sinistro del nodo 1. Quindi ora verrà attraversato il sottoalbero destro del nodo 1 e verrà visitato il nodo radice, ovvero il nodo 3.

Viene visitato il nodo 3

Passaggio 6: Il nodo 3 non ha un sottoalbero sinistro. Quindi verrà attraversato il sottoalbero destro e verrà visitata la radice del sottoalbero, ovvero il nodo 6. Dopodiché non c'è nodo che non sia ancora stato attraversato. Quindi la traversata finisce.

Viene visitato l'albero completo

Quindi l'ordine di attraversamento dei nodi è 1 -> 2 -> 4 -> 5 -> 3 -> 6 .

Programma per implementare l'attraversamento del preordine dell'albero binario

Di seguito è riportata l'implementazione del codice dell'attraversamento del preordine:

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->dati < < ' ';  // Recur on left subtree  printPreorder(node->Sinistra);  // Ricorre sul sottoalbero destro printPreorder(node->right); } // Codice driver int main() { struct Node* root = new Node(1);  radice->sinistra = nuovo nodo(2);  radice->destra = nuovo nodo(3);  radice->sinistra->sinistra = nuovo nodo(4);  root->sinistra->destra = nuovo nodo(5);  radice->destra->destra = nuovo Nodo(6);  // Chiamata di funzione cout < < 'Preorder traversal of binary tree is: 
';  printPreorder(root);  return 0; }

Giava

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

Produzione

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

Spiegazione:

Come funziona l'attraversamento del preordine

Analisi della complessità:

Complessità temporale: O(N) dove N è il numero totale di nodi. Perché attraversa tutti i nodi almeno una volta.
Spazio ausiliario:

O(1) se non viene considerato lo spazio dello stack di ricorsione.
Altrimenti, OH) dove h è l'altezza dell'albero
Nel peggiore dei casi, H può essere lo stesso di N (quando l'albero è un albero inclinato)
Nel migliore dei casi, H può essere lo stesso di calma (quando l'albero è un albero completo)

Casi d'uso di Preorder Traversal:

Alcuni casi d'uso dell'attraversamento del preordine sono:

Questo viene spesso utilizzato per creare una copia di un albero.
È anche utile ottenere l'espressione del prefisso da un albero delle espressioni.

Articoli Correlati:

Tipi di attraversamento degli alberi
Attraversamento iterativo del preordine
Controlla se l'array fornito può rappresentare l'attraversamento del preordine di BST
Preordine da attraversamenti inordine e postordine
Trova l'ennesimo nodo nell'attraversamento in preordine di un albero binario
Attraversamento in preordine di un albero N-ario