במאמר זה, נדון במעבר לאחר סדר במבנה הנתונים.
למבני נתונים ליניאריים כגון מחסנית, מערך, תור וכו', יש רק דרך אחת לעבור את הנתונים. אבל במבנה נתונים היררכי כגון עֵץ , ישנן מספר דרכים לעבור את הנתונים. אז, כאן נדון בדרך אחרת לחצות את מבנה נתוני העץ, כלומר, מעבר הזמנה בדואר . המעבר לאחר סדר הוא אחת מטכניקות המעבר המשמשות לביקור בצומת בעץ. זה הולך לפי העיקרון LRN (צומת שמאל-ימין) . חציית Postorder משמשת כדי לקבל את ביטוי postfix של עץ.
השלבים הבאים משמשים לביצוע המעבר לאחר ההזמנה:
- חצו את תת-העץ השמאלי על ידי קריאה רקורסיבית לפונקציית postorder.
- חצו את תת-העץ הימני על ידי קריאה רקורסיבית לפונקציית postorder.
- גש לחלק הנתונים של הצומת הנוכחי.
טכניקת המעבר לאחר הזמנה עוקבת אחר שורש שמאל ימין מְדִינִיוּת. כאן, שורש שמאלי ימני אומר שתת-העץ השמאלי של צומת השורש עובר תחילה, לאחר מכן תת-העץ הימני, ולבסוף, צומת השורש נחצה. כאן, השם Postorder עצמו מצביע על כך שצומת השורש של העץ יעבור סוף סוף.
מעבר הזמנה
אַלגוֹרִיתְם
כעת, בוא נראה את האלגוריתם של מעבר לפי סדר.
Step 1: Repeat Steps 2 to 4 while TREE != NULL Step 2: POSTORDER(TREE -> LEFT) Step 3: POSTORDER(TREE -> RIGHT) Step 4: Write TREE -> DATA [END OF LOOP] Step 5: END
דוגמה למעבר הזמנה בדואר
כעת, בוא נראה דוגמה למעבר לאחר הזמנה. יהיה קל יותר להבין את תהליך המעבר לאחר הזמנה באמצעות דוגמה.
הצמתים עם צבע צהוב עדיין לא ביקרו. כעת, נחצה את הצמתים של העץ שלמעלה תוך שימוש במעבר לאחר סדר.
- כאן, 40 הוא צומת השורש. אנו מבקרים תחילה בתת-עץ השמאלי של 40, כלומר, 30. צומת 30 גם יחצה בסדר פוסט. 25 הוא תת העץ השמאלי של 30, כך שהוא עובר גם בסדר פוסט. אז 15 הוא תת-העץ השמאלי של 25. אבל ל-15 אין תת-עץ, אז הדפס 15 ולנוע לעבר תת-העץ הימני של 25.
- 28 הוא תת-העץ הימני של 25, ואין לו ילדים. כך, הדפס 28 .
- עַכשָׁיו, הדפס 25 , והמעבר הפוסטר עבור 25 הסתיים.
- לאחר מכן, עברו לעבר תת-העץ הימני של 30. 35 הוא תת-העץ הימני של 30, ואין לו ילדים. כך, הדפס 35 .
- אחרי זה, הדפס 30 , והמעבר הפוסטר עבור 30 הסתיים. אז, תת-העץ השמאלי של העץ הבינארי הנתון נחצה.
- כעת, עברו לעבר תת-העץ הימני של 40 כלומר 50, והוא גם יחצה בסדר פוסט. 45 הוא תת העץ השמאלי של 50, ואין לו ילדים. כך, הדפס 45 ולנוע לעבר תת-העץ הימני של 50.
- 60 הוא תת-העץ הימני של 50, שגם אותו יעבור בסדר פוסט. 55 הוא תת העץ השמאלי של 60 שאין לו ילדים. כך, הדפס 55 .
- עַכשָׁיו, הדפס 70, שהוא תת העץ הימני של 60.
- עַכשָׁיו, הדפס 60, והמעבר לאחר הזמנה עבור 60 הושלם.
- עַכשָׁיו, הדפס 50, והמעבר לאחר הזמנה עבור 50 הושלם.
- לבסוף, הדפס 40, שהוא צומת השורש של העץ הבינארי הנתון, והמעבר לפי סדר עבור צומת 40 הושלם.
הפלט הסופי שנקבל לאחר מעבר הזמנה הוא -
חריתיק רושן
{15, 28, 25, 35, 30, 45, 55, 70, 60, 50, 40}
מורכבות של מעבר הזמנה בדואר
מורכבות הזמן של מעבר לאחר הזמנה היא עַל) , כאשר 'n' הוא הגודל של עץ בינארי.
ואילו, מורכבות החלל של מעבר לאחר הזמנה היא O(1) , אם לא ניקח בחשבון את גודל המחסנית עבור קריאות לפונקציות. אחרת, מורכבות החלל של מעבר לאחר הזמנה היא O(h) , כאשר 'h' הוא גובה העץ.
יישום העברת הזמנה בדואר
כעת, בואו נראה את היישום של מעבר הזמנה לאחר הזמנה בשפות תכנות שונות.
תכנית: כתוב תוכנית ליישום מעבר הזמנה בשפה C.
המרה ממחרוזת למספר שלם של java
#include #include struct node { s 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 postorder*/ void traversePostorder(struct node* root) { if (root == NULL) return; traversePostorder(root->left); traversePostorder(root->right); printf(' %d ', root->element); } 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 Postorder traversal of given binary tree is -
'); traversePostorder(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 postorder*/ void traversePostorder(struct node* root) { if (root == NULL) return; traversePostorder(root->left); traversePostorder(root->right); cout<<' '<element<left="createNode(28);" root->right = createNode(48); root->left->left = createNode(23); root->left->right = createNode(33); root->left->left->left = createNode(13); root->left->left->right = createNode(26); root->right->left = createNode(43); root->right->right = createNode(58); root->right->right->left = createNode(53); root->right->right->right = createNode(68); cout<<'
the postorder traversal of given binary tree is -
'; traversepostorder(root); return 0; } < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/85/postorder-traversal-14.webp" alt="Postorder Traversal"> <p> <strong>Program:</strong> Write a program to implement postorder 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 traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); Console.Write(node.value + ' '); } void traversePostorder() { traversePostorder(root); } static void Main() { BinaryTree bt = new BinaryTree(); bt.root = new Node(37); bt.root.left = new Node(27); bt.root.right = new Node(47); bt.root.left.left = new Node(22); bt.root.left.right = new Node(32); bt.root.left.left.left = new Node(12); bt.root.left.left.right = new Node(25); bt.root.right.left = new Node(42); bt.root.right.right = new Node(57); bt.root.right.right.left = new Node(52); bt.root.right.right.right = new Node(67); Console.WriteLine('The Postorder traversal of given binary tree is - '); bt.traversePostorder(); } } </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/85/postorder-traversal-15.webp" alt="Postorder Traversal"> <p> <strong>Program:</strong> Write a program to implement postorder traversal in Java.</p> <pre> class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class PostorderTraversal { Node root; PostorderTraversal() { root = null; } void traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); System.out.print(node.value + ' '); } void traversePostorder() { traversePostorder(root); } public static void main(String args[]) { PostorderTraversal pt = new PostorderTraversal(); pt.root = new Node(36); pt.root.left = new Node(26); pt.root.right = new Node(46); pt.root.left.left = new Node(21); pt.root.left.right = new Node(31); pt.root.left.left.left = new Node(11); pt.root.left.left.right = new Node(24); pt.root.right.left = new Node(41); pt.root.right.right = new Node(56); pt.root.right.right.left = new Node(51); pt.root.right.right.right = new Node(66); System.out.println(); System.out.println('The Postorder traversal of given binary tree is - '); pt.traversePostorder(); 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/85/postorder-traversal-16.webp" alt="Postorder Traversal"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></'
></'> תְפוּקָה
דגם tcp ו-ip
לאחר ביצוע הקוד לעיל, הפלט יהיה -
תכנית: כתוב תוכנית ליישום מעבר הזמנה ב-Java.
class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class PostorderTraversal { Node root; PostorderTraversal() { root = null; } void traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); System.out.print(node.value + ' '); } void traversePostorder() { traversePostorder(root); } public static void main(String args[]) { PostorderTraversal pt = new PostorderTraversal(); pt.root = new Node(36); pt.root.left = new Node(26); pt.root.right = new Node(46); pt.root.left.left = new Node(21); pt.root.left.right = new Node(31); pt.root.left.left.left = new Node(11); pt.root.left.left.right = new Node(24); pt.root.right.left = new Node(41); pt.root.right.right = new Node(56); pt.root.right.right.left = new Node(51); pt.root.right.right.right = new Node(66); System.out.println(); System.out.println('The Postorder traversal of given binary tree is - '); pt.traversePostorder(); System.out.println(); } } תְפוּקָה
לאחר ביצוע הקוד לעיל, הפלט יהיה -
אז, זה הכל לגבי המאמר. מקווה שהמאמר יהיה מועיל ואינפורמטיבי עבורך.