В тази статия ще обсъдим обхождането на предварителната поръчка в структурата на данните. Линейните структури от данни като стек, масив, опашка и т.н. имат само един начин за преминаване през данните. Но в йерархична структура от данни като напр дърво , има множество начини за преминаване на данните.
При обхождане с предварителна поръчка първо се посещава основният възел, след това лявото поддърво и след това се посещава дясното поддърво. Процесът на обхождане на предварителна поръчка може да бъде представен като -
root → left → right
Основният възел винаги се преминава първи при обхождане от предварителна поръчка, докато е последният елемент при обхождане след подреждане. Обхождането с предварителна поръчка се използва за получаване на префиксния израз на дърво.
Стъпките за извършване на обхождането на предварителната поръчка са изброени както следва -
- Първо посетете основния възел.
- След това посетете лявото поддърво.
- Най-накрая посетете дясното поддърво.
Техниката за преминаване на предварителна поръчка следва Корен наляво надясно политика. Самата предварителна поръчка на името предполага, че основният възел ще бъде преминат първи.
Алгоритъм
Сега нека да видим алгоритъма за обхождане на предварителна поръчка.
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
Пример за обхождане на предварителна поръчка
Сега нека видим пример за обхождане на предварителна поръчка. Ще бъде по-лесно да разберете процеса на обхождане на предварителна поръчка, като използвате пример.
Възлите с жълт цвят все още не са посетени. Сега ще преминем през възлите на горното дърво, като използваме обхождане с предварителна поръчка.
- Започнете с коренния възел 40. Първо, печат 40 и след това рекурсивно преминава през лявото поддърво.
- Сега преминете към лявото поддърво. За лявото поддърво коренният възел е 30. Печат 30 и се придвижете към лявото поддърво на 30.
- В лявото поддърво на 30 има елемент 25, така че печат 25 и пресечете лявото поддърво на 25.
- В лявото поддърво на 25 има елемент 15, а 15 няма поддърво. Така, печат 15 и се преместете в дясното поддърво на 25.
- В дясното поддърво на 25 има 28, а 28 няма поддърво. Така, печат 28 и се преместете в дясното поддърво на 30.
- В дясното поддърво на 30 има 35, което няма поддърво. Така печат 35 и пресечете дясното поддърво на 40.
- В дясното поддърво на 40 има 50. Печат 50 и пресечете лявото поддърво на 50.
- В лявото поддърво на 50 има 45, които нямат деца. Така, печат 45 и пресечете дясното поддърво на 50.
- В дясното поддърво на 50 има 60. Печат 60 и пресечете лявото поддърво на 60.
- В лявото поддърво на 60 има 55, което няма дете. Така, печат 55 и се преместете в дясното поддърво на 60.
- В дясното поддърво на 60 има 70, които нямат деца. Така, печат 70 и спрете процеса.
След завършване на обхождането на предварителната поръчка крайният изход е -
40, 30, 25, 15, 28, 35, 50, 45, 60, 55, 70
Сложност на преминаването на предварителната поръчка
Времевата сложност на обхождането на предварителната поръчка е На) , където 'n' е размерът на двоичното дърво.
Докато пространствената сложност на обхождането на предварителната поръчка е О(1) , ако не вземем предвид размера на стека за извиквания на функции. В противен случай пространствената сложност на обхождането на предварителната поръчка е O(h) , където 'h' е височината на дървото.
Внедряване на обхождане на предварителна поръчка
Сега, нека видим изпълнението на обхождане на предварителна поръчка в различни езици за програмиране.
програма: Напишете програма за прилагане на обхождане на предварителна поръчка на език 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; } Изход
След изпълнението на горния код, изходът ще бъде -
програма: Напишете програма за прилагане на обхождане на предварителна поръчка в 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></'
></'> Изход
След изпълнението на горния код, изходът ще бъде -
програма: Напишете програма за прилагане на обхождане на предварителна поръчка в 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(); } } Изход
След изпълнението на горния код, изходът ще бъде -
И така, това е всичко за статията. Надяваме се, че статията ще ви бъде полезна и информативна.