În acest articol, vom discuta traversarea precomenzilor în structura datelor. Structurile liniare de date, cum ar fi stiva, matricea, coada etc., au o singură modalitate de a parcurge datele. Dar într-o structură de date ierarhică precum copac , există mai multe moduri de a parcurge datele.
În parcurgerea precomenzii, mai întâi, este vizitat nodul rădăcină, apoi sub-arborele din stânga și după aceea este vizitat sub-arborele din dreapta. Procesul de parcurgere a precomenzii poate fi reprezentat ca -
siruri de sortare java
root → left → right
Nodul rădăcină este întotdeauna parcurs primul în traversarea precomandă, în timp ce este ultimul element al traversării postcomandă. Parcurgerea precomanda este folosită pentru a obține expresia prefixului unui arbore.
Pașii pentru a efectua traversarea precomenzii sunt listați după cum urmează -
- Mai întâi, vizitați nodul rădăcină.
- Apoi, vizitați subarborele din stânga.
- În cele din urmă, vizitați subarborele potrivit.
Tehnica de traversare a precomenzii urmează Rădăcină Stânga Dreapta politică. Precomanda numelui în sine sugerează că nodul rădăcină ar fi traversat primul.
Algoritm
Acum, să vedem algoritmul traversării precomenzilor.
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
Exemplu de traversare a precomenzii
Acum, să vedem un exemplu de traversare a precomenzii. Va fi mai ușor de înțeles procesul de parcurgere a precomenzii folosind un exemplu.
Nodurile cu culoare galbenă nu sunt încă vizitate. Acum, vom traversa nodurile arborelui de mai sus folosind traversarea precomandă.
- Începeți cu nodul rădăcină 40. Mai întâi, imprimare 40 și apoi traversați recursiv subarborele din stânga.
- Acum, treceți la subarborele din stânga. Pentru subarborele din stânga, nodul rădăcină este 30. Tipăriți 30 , și deplasați-vă către subarborele din stânga al lui 30.
- În subarborele din stânga 30, există un element 25, deci imprimare 25 , și traversați subarborele din stânga al lui 25.
- În subarborele din stânga 25, există un element 15, iar 15 nu are subarborele. Asa de, imprimare 15 , și deplasați-vă la subarborele din dreapta al lui 25.
- În subarborele din dreapta al lui 25, există 28, iar 28 nu are subarborele. Asa de, imprimare 28 , și deplasați-vă la subarborele din dreapta al lui 30.
- În subarborele din dreapta al lui 30, există 35 care nu are subarborele. Asa de imprimare 35 , și traversați subarborele din dreapta al lui 40.
- În subarborele din dreapta al lui 40, există 50. Tipăriți 50 , și traversați subarborele din stânga al lui 50.
- În subarborele din stânga al lui 50, există 45 care nu au niciun copil. Asa de, imprimare 45 , și traversați subarborele din dreapta al lui 50.
- În subarborele din dreapta cu 50, există 60. Tipăriți 60 și traversați subarborele din stânga lui 60.
- În subarborele din stânga al lui 60, există 55 care nu are niciun copil. Asa de, tipăriți 55 și treceți la subarborele din dreapta cu 60.
- În subarborele din dreapta al lui 60, există 70 care nu au niciun copil. Asa de, imprimare 70 și opriți procesul.
După finalizarea traversării precomenzii, rezultatul final este -
40, 30, 25, 15, 28, 35, 50, 45, 60, 55, 70
Complexitatea traversării precomenzilor
Complexitatea temporală a traversării precomenzilor este Pe) , unde „n” este dimensiunea arborelui binar.
Întrucât, complexitatea spațială a traversării precomenzilor este O(1) , dacă nu luăm în considerare dimensiunea stivei pentru apelurile de funcții. În caz contrar, complexitatea spațială a traversării precomenzii este Oh) , unde „h” este înălțimea copacului.
Implementarea traversării precomenzilor
Acum, să vedem implementarea traversării precomenzilor în diferite limbaje de programare.
Program: Scrieți un program pentru a implementa traversarea precomenzii în limbaj 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; } Ieșire
După executarea codului de mai sus, rezultatul va fi -
Program: Scrieți un program pentru a implementa traversarea precomenzii în C++.
cum se convertesc șirul în int java
#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></'
></'> Ieșire
După executarea codului de mai sus, rezultatul va fi -
Program: Scrieți un program pentru a implementa traversarea precomenzilor în 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(); } } Ieșire
După executarea codului de mai sus, rezultatul va fi -
Deci, asta e totul despre articol. Sper că articolul vă va fi util și informativ.