V tomto článku se budeme zabývat předobjednávkou v datové struktuře. Lineární datové struktury, jako je zásobník, pole, fronta atd., mají pouze jeden způsob, jak data procházet. Ale v hierarchické datové struktuře jako je např strom , existuje několik způsobů, jak data procházet.
Při procházení předobjednávkou se nejprve navštíví kořenový uzel, poté levý podstrom a poté se navštíví pravý podstrom. Proces předobjednávky lze znázornit jako -
root → left → right
Kořenový uzel je vždy procházen jako první v předobjednávkovém procházení, zatímco je poslední položkou postorderového procházení. Preorder traversal se používá k získání prefixového výrazu stromu.
Kroky k provedení přechodu předobjednávky jsou uvedeny následovně -
- Nejprve navštivte kořenový uzel.
- Poté navštivte levý podstrom.
- Nakonec navštivte správný podstrom.
Technika předobjednávkového průchodu následuje Kořen vlevo vpravo politika. Samotný název předobjednávka naznačuje, že kořenový uzel bude procházet jako první.
Algoritmus
Nyní se podívejme na algoritmus procházení předobjedná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
Příklad procházení předobjednávky
Nyní se podívejme na příklad předobjednávkového průchodu. Na příkladu bude snazší pochopit proces procházení předobjednávky.
Uzly se žlutou barvou zatím nejsou navštěvovány. Nyní budeme procházet uzly výše uvedeného stromu pomocí předobjednávkového procházení.
- Začněte s kořenovým uzlem 40. Nejprve tisknout 40 a poté rekurzivně procházet levým podstromem.
- Nyní přejděte do levého podstromu. Pro levý podstrom je kořenový uzel 30. Tisk 30 a přejděte k levému podstromu 30.
- V levém podstromu 30 je prvek 25, takže tisknout 25 a projděte levý podstrom 25.
- V levém podstromu 25 je prvek 15 a 15 nemá žádný podstrom. Tak, tisknout 15 a přejděte do pravého podstromu 25.
- V pravém podstromu 25 je 28 a 28 nemá žádný podstrom. Tak, tisknout 28 a přejděte do pravého podstromu 30.
- V pravém podstromu 30 je 35, které nemá žádný podstrom. Tak tisknout 35 a projděte pravý podstrom 40.
- V pravém podstromu 40 je 50. Tisk 50 a projděte levý podstrom 50.
- V levém podstromu 50 je 45, které nemají žádné dítě. Tak, tisk 45 a projděte pravý podstrom 50.
- V pravém podstromu 50 je 60. Tisk 60 a projděte levý podstrom 60.
- V levém podstromu 60 je 55, které nemají žádné potomky. Tak, tisk 55 a přesuňte se do pravého podstromu 60.
- V pravém podstromu 60 je 70, které nemají žádné dítě. Tak, tisk 70 a zastavit proces.
Po dokončení předobjednávkového průchodu je konečným výstupem -
40, 30, 25, 15, 28, 35, 50, 45, 60, 55, 70
Složitost předobjednávkového průchodu
Časová složitost předobjednávkového průchodu je Na) , kde 'n' je velikost binárního stromu.
Zatímco prostorová složitost předobjednávkového průchodu je O(1) , pokud neuvažujeme velikost zásobníku pro volání funkcí. Jinak je prostorová složitost předobjednávkového průchodu stejná Ach) , kde 'h' je výška stromu.
Implementace předobjednávkového průchodu
Nyní se podívejme na implementaci předobjednávkového průchodu v různých programovacích jazycích.
Program: Napište program pro implementaci předobjednávkového průchodu v jazyce 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ýstup
Po provedení výše uvedeného kódu bude výstupem -
Program: Napište program pro implementaci předobjednávkového průchodu 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ýstup
Po provedení výše uvedeného kódu bude výstupem -
Program: Napište program pro implementaci předobjednávkového průchodu v Javě.
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ýstup
topologie sítě
Po provedení výše uvedeného kódu bude výstupem -
Tak to je k článku vše. Doufám, že vám článek bude užitečný a informativní.