In questo articolo discuteremo dell'attraversamento del preordine nella struttura dei dati. Le strutture di dati lineari come stack, array, coda, ecc. hanno solo un modo per attraversare i dati. Ma in una struttura di dati gerarchica come albero , esistono diversi modi per esaminare i dati.
Nell'attraversamento in preordine, viene visitato prima il nodo radice, quindi il sottoalbero sinistro e successivamente il sottoalbero destro. Il processo di attraversamento del preordine può essere rappresentato come:
root → left → right
Il nodo radice viene sempre attraversato per primo nell'attraversamento in preordine, mentre è l'ultimo elemento dell'attraversamento in postordine. L'attraversamento del preordine viene utilizzato per ottenere l'espressione del prefisso di un albero.
I passaggi per eseguire l'attraversamento del preordine sono elencati di seguito:
- Innanzitutto, visita il nodo radice.
- Quindi, visita il sottoalbero di sinistra.
- Alla fine, visita il sottoalbero destro.
La tecnica di attraversamento del preordine segue la Radice sinistra destra politica. Il nome preordine stesso suggerisce che il nodo radice verrebbe attraversato per primo.
Algoritmo
Vediamo ora l'algoritmo di attraversamento del preordine.
Step 1: Repeat Steps 2 to 4 while TREE != NULL Step 2: Write TREE -> DATA Step 3: PREORDER(TREE -> LEFT) Step 4: PREORDER(TREE -> RIGHT) [END OF LOOP] Step 5: END
Esempio di attraversamento del preordine
Vediamo ora un esempio di attraversamento del preordine. Sarà più semplice comprendere il processo di attraversamento del preordine utilizzando un esempio.
I nodi di colore giallo non sono ancora visitati. Ora attraverseremo i nodi dell'albero precedente utilizzando l'attraversamento del preordine.
- Inizia con il nodo radice 40. Innanzitutto, stampa 40 e quindi attraversare ricorsivamente il sottoalbero sinistro.
- Ora spostati nel sottoalbero di sinistra. Per il sottoalbero sinistro, il nodo radice è 30. Stampa 30 e spostati verso il sottoalbero sinistro di 30.
- Nel sottoalbero sinistro di 30 c'è un elemento 25, quindi stampa 25 e attraversa il sottoalbero sinistro di 25.
- Nel sottoalbero sinistro di 25 c'è un elemento 15 e 15 non ha un sottoalbero. COSÌ, stampa 15 e spostati al sottoalbero destro di 25.
- Nel sottoalbero destro di 25 c'è 28 e 28 non ha sottoalbero. COSÌ, stampa 28 e spostati al sottoalbero destro di 30.
- Nel sottoalbero destro di 30, ce n'è 35 che non ha sottoalbero. COSÌ stampa 35 e attraversare il sottoalbero destro di 40.
- Nel sottoalbero destro di 40 ce n'è 50. Stampa 50 e attraversa il sottoalbero sinistro di 50.
- Nel sottoalbero sinistro di 50, ce ne sono 45 che non hanno figli. COSÌ, stampa 45 e attraversare il sottoalbero destro di 50.
- Nel sottoalbero destro di 50 ce n'è 60. Stampa 60 e attraversare il sottoalbero sinistro di 60.
- Nel sottoalbero sinistro di 60, ce n'è 55 che non ha figli. COSÌ, stampa 55 e spostati al sottoalbero destro di 60.
- Nel sottoalbero destro di 60, ce ne sono 70 che non hanno figli. COSÌ, stampa 70 e interrompere il processo.
Dopo il completamento dell'attraversamento del preordine, l'output finale è:
40, 30, 25, 15, 28, 35, 50, 45, 60, 55, 70
Complessità dell'attraversamento del preordine
La complessità temporale dell'attraversamento del preordine è SU) , dove 'n' è la dimensione dell'albero binario.
Mentre la complessità spaziale dell'attraversamento del preordine lo è O(1) , se non consideriamo la dimensione dello stack per le chiamate di funzione. Altrimenti, la complessità spaziale dell'attraversamento del preordine lo è OH) , dove 'h' è l'altezza dell'albero.
Implementazione dell'attraversamento del preordine
Ora vediamo l'implementazione del preorder traversal in diversi linguaggi di programmazione.
Programma: Scrivere un programma per implementare l'attraversamento del preordine in linguaggio C.
#include #include struct node { int element; struct node* left; struct node* right; }; /*To create a new node*/ struct node* createNode(int val) { struct node* Node = (struct node*)malloc(sizeof(struct node)); Node->element = val; Node->left = NULL; Node->right = NULL; return (Node); } /*function to traverse the nodes of binary tree in preorder*/ void traversePreorder(struct node* root) { if (root == NULL) return; printf(' %d ', root->element); traversePreorder(root->left); traversePreorder(root->right); } int main() { struct node* root = createNode(40); root->left = createNode(30); root->right = createNode(50); root->left->left = createNode(25); root->left->right = createNode(35); root->left->left->left = createNode(15); root->left->left->right = createNode(28); root->right->left = createNode(45); root->right->right = createNode(60); root->right->right->left = createNode(55); root->right->right->right = createNode(70); printf('
The Preorder traversal of given binary tree is -
'); traversePreorder(root); return 0; } Produzione
Dopo l'esecuzione del codice sopra, l'output sarà:
Programma: Scrivere un programma per implementare l'attraversamento del preordine in C++.
#include using namespace std; struct node { int element; struct node* left; struct node* right; }; /*To create a new node*/ struct node* createNode(int val) { struct node* Node = (struct node*)malloc(sizeof(struct node)); Node->element = val; Node->left = NULL; Node->right = NULL; return (Node); } /*function to traverse the nodes of binary tree in preorder*/ void traversePreorder(struct node* root) { if (root == NULL) return; cout<<' '<element<left); traversepreorder(root->right); } int main() { struct node* root = createNode(39); root->left = createNode(29); root->right = createNode(49); root->left->left = createNode(24); root->left->right = createNode(34); root->left->left->left = createNode(14); root->left->left->right = createNode(27); root->right->left = createNode(44); root->right->right = createNode(59); root->right->right->left = createNode(54); root->right->right->right = createNode(69); cout<<'
the preorder traversal of given binary tree is -
'; traversepreorder(root); return 0; } < pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/25/preorder-traversal-14.webp" alt="Preorder Traversal"> <p> <strong>Program:</strong> Write a program to implement preorder traversal in C#.</p> <pre> using System; class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class BinaryTree { Node root; BinaryTree() { root = null; } void traversePreorder(Node node) { if (node == null) return; Console.Write(node.value + ' '); traversePreorder(node.left); traversePreorder(node.right); } void traversePreorder() { traversePreorder(root); } static void Main() { BinaryTree bt = new BinaryTree(); bt.root = new Node(38); bt.root.left = new Node(28); bt.root.right = new Node(48); bt.root.left.left = new Node(23); bt.root.left.right = new Node(33); bt.root.left.left.left = new Node(13); bt.root.left.left.right = new Node(26); bt.root.right.left = new Node(43); bt.root.right.right = new Node(58); bt.root.right.right.left = new Node(53); bt.root.right.right.right = new Node(68); Console.WriteLine('Preorder traversal of given binary tree is - '); bt.traversePreorder(); } } </pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/25/preorder-traversal-15.webp" alt="Preorder Traversal"> <p> <strong>Program:</strong> Write a program to implement preorder traversal in Java.</p> <pre> class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class PreorderTraversal { Node root; PreorderTraversal() { root = null; } void traversePreorder(Node node) { if (node == null) return; System.out.print(node.value + ' '); traversePreorder(node.left); traversePreorder(node.right); } void traversePreorder() { traversePreorder(root); } public static void main(String args[]) { PreorderTraversal pt = new PreorderTraversal(); pt.root = new Node(37); pt.root.left = new Node(27); pt.root.right = new Node(47); pt.root.left.left = new Node(22); pt.root.left.right = new Node(32); pt.root.left.left.left = new Node(12); pt.root.left.left.right = new Node(25); pt.root.right.left = new Node(42); pt.root.right.right = new Node(57); pt.root.right.right.left = new Node(52); pt.root.right.right.right = new Node(67); System.out.println(); System.out.println('Preorder traversal of given binary tree is - '); pt.traversePreorder(); System.out.println(); } } </pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/25/preorder-traversal-16.webp" alt="Preorder Traversal"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></'
></'> Produzione
Dopo l'esecuzione del codice sopra, l'output sarà:
Programma: Scrivere un programma per implementare l'attraversamento del preordine in Java.
class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class PreorderTraversal { Node root; PreorderTraversal() { root = null; } void traversePreorder(Node node) { if (node == null) return; System.out.print(node.value + ' '); traversePreorder(node.left); traversePreorder(node.right); } void traversePreorder() { traversePreorder(root); } public static void main(String args[]) { PreorderTraversal pt = new PreorderTraversal(); pt.root = new Node(37); pt.root.left = new Node(27); pt.root.right = new Node(47); pt.root.left.left = new Node(22); pt.root.left.right = new Node(32); pt.root.left.left.left = new Node(12); pt.root.left.left.right = new Node(25); pt.root.right.left = new Node(42); pt.root.right.right = new Node(57); pt.root.right.right.left = new Node(52); pt.root.right.right.right = new Node(67); System.out.println(); System.out.println('Preorder traversal of given binary tree is - '); pt.traversePreorder(); System.out.println(); } } Produzione
Dopo l'esecuzione del codice sopra, l'output sarà:
Quindi, questo è tutto sull'articolo. Spero che l'articolo ti sia utile e informativo.