Šiame straipsnyje aptarsime išankstinio užsakymo perėjimą duomenų struktūroje. Linijinės duomenų struktūros, tokios kaip dėklas, masyvas, eilė ir t. t., turi tik vieną būdą perduoti duomenis. Tačiau hierarchinėje duomenų struktūroje, pvz medis , yra keli būdai, kaip peržiūrėti duomenis.
Išankstinio užsakymo metu pirmiausia aplankomas šakninis mazgas, tada kairysis pomedis, o po to – dešinysis pomedis. Išankstinio užsakymo judėjimo procesas gali būti pavaizduotas kaip -
root → left → right
Šakninis mazgas visada kertamas pirmas atliekant išankstinio užsakymo eigą, o tai yra paskutinis postorder perėjimo elementas. Išankstinis užsakymas naudojamas norint gauti medžio priešdėlio išraišką.
Išankstinio užsakymo judėjimo veiksmai yra išvardyti taip:
- Pirmiausia apsilankykite šakniniame mazge.
- Tada apsilankykite kairiajame pomedyje.
- Galiausiai apsilankykite dešiniajame pomedyje.
Išankstinio užsakymo perėjimo technika yra tokia Šaknis Kairė Dešinė politika. Pats pavadinimas išankstinis užsakymas rodo, kad šakninis mazgas būtų pereitas pirmiausia.
Algoritmas
Dabar pažiūrėkime išankstinio užsakymo judėjimo algoritmą.
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
Išankstinio užsakymo perėjimo pavyzdys
Dabar pažiūrėkime apie išankstinio užsakymo pavyzdį. Naudojant pavyzdį, bus lengviau suprasti išankstinio užsakymo judėjimo procesą.
Geltonos spalvos mazgai dar nelankyti. Dabar pereisime per aukščiau pateikto medžio mazgus naudodami išankstinio užsakymo perėjimą.
- Pradėkite nuo šakninio mazgo 40. Pirma, spausdinti 40 ir tada rekursyviai pereiti kairįjį pomedį.
- Dabar pereikite prie kairiojo pomedžio. Kairiojo pomedžio šakninis mazgas yra 30. Spausdinti 30 ir pereikite link kairiojo 30 pomedžio.
- Kairiajame 30 pomedyje yra elementas 25, taigi spausdinti 25 , ir pereikite per kairįjį 25 pomedį.
- Kairiajame 25 pomedyje yra elementas 15, o 15 pomedžio nėra. Taigi, spausdinti 15 ir pereikite į dešinįjį 25 pomedį.
- Dešiniajame 25 pomedyje yra 28, o 28 pomedžio nėra. Taigi, spausdinti 28 ir pereikite į dešinįjį 30 pomedį.
- Dešiniajame 30 pomedžio yra 35, kuriame nėra pomedžio. Taigi spausdinti 35 ir pereikite dešinįjį 40 pomedį.
- Dešiniajame 40 pomedyje yra 50. Spausdinti 50 , ir pereikite per kairįjį 50 pomedį.
- Kairiajame 50 pomedyje yra 45, kurie neturi vaikų. Taigi, Spausdinti 45 , ir pereikite dešinįjį 50 pomedį.
- Dešiniajame 50 pomedyje yra 60. Spausdinti 60 ir pereikite per kairįjį 60 pomedį.
- Kairiajame 60 pomedyje yra 55, kurie neturi vaikų. Taigi, spausdinti 55 ir pereikite į dešinįjį 60 pomedį.
- Dešiniajame 60 pomedžio yra 70, kurie neturi vaikų. Taigi, spausdinti 70 ir sustabdyti procesą.
Užbaigus išankstinio užsakymo judėjimą, galutinis rezultatas yra -
40, 30, 25, 15, 28, 35, 50, 45, 60, 55, 70
Išankstinio užsakymo perėjimo sudėtingumas
Išankstinio užsakymo kelionės sudėtingumas yra toks O(n) , kur „n“ yra dvejetainio medžio dydis.
Tuo tarpu išankstinio užsakymo judėjimo sudėtingumas yra toks O(1) , jei neatsižvelgsime į funkcijų iškvietimų krūvos dydį. Priešingu atveju išankstinio užsakymo skrydžio erdvė yra sudėtinga Oi) , kur „h“ yra medžio aukštis.
Išankstinio užsakymo perėjimo įgyvendinimas
Dabar pažiūrėkime, kaip vykdomas išankstinis užsakymas skirtingomis programavimo kalbomis.
Programa: Parašykite programą, kuri įgyvendintų išankstinio užsakymo perėjimą C kalba.
#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; } Išvestis
Įvykdžius aukščiau pateiktą kodą, išvestis bus -
Programa: Parašykite programą, kuri įgyvendintų išankstinio užsakymo perėjimą 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></'
></'> Išvestis
formato java eilutė
Įvykdžius aukščiau pateiktą kodą, išvestis bus -
Programa: Parašykite programą, kuri įdiegtų išankstinio užsakymo perėjimą 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(); } } Išvestis
Įvykdžius aukščiau pateiktą kodą, išvestis bus -
Taigi, viskas apie straipsnį. Tikimės, kad straipsnis bus jums naudingas ir informatyvus.