In questo articolo discuteremo dell'attraversamento dell'albero nella struttura dati. Il termine 'attraversamento dell'albero' significa attraversare o visitare ciascun nodo di un albero. Esiste un unico modo per attraversare la struttura lineare dei dati come elenco collegato, coda e stack. Considerando che esistono diversi modi per attraversare un albero elencati come segue:
- Attraversamento del preordine
- Attraversamento in ordine
- Viaggio del vaglia postale
Quindi, in questo articolo discuteremo delle tecniche sopra elencate per attraversare un albero. Ora iniziamo a discutere le modalità di attraversamento degli alberi.
Attraversamento del preordine
Questa tecnica segue la politica della 'radice sinistra destra'. Ciò significa che il primo nodo radice viene visitato, dopo che il sottoalbero sinistro viene attraversato ricorsivamente e, infine, il sottoalbero destro viene attraversato ricorsivamente. Poiché il nodo radice viene attraversato prima (o prima) dei sottoalberi sinistro e destro, si parla di attraversamento del preordine.
Quindi, in un attraversamento in preordine, ciascun nodo viene visitato prima di entrambi i suoi sottoalberi.
Le applicazioni dell'attraversamento del preordine includono:
- Viene utilizzato per creare una copia dell'albero.
- Può anche essere utilizzato per ottenere l'espressione del prefisso di un albero delle espressioni.
Algoritmo
Until all nodes of the tree are not visited Step 1 - Visit the root node Step 2 - Traverse the left subtree recursively. Step 3 - Traverse the right subtree recursively.
Esempio
Vediamo ora l'esempio della tecnica di attraversamento del preordine.
Ora inizia ad applicare l'attraversamento del preordine sull'albero sopra. Innanzitutto, attraversiamo il nodo radice UN; dopodiché, spostati al sottoalbero sinistro B , che verrà percorso anch'esso in preordine.
Quindi, per il sottoalbero sinistro B, innanzitutto il nodo radice B è attraversato stesso; dopodiché, è il sottoalbero sinistro D è attraversato. Dal nodo D non ha figli, spostati nel sottoalbero destro E . Poiché anche il nodo E non ha figli, l'attraversamento del sottoalbero sinistro del nodo radice A è completato.
mondo wumpus
Ora spostati verso il sottoalbero destro del nodo radice A che è C. Quindi, per il sottoalbero destro C, prima il nodo radice C ha attraversato se stesso; dopodiché, è il sottoalbero sinistro F è attraversato. Dal nodo F non ha figli, spostati nel sottoalbero destro G . Poiché anche il nodo G non ha figli, l'attraversamento del sottoalbero destro del nodo radice A è completato.
Pertanto tutti i nodi dell'albero vengono attraversati. Quindi, l'output dell'attraversamento del preordine dell'albero sopra è:
La → Si → Re → Mi → Do → Fa → Sol
Per saperne di più sull'attraversamento del preordine nella struttura dei dati, puoi seguire il collegamento Attraversamento del preordine .
Viaggio del vaglia postale
Questa tecnica segue la politica della 'radice sinistra-destra'. Ciò significa che viene attraversato il primo sottoalbero sinistro del nodo radice, successivamente attraversa ricorsivamente il sottoalbero destro e infine viene attraversato il nodo radice. Poiché il nodo radice viene attraversato dopo (o dopo) i sottoalberi sinistro e destro, viene chiamato attraversamento postordine.
Quindi, in un attraversamento postordine, ciascun nodo viene visitato dopo entrambi i suoi sottoalberi.
Le applicazioni dell'attraversamento postorder includono:
Java pubblico o privato
- Viene utilizzato per eliminare l'albero.
- Può anche essere utilizzato per ottenere l'espressione suffissa di un albero delle espressioni.
Algoritmo
Until all nodes of the tree are not visited Step 1 - Traverse the left subtree recursively. Step 2 - Traverse the right subtree recursively. Step 3 - Visit the root node.
Esempio
Vediamo ora l'esempio della tecnica di attraversamento postorder.
Ora inizia ad applicare l'attraversamento postorder sull'albero sopra. Innanzitutto, attraversiamo il sottoalbero sinistro B che verrà attraversato in postordine. Successivamente, attraverseremo il sottoalbero destro C in postordine. E infine, il nodo radice dell'albero sopra, cioè UN , è attraversato.
Quindi, per il sottoalbero sinistro B, innanzitutto il suo sottoalbero sinistro D è attraversato. Dal nodo D non ha figli, attraversare il sottoalbero destro E . Poiché anche il nodo E non ha figli, spostati sul nodo radice B. Dopo aver attraversato il nodo B, l'attraversamento del sottoalbero sinistro del nodo radice A è completato.
Ora spostati verso il sottoalbero destro del nodo radice A che è C. Quindi, per il sottoalbero destro C, prima il suo sottoalbero sinistro F è attraversato. Dal nodo F non ha figli, attraversare il sottoalbero destro G . Poiché anche il nodo G non ha figli, quindi, infine, il nodo radice del sottoalbero destro, cioè, C, è attraversato. L'attraversamento del sottoalbero destro del nodo radice A è completato.
Infine, attraversa il nodo radice di un dato albero, ovvero UN . Dopo aver attraversato il nodo radice, l'attraversamento postordine dell'albero dato è completato.
Pertanto tutti i nodi dell'albero vengono attraversati. Quindi, l'output dell'attraversamento postorder dell'albero sopra è:
RE → MI → SI → FA → SOL → DO → LA
Per saperne di più sull'attraversamento del postorder nella struttura dei dati, puoi seguire il collegamento Viaggio del vaglia postale .
Attraversamento in ordine
Questa tecnica segue la politica della 'radice sinistra destra'. Ciò significa che il primo sottoalbero di sinistra viene visitato dopo che è stato attraversato il nodo radice e, infine, viene attraversato il sottoalbero di destra. Quando il nodo radice viene attraversato tra il sottoalbero sinistro e quello destro, viene denominato attraversamento in ordine.
mysql crea utente
Quindi, nell'attraversamento in ordine, ogni nodo viene visitato tra i suoi sottoalberi.
Le applicazioni dell'attraversamento in ordine includono:
- Viene utilizzato per ottenere i nodi BST in ordine crescente.
- Può anche essere utilizzato per ottenere l'espressione del prefisso di un albero delle espressioni.
Algoritmo
Until all nodes of the tree are not visited Step 1 - Traverse the left subtree recursively. Step 2 - Visit the root node. Step 3 - Traverse the right subtree recursively.
Esempio
Vediamo ora l'esempio della tecnica di attraversamento Inorder.
Ora inizia ad applicare l'attraversamento in ordine sull'albero sopra. Innanzitutto, attraversiamo il sottoalbero sinistro B che verranno percorse in ordine. Successivamente, attraverseremo il nodo radice UN . E infine, il sottoalbero destro C viene percorso in ordine.
Quindi, per il sottoalbero sinistro B , in primo luogo, il suo sottoalbero sinistro D è attraversato. Dal nodo D non ha figli, quindi dopo averlo attraversato, node B verrà attraversato e, infine, il sottoalbero destro del nodo B E , è attraversato. Anche il nodo E non ha figli; pertanto, l'attraversamento del sottoalbero sinistro del nodo radice A è completato.
Successivamente, attraversa il nodo radice di un dato albero, ovvero UN .
Infine, spostati verso il sottoalbero destro del nodo radice A che è C. Quindi, per il sottoalbero destro C; innanzitutto, il suo sottoalbero sinistro F è attraversato. Dal nodo F non ha figli, node C verrà attraversato e, infine, un sottoalbero destro del nodo C, cioè G , è attraversato. Anche il nodo G non ha figli; pertanto, l'attraversamento del sottoalbero destro del nodo radice A è completato.
attore saira banu
Quando tutti i nodi dell'albero vengono attraversati, l'attraversamento in ordine dell'albero dato è completato. L'output dell'attraversamento in ordine dell'albero sopra è:
RE → SI → MI → LA → FA → DO → SOL
Per saperne di più sull'attraversamento in ordine nella struttura dei dati, puoi seguire il collegamento Attraversamento in ordine .
Complessità delle tecniche di attraversamento degli alberi
La complessità temporale delle tecniche di attraversamento degli alberi discusse sopra è SU) , Dove 'N' è la dimensione dell'albero binario.
Mentre la complessità spaziale delle tecniche di attraversamento degli alberi discusse sopra lo è O(1) se non consideriamo la dimensione dello stack per le chiamate di funzione. Altrimenti, la complessità spaziale di queste tecniche lo è OH) , Dove 'H' è l'altezza dell'albero.
Implementazione dell'attraversamento degli alberi
Vediamo ora l'implementazione delle tecniche sopra discusse utilizzando diversi linguaggi di programmazione.
Programma: Scrivere un programma per implementare tecniche di attraversamento degli alberi in 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); } /*function to traverse the nodes of binary tree in Inorder*/ void traverseInorder(struct node* root) { if (root == NULL) return; traverseInorder(root->left); printf(' %d ', root->element); traverseInorder(root->right); } /*function to traverse the nodes of binary tree in postorder*/ void traversePostorder(struct node* root) { if (root == NULL) return; traversePostorder(root->left); traversePostorder(root->right); printf(' %d ', root->element); } int main() { struct node* root = createNode(36); root->left = createNode(26); root->right = createNode(46); root->left->left = createNode(21); root->left->right = createNode(31); root->left->left->left = createNode(11); root->left->left->right = createNode(24); root->right->left = createNode(41); root->right->right = createNode(56); root->right->right->left = createNode(51); root->right->right->right = createNode(66); printf('
The Preorder traversal of given binary tree is -
'); traversePreorder(root); printf('
The Inorder traversal of given binary tree is -
'); traverseInorder(root); printf('
The Postorder traversal of given binary tree is -
'); traversePostorder(root); return 0; } Produzione
Programma: Scrivere un programma per implementare tecniche di attraversamento degli alberi in C#.
arp: un comando
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 traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); Console.Write(node.value + ' '); traverseInorder(node.right); } void traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); Console.Write(node.value + ' '); } void traversePreorder() { traversePreorder(root); } void traverseInorder() { traverseInorder(root); } void traversePostorder() { traversePostorder(root); } static void Main() { BinaryTree bt = new BinaryTree(); bt.root = new Node(37); bt.root.left = new Node(27); bt.root.right = new Node(47); bt.root.left.left = new Node(22); bt.root.left.right = new Node(32); bt.root.left.left.left = new Node(12); bt.root.left.left.right = new Node(25); bt.root.right.left = new Node(42); bt.root.right.right = new Node(57); bt.root.right.right.left = new Node(52); bt.root.right.right.right = new Node(67); Console.WriteLine('The Preorder traversal of given binary tree is - '); bt.traversePreorder(); Console.WriteLine(); Console.WriteLine('The Inorder traversal of given binary tree is - '); bt.traverseInorder(); Console.WriteLine(); Console.WriteLine('The Postorder traversal of given binary tree is - '); bt.traversePostorder(); } } Produzione
Programma: Scrivere un programma per implementare tecniche di attraversamento degli alberi 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); } /*function to traverse the nodes of binary tree in Inorder*/ void traverseInorder(struct node* root) { if (root == NULL) return; traverseInorder(root->left); cout<<' '<element<right); } *function to traverse the nodes of binary tree in postorder* void traversepostorder(struct node* root) { if (root="=" null) return; traversepostorder(root->left); traversePostorder(root->right); cout<<' '<element<left="createNode(28);" root->right = createNode(48); root->left->left = createNode(23); root->left->right = createNode(33); root->left->left->left = createNode(13); root->left->left->right = createNode(26); root->right->left = createNode(43); root->right->right = createNode(58); root->right->right->left = createNode(53); root->right->right->right = createNode(68); cout<<'
the preorder traversal of given binary tree is -
'; traversepreorder(root); cout<<'
inorder traverseinorder(root); postorder traversepostorder(root); return 0; } < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/17/tree-traversal-inorder-6.webp" alt="Tree Traversal"> <p> <strong>Program:</strong> Write a program to implement tree traversal techniques in Java.</p> <pre> class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class Tree { Node root; /* root of the tree */ Tree() { root = null; } /*function to print the nodes of given binary in Preorder*/ void traversePreorder(Node node) { if (node == null) return; System.out.print(node.value + ' '); traversePreorder(node.left); traversePreorder(node.right); } /*function to print the nodes of given binary in Inorder*/ void traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); System.out.print(node.value + ' '); traverseInorder(node.right); } /*function to print the nodes of given binary in Postorder*/ void traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); System.out.print(node.value + ' '); } void traversePreorder() { traversePreorder(root); } void traverseInorder() { traverseInorder(root); } void traversePostorder() { traversePostorder(root); } public static void main(String args[]) { Tree pt = new Tree(); pt.root = new Node(36); pt.root.left = new Node(26); pt.root.right = new Node(46); pt.root.left.left = new Node(21); pt.root.left.right = new Node(31); pt.root.left.left.left = new Node(11); pt.root.left.left.right = new Node(24); pt.root.right.left = new Node(41); pt.root.right.right = new Node(56); pt.root.right.right.left = new Node(51); pt.root.right.right.right = new Node(66); System.out.println(); System.out.println('The Preorder traversal of given binary tree is - '); pt.traversePreorder(); System.out.println('
'); System.out.println('The Inorder traversal of given binary tree is - '); pt.traverseInorder(); System.out.println('
'); System.out.println('The Postorder traversal of given binary tree is - '); pt.traversePostorder(); 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/17/tree-traversal-inorder-7.webp" alt="Tree Traversal"> <h2>Conclusion</h2> <p>In this article, we have discussed the different types of tree traversal techniques: preorder traversal, inorder traversal, and postorder traversal. We have seen these techniques along with algorithm, example, complexity, and implementation in C, C++, C#, and java.</p> <p>So, that's all about the article. Hope it will be helpful and informative to you.</p> <hr></'
></'></'></'> Produzione
Dopo l'esecuzione del codice sopra, l'output sarà:
Conclusione
In questo articolo abbiamo discusso i diversi tipi di tecniche di attraversamento degli alberi: attraversamento in preordine, attraversamento in ordine e attraversamento in postordine. Abbiamo visto queste tecniche insieme all'algoritmo, all'esempio, alla complessità e all'implementazione in C, C++, C# e Java.
Quindi, questo è tutto sull'articolo. Spero che ti sarà utile e informativo.