במאמר זה, נדון במעבר לא-סדר במבנה הנתונים.

אם אנחנו רוצים לחצות את הצמתים בסדר עולה, אז אנחנו משתמשים במעבר לא-סדר. להלן השלבים הנדרשים למעבר הסדר:

• בקר בכל הצמתים בתת-עץ השמאלי
• בקר בצומת השורש
• בקר בכל הצמתים בתת-עץ הימני

למבני נתונים ליניאריים כגון מחסנית, מערך, תור וכו', יש רק דרך אחת לעבור את הנתונים. אבל במבני נתונים היררכיים כגון עֵץ, ישנן מספר דרכים לעבור את הנתונים. כאן נדון בדרך אחרת לחצות את מבנה נתוני העץ, כלומר, מעבר לא-סדר.

ישנן שתי גישות המשמשות למעבר לא-סדר:

• מעבר לא-סדר באמצעות רקורסיה
• מעבר לא-סדר באמצעות שיטה איטרטיבית

טכניקת מעבר לא-סדר עוקבת אחר שורש שמאל ימין מְדִינִיוּת. כאן, Left Root Right אומר שתת-העץ השמאלי של צומת השורש עובר תחילה, לאחר מכן צומת השורש, ולאחר מכן עוברים את תת-העץ הימני של צומת השורש. כאן, שם אין-סדר עצמו מרמז שצומת השורש נכנס בין תת-העץ השמאלי והימני.

נדון במעבר לא-סדר באמצעות טכניקות רקורסיביות ואיטרטיביות כאחד. נתחיל תחילה במעבר לא-סדר באמצעות רקורסיה.

מעבר לא-סדר באמצעות רקורסיה

 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' הוא גודל העץ הבינארי.

ואילו, מורכבות החלל של חציית סדר היא O(1), אם לא ניקח בחשבון את גודל המחסנית עבור קריאות לפונקציות. אחרת, מורכבות החלל של מעבר לא-סדר הוא O(h), כאשר 'h' הוא גובה העץ.

יישום חציית 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; } 

תְפוּקָה

תכנית: כתוב תוכנית ליישום מעבר סדר ב-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></'
></'>

תְפוּקָה

תכנית: כתוב תוכנית ליישום מעבר סדר ב-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(); } } 

תְפוּקָה

אז, זה הכל לגבי המאמר. מקווה שהמאמר יהיה מועיל ואינפורמטיבי עבורך.