V tem članku bomo razpravljali o prehodu prednaročila v strukturi podatkov. Linearne podatkovne strukture, kot so sklad, niz, čakalna vrsta itd., imajo samo en način za prečkanje podatkov. Toda v hierarhični strukturi podatkov, kot je npr drevo , obstaja več načinov za pregledovanje podatkov.
Pri prehodu pred naročilom se najprej obišče korensko vozlišče, nato levo poddrevo in za tem desno poddrevo. Proces prečkanja prednaročila lahko predstavimo kot -
root → left → right
Korensko vozlišče je vedno prvo prečkano pri prehodu pred naročilom, medtem ko je zadnji element pri prehodu po naročilu. Prehod pred naročilom se uporablja za pridobitev predponskega izraza drevesa.
Koraki za izvedbo prečkanja prednaročila so navedeni na naslednji način -
chiranjeevi igralec
- Najprej obiščite korensko vozlišče.
- Nato obiščite levo poddrevo.
- Končno obiščite desno poddrevo.
Tehnika prečkanja prednaročila sledi Korenina levo desno politika. Samo prednaročilo imena nakazuje, da bo najprej prečkano korensko vozlišče.
Algoritem
Zdaj pa si oglejmo algoritem prečkanja prednaročila.
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
Primer prečkanja prednaročila
Zdaj pa si oglejmo primer prečkanja prednaročila. Na primeru bomo lažje razumeli postopek prečkanja prednaročila.
Vozlišča z rumeno barvo še niso obiskana. Zdaj bomo prečkali vozlišča zgornjega drevesa s prehodom pred naročilom.
- Začnite s korenskim vozliščem 40. Najprej, natisni 40 in nato rekurzivno prečka levo poddrevo.
- Zdaj se premaknite na levo poddrevo. Za levo poddrevo je korensko vozlišče 30. Natisni 30 in se premaknite proti levemu poddrevesu 30.
- V levem poddrevesu 30 je element 25, torej natisni 25 , in prečkajte levo poddrevo 25.
- V levem poddrevesu 25 je element 15, 15 pa nima poddrevesa. Torej, natisni 15 in se premaknite na desno poddrevo 25.
- V desnem poddrevesu 25 je 28, 28 pa nima poddrevesa. Torej, natisni 28 in se pomaknite na desno poddrevo 30.
- V desnem poddrevesu od 30 je 35, ki nima poddrevesa. torej natisni 35 , in prečkajte desno poddrevo 40.
- V desnem poddrevesu 40 je 50. Natisni 50 , in prečkajte levo poddrevo 50.
- V levem poddrevesu 50 je 45, ki nimajo nobenega otroka. Torej, natisni 45 , in prečkajte desno poddrevo 50.
- V desnem poddrevesu 50 je 60. Natisni 60 in prečkajte levo poddrevo 60.
- V levem poddrevesu 60 je 55, ki nima nobenega otroka. Torej, natisni 55 in se pomaknite na desno poddrevo 60.
- V desnem poddrevesu 60 je 70, ki nimajo nobenega otroka. Torej, natisni 70 in ustavite postopek.
Po zaključku prečkanja prednaročila je končni rezultat -
40, 30, 25, 15, 28, 35, 50, 45, 60, 55, 70
primerljiv seznam
Kompleksnost prečkanja prednaročila
Časovna zapletenost prečkanja prednaročila je O(n) , kjer je 'n' velikost binarnega drevesa.
Medtem ko je prostorska kompleksnost prečkanja prednaročila O(1) , če ne upoštevamo velikosti sklada za klice funkcij. V nasprotnem primeru je prostorska zapletenost prečkanja prednaročila O(h) , kjer je 'h' višina drevesa.
Implementacija prečkanja prednaročila
Zdaj pa si oglejmo implementacijo prečkanja prednaročila v različnih programskih jezikih.
Program: Napišite program za izvajanje prehoda pred naročilom v jeziku C.
java spanje
#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; } Izhod
Po izvedbi zgornje kode bo rezultat -
Program: Napišite program za izvajanje prečkanja prednaročila v 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></'
></'> Izhod
Po izvedbi zgornje kode bo rezultat -
Program: Napišite program za izvajanje prehoda pred naročilom v Javi.
sql klavzule
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(); } } Izhod
Po izvedbi zgornje kode bo rezultat -
Torej, to je vse o članku. Upam, da vam bo članek koristen in informativen.