У овом чланку ћемо разговарати о преласку преднаруџбина у структури података. Линеарне структуре података као што су стек, низ, ред, итд., имају само један начин да прелазе податке. Али у хијерархијској структури података као што је дрво , постоји више начина да се пређу подаци.
У обиласку пре поруџбине, прво се посећује основни чвор, затим лево подстабло и након тога се посећује десно подстабло. Процес преласка наруџбине може се представити као -
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
нп.меан
Сложеност преласка у претпродају
Временска сложеност преласка наруџбине је На) , где је 'н' величина бинарног стабла.
Док је просторна сложеност преласка наруџбине О(1) , ако не узмемо у обзир величину стека за позиве функција. У супротном, просторна сложеност преласка наруџбине је О(х) , где је 'х' висина стабла.
Имплементација преласка преко налога
Сада, хајде да видимо имплементацију преласка наруџбине у различитим програмским језицима.
Програм: Напишите програм за имплементацију преласка наруџбине у Ц језику.
ред у односу на колону
#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; } Излаз
Након извршења горњег кода, излаз ће бити -
Програм: Напишите програм за имплементацију преласка наруџбине у Ц++.
#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></'
></'> Излаз
Након извршења горњег кода, излаз ће бити -
Програм: Напишите програм за имплементацију обиласка пре поруџбине у Јави.
величина мог монитора
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(); } } Излаз
Након извршења горњег кода, излаз ће бити -
Дакле, то је све о чланку. Надамо се да ће вам чланак бити користан и информативан.