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