V tomto článku budeme diskutovať o prechode predobjednávky v dátovej štruktúre. Lineárne dátové štruktúry, ako je zásobník, pole, front atď., majú iba jeden spôsob prechodu dát. Ale v hierarchickej dátovej štruktúre ako napr strom , existuje viacero spôsobov, ako prechádzať údajmi.
Pri prechode predobjednávkou sa najprv navštívi koreňový uzol, potom sa navštívi ľavý podstrom a potom sa navštívi pravý podstrom. Proces prechodu predobjednávky možno znázorniť ako -
root → left → right
Koreňový uzol sa vždy prechádza ako prvý pri prechode predobjednávkou, zatiaľ čo je poslednou položkou prechodu po postorderi. Prechod predobjednávky sa používa na získanie predponového výrazu stromu.
tlačidlo tkinter
Kroky na vykonanie prechodu predobjednávky sú uvedené nasledovne -
- Najprv navštívte koreňový uzol.
- Potom navštívte ľavý podstrom.
- Nakoniec navštívte správny podstrom.
Nasleduje technika prechodu predobjednávky Koreň zľava doprava politika. Samotný názov predobjednávka naznačuje, že koreňový uzol by sa mal prejsť ako prvý.
Algoritmus
Teraz sa pozrime na algoritmus prechodu predobjednávky.
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
Príklad prechodu predobjednávky
Teraz sa pozrime na príklad prechodu predobjednávky. Na príklade bude jednoduchšie pochopiť proces prechodu predobjednávky.
Uzly so žltou farbou zatiaľ nie sú navštevované. Teraz budeme prechádzať uzlami vyššie uvedeného stromu pomocou prechodu predobjednávky.
- Začnite s koreňovým uzlom 40. Najprv tlač 40 a potom rekurzívne prejsť ľavým podstromom.
- Teraz prejdite do ľavého podstromu. Pre ľavý podstrom je koreňový uzol 30. Vytlačiť 30 a prejdite k ľavému podstromu 30.
- V ľavom podstrome 30 je prvok 25, tzv vytlačiť 25 a prejdite ľavým podstromom 25.
- V ľavom podstrome 25 je prvok 15 a 15 nemá žiadny podstrom. takže, vytlačiť 15 a prejdite do pravého podstromu 25.
- V pravom podstrome 25 je 28 a 28 nemá žiadny podstrom. takže, vytlačiť 28 a prejdite do pravého podstromu 30.
- V pravom podstrome 30 je 35, ktoré nemá žiadny podstrom. Takže vytlačiť 35 a prejdite pravým podstromom 40.
- V pravom podstrome 40 je 50. Vytlačiť 50 a prejdite ľavým podstromom 50.
- V ľavom podstrome 50 je 45, ktoré nemajú žiadne dieťa. takže, tlač 45 a prejdite pravým podstromom 50.
- V pravom podstrome 50 je 60. Tlač 60 a prejdite ľavým podstromom 60.
- V ľavom podstrome 60 je 55, ktoré nemajú žiadne dieťa. takže, vytlačiť 55 a presuňte sa do pravého podstromu 60.
- V pravom podstrome 60 je 70, ktoré nemajú žiadne dieťa. takže, tlač 70 a zastaviť proces.
Po dokončení prechodu predobjednávky je konečný výstup -
40, 30, 25, 15, 28, 35, 50, 45, 60, 55, 70
Zložitosť prechodu predobjednávky
Časová zložitosť prechodu predobjednávky je O(n) , kde 'n' je veľkosť binárneho stromu.
Zatiaľ čo priestorová zložitosť prechodu predobjednávky je O(1) , ak neberieme do úvahy veľkosť zásobníka pre volania funkcií. V opačnom prípade je priestorová zložitosť prechodu predobjednávky O(h) , kde 'h' je výška stromu.
Implementácia Preorder traversal
Teraz sa pozrime na implementáciu prechodu predobjednávky v rôznych programovacích jazykoch.
Program: Napíšte program na implementáciu prechodu predobjednávky v jazyku 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; } Výkon
Po vykonaní vyššie uvedeného kódu bude výstupom -
Program: Napíšte program na implementáciu prechodu predobjednávky 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></'
></'> Výkon
Po vykonaní vyššie uvedeného kódu bude výstupom -
Program: Napíšte program na implementáciu prechodu predobjednávky v jazyku 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(); } } Výkon
spracovanie výnimiek v jazyku Java
Po vykonaní vyššie uvedeného kódu bude výstupom -
Tak, to je o článku všetko. Dúfam, že článok bude pre vás užitočný a poučný.