TechCodeview

في هذه المقالة، سنناقش الاجتياز الداخلي في بنية البيانات.

إذا أردنا اجتياز العقد بترتيب تصاعدي، فإننا نستخدم الاجتياز الداخلي. فيما يلي الخطوات المطلوبة للاجتياز الداخلي:

• قم بزيارة كافة العقد في الشجرة الفرعية اليسرى
• قم بزيارة العقدة الجذرية
• قم بزيارة كافة العقد في الشجرة الفرعية الصحيحة

هياكل البيانات الخطية مثل المكدس والمصفوفة وقائمة الانتظار وما إلى ذلك، لها طريقة واحدة فقط لاجتياز البيانات. ولكن في هياكل البيانات الهرمية مثل شجرة، هناك طرق متعددة لاجتياز البيانات. سنناقش هنا طريقة أخرى لاجتياز بنية بيانات الشجرة، أي الاجتياز الداخلي.

هناك طريقتان تستخدمان للاجتياز الداخلي:

مجموعات في جافا

• اجتياز Inorder باستخدام العودية
• اجتياز Inorder باستخدام الطريقة التكرارية

تتبع تقنية الاجتياز الداخلي الجذر الأيسر الأيمن سياسة. هنا، يعني الجذر الأيسر لليمين أنه يتم اجتياز الشجرة الفرعية اليسرى للعقدة الجذرية أولاً، ثم العقدة الجذرية، ثم يتم اجتياز الشجرة الفرعية اليمنى للعقدة الجذرية. هنا، يشير الاسم الداخلي نفسه إلى أن العقدة الجذرية تأتي بين الشجرتين الفرعيتين اليمنى واليسرى.

سنناقش الاجتياز الداخلي باستخدام كل من التقنيات العودية والتكرارية. لنبدأ أولاً بالاجتياز الداخلي باستخدام التكرار.

اجتياز Inorder باستخدام العودية

 Step 1: Recursively traverse the left subtree Step 2: Now, visit the root Step 3: Traverse the right subtree recursively 

مثال على اجتياز النظام الداخلي

الآن، دعونا نرى مثالاً على اجتياز النظام الداخلي. سيكون من الأسهل فهم إجراء الاجتياز الداخلي باستخدام مثال.

ص في ​​البرمجة ج

لم تتم زيارة العقد ذات اللون الأصفر بعد. الآن، سوف نجتاز عقد الشجرة أعلاه باستخدام الاجتياز الداخلي.

• هنا، 40 هي العقدة الجذرية. ننتقل إلى الشجرة الفرعية اليسرى 40، أي 30، ولها أيضًا الشجرة الفرعية 25، لذا ننتقل مرة أخرى إلى الشجرة الفرعية اليسرى 25، أي 15. هنا، 15 ليس له شجرة فرعية، لذا طباعة 15 والتحرك نحو العقدة الأم، 25.
  
• الآن، طباعة 25 والانتقال إلى الشجرة الفرعية اليمنى من 25.
  
• الآن، طباعة 28 وانتقل إلى العقدة الجذرية للرقم 25 وهي 30.
  
• لذلك، تمت زيارة الشجرة الفرعية اليسرى المكونة من 30. الآن، طباعة 30 والانتقال إلى الطفل المناسب البالغ من العمر 30 عامًا.
  
• الآن، طباعة 35 والانتقال إلى العقدة الجذرية 30.
  
• الآن، طباعة العقدة الجذرية 40 والانتقال إلى الشجرة الفرعية اليمنى.
  
• الآن قم باجتياز الشجرة الفرعية الصحيحة المكونة من 40 والتي تكون 50 بشكل متكرر.
  50 لها شجرة فرعية، لذا قم أولاً باجتياز الشجرة الفرعية اليسرى لـ 50 والتي هي 45. 45 ليس لها أطفال، لذا طباعة 45 والانتقال إلى عقدة الجذر الخاصة به.
  
• الآن طباعة 50 وانتقل إلى الشجرة الفرعية اليمنى المكونة من 50 والتي تبلغ 60.
  
• الآن، قم باجتياز الشجرة الفرعية اليمنى المكونة من 50 والتي تمثل 60 بشكل متكرر. 60 بها شجرة فرعية، لذا قم أولاً باجتياز الشجرة الفرعية اليسرى المكونة من 60 والتي تمثل 55. 55 ليس لها أبناء، لذا طباعة 55 والانتقال إلى عقدة الجذر الخاصة به.
  
• الآن طباعة 60 وانتقل إلى الشجرة الفرعية اليمنى المكونة من 60 والتي تبلغ 70.
  
• الآن طباعة 70.
  

بعد الانتهاء من اجتياز الترتيب الداخلي، يكون الإخراج النهائي هو -

{15، 25، 28، 30، 35، 40، 45، 50، 55، 60، 70}

تعقيد اجتياز Inorder

التعقيد الزمني لاجتياز Inorder هو على)، حيث 'n' هو حجم الشجرة الثنائية.

حيث أن التعقيد المكاني للاجتياز الداخلي هو يا (1)، إذا لم نأخذ في الاعتبار حجم المكدس لاستدعاءات الوظائف. خلاف ذلك، فإن التعقيد المكاني للاجتياز الداخلي هو أوه)، حيث 'h' هو ارتفاع الشجرة.

تنفيذ اجتياز Inorder

الآن، دعونا نرى تنفيذ اجتياز Inorder في لغات البرمجة المختلفة.

برنامج: اكتب برنامجًا لتنفيذ عملية الاجتياز الداخلي في لغة 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 Inorder*/ void traverseInorder(struct node* root) { if (root == NULL) return; traverseInorder(root->left); printf(' %d ', root->element); traverseInorder(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 Inorder traversal of given binary tree is -
'); traverseInorder(root); return 0; } 

انتاج |

افعل أثناء حلقة Java

برنامج: اكتب برنامجًا لتنفيذ عملية الاجتياز الداخلي في لغة 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-&gt;element = val; Node-&gt;left = NULL; Node-&gt;right = NULL; return (Node); } /*function to traverse the nodes of binary tree in Inorder*/ void traverseInorder(struct node* root) { if (root == NULL) return; traverseInorder(root-&gt;left); cout&lt;<' '<element<right); } int main() { struct node* root="createNode(39);" root->left = createNode(29); root-&gt;right = createNode(49); root-&gt;left-&gt;left = createNode(24); root-&gt;left-&gt;right = createNode(34); root-&gt;left-&gt;left-&gt;left = createNode(14); root-&gt;left-&gt;left-&gt;right = createNode(27); root-&gt;right-&gt;left = createNode(44); root-&gt;right-&gt;right = createNode(59); root-&gt;right-&gt;right-&gt;left = createNode(54); root-&gt;right-&gt;right-&gt;right = createNode(69); cout&lt;<'
 the inorder traversal of given binary tree is -
'; traverseinorder(root); return 0; } < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/15/inorder-traversal-14.webp" alt="Inorder Traversal"> <p> <strong>Program:</strong> Write a program to implement inorder 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 traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); Console.Write(node.value + &apos; &apos;); traverseInorder(node.right); } void traverseInorder() { traverseInorder(root); } static void Main() { BinaryTree bt = new BinaryTree(); bt.root = new Node(36); bt.root.left = new Node(26); bt.root.right = new Node(46); bt.root.left.left = new Node(21); bt.root.left.right = new Node(31); bt.root.left.left.left = new Node(11); bt.root.left.left.right = new Node(24); bt.root.right.left = new Node(41); bt.root.right.right = new Node(56); bt.root.right.right.left = new Node(51); bt.root.right.right.right = new Node(66); Console.WriteLine(&apos;The Inorder traversal of given binary tree is - &apos;); bt.traverseInorder(); } } </pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/15/inorder-traversal-15.webp" alt="Inorder Traversal"> <p> <strong>Program:</strong> Write a program to implement inorder traversal in Java.</p> <pre> class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class InorderTraversal { Node root; InorderTraversal() { root = null; } void traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); System.out.print(node.value + &apos; &apos;); traverseInorder(node.right); } void traverseInorder() { traverseInorder(root); } public static void main(String args[]) { InorderTraversal pt = new InorderTraversal(); pt.root = new Node(35); pt.root.left = new Node(25); pt.root.right = new Node(45); pt.root.left.left = new Node(20); pt.root.left.right = new Node(30); pt.root.left.left.left = new Node(10); pt.root.left.left.right = new Node(23); pt.root.right.left = new Node(40); pt.root.right.right = new Node(55); pt.root.right.right.left = new Node(50); pt.root.right.right.right = new Node(66); System.out.println(); System.out.println(&apos;The Inorder traversal of given binary tree is - &apos;); pt.traverseInorder(); System.out.println(); } } </pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/15/inorder-traversal-16.webp" alt="Inorder Traversal"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <hr></'
></'>

انتاج |

تحميل اوتوكاد 2019 انجليزي من ميديا ​​فاير

برنامج: اكتب برنامجًا لتنفيذ الاجتياز الداخلي في Java.

 class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class InorderTraversal { Node root; InorderTraversal() { root = null; } void traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); System.out.print(node.value + ' '); traverseInorder(node.right); } void traverseInorder() { traverseInorder(root); } public static void main(String args[]) { InorderTraversal pt = new InorderTraversal(); pt.root = new Node(35); pt.root.left = new Node(25); pt.root.right = new Node(45); pt.root.left.left = new Node(20); pt.root.left.right = new Node(30); pt.root.left.left.left = new Node(10); pt.root.left.left.right = new Node(23); pt.root.right.left = new Node(40); pt.root.right.right = new Node(55); pt.root.right.right.left = new Node(50); pt.root.right.right.right = new Node(66); System.out.println(); System.out.println('The Inorder traversal of given binary tree is - '); pt.traverseInorder(); System.out.println(); } } 

انتاج |

لذلك، هذا كل ما في هذه المادة. نأمل أن تكون المقالة مفيدة وغنية بالمعلومات لك.