logo

TechCodeview

Inorder Traversal

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

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

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

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

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

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

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

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

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

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

דוגמה למעבר לא סדר

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

Inorder Traversal

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

  • כאן, 40 הוא צומת השורש. אנחנו עוברים לתת-העץ השמאלי של 40, כלומר 30, ויש לו גם תת-עץ 25, אז אנחנו שוב עוברים לתת-העץ השמאלי של 25 שהוא 15. כאן, ל-15 אין תת-עץ, אז הדפס 15 ולנוע לעבר צומת האב שלו, 25.
    Inorder Traversal
  • עַכשָׁיו, הדפס 25 ועבור לתת-עץ הימני של 25.
    Inorder Traversal
  • עַכשָׁיו, הדפס 28 ועבור לצומת השורש של 25 כלומר 30.
    Inorder Traversal
  • אז, תת-עץ שמאלי של 30 הוא ביקר. עַכשָׁיו, הדפס 30 ולעבור לילד הנכון בן 30.
    Inorder Traversal
  • עַכשָׁיו, הדפס 35 ועבור לצומת השורש של 30.
    Inorder Traversal
  • עַכשָׁיו, הדפס צומת שורש 40 ולעבור לעץ המשנה הימני שלו.
    Inorder Traversal
  • כעת חצו באופן רקורסיבי את תת-העץ הימני של 40 כלומר 50.
    ל-50 יש תת-עץ אז תעברו קודם את תת-העץ השמאלי של 50 כלומר 45. ל-45 אין ילדים, אז הדפס 45 ולעבור לצומת השורש שלו.
    Inorder Traversal
  • עַכשָׁיו הדפס 50 ועבור לתת-עץ הימני של 50 כלומר 60.
    Inorder Traversal
  • כעת חצו באופן רקורסיבי את תת-העץ הימני של 50 כלומר 60. ל-60 יש תת-עץ אז תעברו קודם את תת-העץ השמאלי של 60 שהוא 55. ל-55 אין ילדים, אז הדפס 55 ולעבור לצומת השורש שלו.
    Inorder Traversal
  • עַכשָׁיו הדפס 60 ועבור לתת-עץ הימני של 60 כלומר 70.
    Inorder Traversal
  • עַכשָׁיו הדפס 70.
    Inorder Traversal

לאחר השלמת מעבר לא-סדר, הפלט הסופי הוא -

{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; }

תְפוּקָה

Inorder Traversal

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

תְפוּקָה

Inorder Traversal

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

תְפוּקָה

Inorder Traversal

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