U ovom ćemo članku raspravljati o obilasku prednarudžbe u strukturi podataka. Linearne podatkovne strukture kao što su stog, niz, red čekanja itd. imaju samo jedan način za prolazak kroz podatke. Ali u hijerarhijskoj strukturi podataka kao što je drvo , postoji više načina za prelazak podataka.
U prethodnom obilasku prvo se posjećuje korijenski čvor, zatim lijevo podstablo i nakon toga desno podstablo. Proces prolaska prednarudžbe može se predstaviti kao -
root → left → right
Korijenski čvor se uvijek prvi obilazi u prethodnom obilasku, dok je posljednja stavka u postorderu obilasku. Prolaz prednarudžbe koristi se za dobivanje prefiksnog izraza stabla.
Koraci za izvođenje prolaska prednarudžbe navedeni su kako slijedi -
višenitnost u Javi
- Najprije posjetite korijenski čvor.
- Zatim posjetite lijevo podstablo.
- Na kraju, posjetite desno podstablo.
Tehnika obilaska prednarudžbe slijedi Korijen lijevo desno politika. Sam naziv prednarudžbe sugerira da će se prvo obići korijenski čvor.
Algoritam
Pogledajmo sada algoritam prolaska prednarudžbe.
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
Primjer obilaska prednarudžbe
Sada, da vidimo primjer obilaska prednarudžbe. Na primjeru će biti lakše razumjeti proces prolaska prednarudžbi.
Čvorovi sa žutom bojom još nisu posjećeni. Sada ćemo preći čvorove gornjeg stabla korištenjem obilaska unaprijed.
- Počnite s korijenskim čvorom 40. Prvo, ispis 40 a zatim rekurzivno prelazi lijevo podstablo.
- Sada prijeđite na lijevo podstablo. Za lijevo podstablo, korijenski čvor je 30. Ispis 30 , i pomaknite se prema lijevom podstablu od 30.
- U lijevom podstablu od 30 nalazi se element 25, dakle ispis 25 , i pređite lijevo podstablo od 25.
- U lijevom podstablu od 25 nalazi se element 15, a 15 nema podstablo. Tako, ispis 15 , i pomaknite se na desno podstablo od 25.
- U desnom podstablu od 25 nalazi se 28, a 28 nema podstablo. Tako, ispis 28 , i pomaknite se na desno podstablo od 30.
- U desnom podstablu od 30 nalazi se 35 koje nema podstablo. Tako ispis 35 , i prelazi desno podstablo od 40.
- U desnom podstablu od 40 nalazi se 50. Ispis 50 , i prijeći lijevo podstablo od 50.
- U lijevom podstablu od 50 nalazi se 45 koji nemaju dijete. Tako, ispis 45 , i prelazi desno podstablo od 50.
- U desnom podstablu od 50 nalazi se 60. Ispis 60 i pređite lijevo podstablo od 60.
- U lijevom podstablu od 60 nalazi se 55 koje nema dijete. Tako, ispis 55 i pomaknite se na desno podstablo od 60.
- U desnom podstablu od 60 nalazi se 70 koji nemaju dijete. Tako, ispis 70 i zaustaviti proces.
Nakon završetka prolaska prednarudžbe, konačni izlaz je -
40, 30, 25, 15, 28, 35, 50, 45, 60, 55, 70
mysql prikaži sve korisnike
Složenost prolaska prednarudžbe
Vremenska složenost prolaska prednarudžbe je Na) , gdje je 'n' veličina binarnog stabla.
Dok je prostorna složenost obilaska prednarudžbe O(1) , ako ne uzmemo u obzir veličinu stoga za pozive funkcija. U suprotnom, prostorna složenost obilaska prednarudžbe je Oh) , gdje je 'h' visina stabla.
Implementacija prelaska prednarudžbi
Pogledajmo sada implementaciju prolaska prednarudžbi u različitim programskim jezicima.
Program: Napišite program za implementaciju obilaska prednarudžbe u C jeziku.
testiranje performansi
#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; } Izlaz
Nakon izvršenja gornjeg koda, izlaz će biti -
Program: Napišite program za implementaciju obilaska prednarudžbi u 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></'
></'> Izlaz
Nakon izvršenja gornjeg koda, izlaz će biti -
Program: Napišite program za implementaciju obilaska prednarudžbi u Javi.
Glumac Rekha
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(); } } Izlaz
Nakon izvršenja gornjeg koda, izlaz će biti -
Dakle, to je sve o članku. Nadamo se da će vam članak biti koristan i informativan.