Šajā rakstā mēs apspriedīsim priekšpasūtīšanas šķērsošanu datu struktūrā. Lineārām datu struktūrām, piemēram, kaudze, masīvs, rinda utt., ir tikai viens veids, kā šķērsot datus. Bet hierarhiskā datu struktūrā, piemēram, koks , ir vairāki veidi, kā pārvietot datus.
Veicot priekšpasūtīšanu, vispirms tiek apmeklēts saknes mezgls, tad kreisais apakškoks un pēc tam tiek apmeklēts labais apakškoks. Iepriekšpasūtīšanas šķērsošanas procesu var attēlot kā -
root → left → right
Saknes mezgls vienmēr tiek šķērsots pirmais, veicot priekšpasūtīšanas apceļošanu, savukārt tas ir pēdējais postorder šķērsošanas vienums. Priekšpasūtīšanas šķērsošana tiek izmantota, lai iegūtu koka prefiksa izteiksmi.
Darbības, lai veiktu priekšpasūtīšanas apceļošanu, ir norādītas šādi:
jdbc jdbc
- Vispirms apmeklējiet saknes mezglu.
- Pēc tam apmeklējiet kreiso apakškoku.
- Beidzot apmeklējiet labo apakškoku.
Iepriekšpasūtīšanas šķērsošanas tehnika seko Sakne pa kreisi pa labi politiku. Pats nosaukums priekšpasūtījums liecina, ka saknes mezgls tiktu šķērsots vispirms.
Algoritms
Tagad apskatīsim priekšpasūtīšanas šķērsošanas algoritmu.
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
Iepriekšpasūtīšanas šķērsošanas piemērs
Tagad apskatīsim priekšpasūtīšanas šķērsošanas piemēru. Izmantojot piemēru, būs vieglāk izprast priekšpasūtīšanas šķērsošanas procesu.
Mezgli ar dzeltenu krāsu vēl nav apmeklēti. Tagad mēs šķērsosim iepriekš minētā koka mezglus, izmantojot priekšpasūtīšanas šķērsošanu.
- Sāciet ar saknes mezglu 40. Pirmkārt, drukāt 40 un pēc tam rekursīvi šķērsojiet kreiso apakškoku.
- Tagad pārejiet uz kreiso apakškoku. Kreisajam apakškokam saknes mezgls ir 30. Drukāt 30 , un virzieties uz kreiso apakškoku 30.
- Kreisajā apakškokā 30 ir elements 25, tātad drukāt 25 , un šķērsojiet kreiso apakškoku 25.
- Kreisajā apakškokā 25 ir elements 15, un 15 nav apakškoka. Tātad, drukāt 15 , un pārejiet uz labo apakškoku 25.
- Labajā apakškokā 25 ir 28, un 28 nav apakškoka. Tātad, drukāt 28 , un pārejiet uz labo apakškoku 30.
- Labajā apakškokā 30 ir 35, kam nav apakškoka. Tātad drukāt 35 , un šķērsojiet labo apakškoku 40.
- Labajā apakškokā 40 ir 50. Drukāt 50 , un šķērsojiet 50 kreiso apakškoku.
- Kreisajā apakškokā 50 ir 45, kuriem nav neviena bērna. Tātad, drukāt 45 , un šķērsojiet labo apakškoku 50.
- Labajā apakškokā 50 ir 60. Drukāt 60 un šķērsojiet 60 kreiso apakškoku.
- Kreisajā apakškokā 60 ir 55, kam nav neviena bērna. Tātad, drukāt 55 un pārejiet uz 60 labo apakškoku.
- Labajā apakškokā 60 ir 70, kuriem nav neviena bērna. Tātad, drukāt 70 un pārtrauciet procesu.
Pēc priekšpasūtīšanas šķērsošanas pabeigšanas gala rezultāts ir -
40, 30, 25, 15, 28, 35, 50, 45, 60, 55, 70
java virkne satur
Iepriekšpasūtīšanas šķērsošanas sarežģītība
Priekšpasūtīšanas laika sarežģītība ir O(n) , kur “n” ir binārā koka izmērs.
Tā kā priekšpasūtīšanas šķērsošanas telpa ir sarežģīta O(1) , ja neņemam vērā funkciju izsaukumu steka lielumu. Pretējā gadījumā priekšpasūtīšanas šķērsošana ir sarežģīta O(h) , kur “h” ir koka augstums.
Iepriekšpasūtīšanas šķērsošanas ieviešana
Tagad apskatīsim priekšpasūtīšanas caurlaides ieviešanu dažādās programmēšanas valodās.
Programma: Uzrakstiet programmu, lai ieviestu priekšpasūtīšanas šķērsošanu C valodā.
python generē uuid
#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; } Izvade
Pēc iepriekš minētā koda izpildes izvade būs -
Programma: Uzrakstiet programmu, lai ieviestu priekšpasūtīšanas šķērsošanu programmā 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></'
></'> Izvade
Pēc iepriekš minētā koda izpildes izvade būs -
Programma: Uzrakstiet programmu, lai Java ieviestu priekšpasūtīšanas šķērsošanu.
pavasara mvc
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(); } } Izvade
Pēc iepriekš minētā koda izpildes izvade būs -
Tātad, tas viss par rakstu. Cerams, ka raksts jums būs noderīgs un informatīvs.