في هذه المقالة، سنناقش اجتياز الطلب اللاحق في بنية البيانات.
هياكل البيانات الخطية مثل المكدس والمصفوفة وقائمة الانتظار وما إلى ذلك، لها طريقة واحدة فقط لاجتياز البيانات. ولكن في بنية البيانات الهرمية مثل شجرة ، هناك طرق متعددة لاجتياز البيانات. لذا، سنناقش هنا طريقة أخرى لاجتياز بنية بيانات الشجرة، أي: اجتياز أمر البريد . يعد اجتياز ما بعد الطلب أحد تقنيات الاجتياز المستخدمة لزيارة العقدة في الشجرة. إنه يتبع المبدأ LRN (عقدة اليسار واليمين) . يتم استخدام اجتياز ما بعد الطلب للحصول على تعبير postfix للشجرة.
: في جافا
يتم استخدام الخطوات التالية لتنفيذ اجتياز الطلب اللاحق:
- اجتياز الشجرة الفرعية اليسرى عن طريق استدعاء وظيفة الطلب اللاحق بشكل متكرر.
- اجتياز الشجرة الفرعية الصحيحة عن طريق استدعاء وظيفة الطلب اللاحق بشكل متكرر.
- الوصول إلى جزء البيانات من العقدة الحالية.
تتبع تقنية اجتياز الطلب اللاحق الجذر الأيمن الأيسر سياسة. هنا، يعني الجذر الأيمن الأيسر أنه تم اجتياز الشجرة الفرعية اليسرى للعقدة الجذرية أولاً، ثم الشجرة الفرعية اليمنى، وأخيرًا، تم اجتياز العقدة الجذرية. هنا، يشير اسم 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' هو حجم الشجرة الثنائية.
حيث أن التعقيد المكاني لاجتياز ما بعد الطلب هو يا(1) ، إذا لم نأخذ في الاعتبار حجم المكدس لاستدعاءات الوظائف. خلاف ذلك، فإن التعقيد المكاني لاجتياز ما بعد الطلب هو أوه) ، حيث 'h' هو ارتفاع الشجرة.
تنفيذ اجتياز الطلب عبر البريد
الآن، دعونا نرى تنفيذ اجتياز ما بعد الطلب في لغات البرمجة المختلفة.
برنامج: اكتب برنامجًا لتنفيذ اجتياز ما بعد الطلب بلغة C.
#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></'
></'> انتاج |
بعد تنفيذ الكود أعلاه سيكون الناتج -
برنامج: اكتب برنامجًا لتنفيذ اجتياز ما بعد الطلب في 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(); } } انتاج |
بعد تنفيذ الكود أعلاه سيكون الناتج -
لذلك، هذا كل ما في هذه المادة. نأمل أن تكون المقالة مفيدة وغنية بالمعلومات لك.