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

• מעבר בהזמנה מראש
• מעבר לא-סדר
• העברת הזמנה בדואר

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

מעבר בהזמנה מראש

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

אז, במעבר הזמנה מראש, כל צומת מבקר לפני שני תתי העצים שלו.

היישומים של מעבר הזמנה מראש כוללים -

• הוא משמש ליצירת עותק של העץ.
• ניתן להשתמש בו גם כדי לקבל את ביטוי הקידומת של עץ ביטוי.

אַלגוֹרִיתְם

 Until all nodes of the tree are not visited Step 1 - Visit the root node Step 2 - Traverse the left subtree recursively. Step 3 - Traverse the right subtree recursively. 

דוגמא

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

כעת, התחל להחיל את המעבר להזמנה מראש על העץ שלמעלה. ראשית, אנו חוצים את צומת השורש א; לאחר מכן, עבור אל תת העץ השמאלי שלו ב , שגם יעברו בהזמנה מראש.

אז, עבור תת-עץ B השמאלי, ראשית, צומת השורש ב חוצה את עצמו; לאחר מכן, תת העץ השמאלי שלו ד נחצה. מאז הצומת ד אין לו ילדים, עבור לעץ המשנה הימני ו . מכיוון שגם לצומת E אין ילדים, המעבר של תת-העץ השמאלי של צומת שורש A הושלם.

הסרת ה-commit האחרון git

כעת, עברו לכיוון תת-העץ הימני של צומת השורש A כלומר C. לכן, עבור תת-העץ הימני C, ראשית צומת השורש ג חצתה את עצמה; לאחר מכן, תת העץ השמאלי שלו ו נחצה. מאז הצומת ו אין לו ילדים, עבור לעץ המשנה הימני G . מכיוון שגם לצומת G אין ילדים, המעבר של תת-העץ הימני של צומת השורש A הושלם.

לכן, כל צמתים של העץ עוברים. אז הפלט של מעבר ההזמנה מראש של העץ לעיל הוא -

A → B → D → E → C → F → G

Java indexof

כדי לדעת יותר על מעבר הזמנה מראש במבנה הנתונים, תוכל לעקוב אחר הקישור מעבר בהזמנה מראש .

העברת הזמנה בדואר

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

אז, במעבר פוסט-order, כל צומת מבקר אחרי שני תתי העצים שלו.

היישומים של מעבר הזמנה כוללים -

• הוא משמש למחיקת העץ.
• זה יכול לשמש גם כדי לקבל את הביטוי postfix של עץ ביטוי.

אַלגוֹרִיתְם

 Until all nodes of the tree are not visited Step 1 - Traverse the left subtree recursively. Step 2 - Traverse the right subtree recursively. Step 3 - Visit the root node. 

דוגמא

כעת, בואו נראה את הדוגמה של טכניקת המעבר לאחר הזמנה.

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

אז, עבור תת-עץ B השמאלי, ראשית, תת-העץ השמאלי שלו ד נחצה. מאז הצומת ד אין לו ילדים, חצו את תת-העץ הימני ו . מכיוון שגם לצומת E אין ילדים, עברו לצומת השורש ב. לאחר חציית צומת ב, המעבר של תת-העץ השמאלי של צומת שורש A הושלם.

כעת, עברו לעבר תת-העץ הימני של צומת השורש A שהוא C. לכן, עבור תת-עץ הימני C, ראשית תת-העץ השמאלי שלו ו נחצה. מאז הצומת ו אין לו ילדים, חצו את תת-העץ הימני G . מכיוון שגם לצומת G אין ילדים, לכן, לבסוף, צומת השורש של תת-העץ הימני, כלומר, ג, נחצה. המעבר של תת-העץ הימני של צומת שורש A הושלם.

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

לכן, כל צמתים של העץ עוברים. אז הפלט של המעבר שלאחר הסדר של העץ לעיל הוא -

D → E → B → F → G → C → A

כדי לדעת יותר על העברת ההזמנה במבנה הנתונים, תוכל לעקוב אחר הקישור העברת הזמנה בדואר .

מעבר לא-סדר

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

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

היישומים של מעבר Inorder כוללים -

מחרוזת ב-char java

• הוא משמש כדי לקבל את צמתי BST בסדר הולך וגדל.
• ניתן להשתמש בו גם כדי לקבל את ביטוי הקידומת של עץ ביטוי.

אַלגוֹרִיתְם

 Until all nodes of the tree are not visited Step 1 - Traverse the left subtree recursively. Step 2 - Visit the root node. Step 3 - Traverse the right subtree recursively. 

דוגמא

כעת, בואו נראה את הדוגמה של טכניקת המעבר של Inorder.

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

אז, עבור תת-עץ שמאלי ב , ראשית, תת העץ השמאלי שלו ד נחצה. מאז הצומת ד אין לו ילדים, אז אחרי שחוצים אותו, צומת ב יעבור, ולבסוף תת-עץ ימני של צומת B, כלומר ו , עוברים. גם לצומת E אין ילדים; לכן, המעבר של תת-העץ השמאלי של צומת שורש A הושלם.

לאחר מכן, חצו את צומת השורש של עץ נתון, כלומר, א .

לבסוף, זז לעבר תת-העץ הימני של צומת השורש A שהוא C. אז, עבור תת-העץ הימני C; ראשית, תת העץ השמאלי שלו ו נחצה. מאז הצומת ו אין לו ילדים, צומת ג יעבור, ולבסוף תת-עץ ימני של צומת C, כלומר, G , עוברים. גם לצומת G אין ילדים; לכן, המעבר של תת-העץ הימני של צומת שורש A הושלם.

כאשר כל הצמתים של העץ עוברים, המעבר הלא-סדר של העץ הנתון הושלם. הפלט של מעבר לא-סדר של העץ לעיל הוא -

D → B → E → A → F → C → G

ריפוד np

כדי לדעת יותר על מעבר לא-סדר במבנה הנתונים, אתה יכול לעקוב אחר הקישור Inorder Traversal .

מורכבות של טכניקות חציית עצים

מורכבות הזמן של טכניקות חציית עצים שנדונו לעיל היא עַל) , איפה 'נ' הוא בגודל של עץ בינארי.

ואילו מורכבות החלל של טכניקות חציית עצים שנדונו לעיל היא O(1) אם לא ניקח בחשבון את גודל המחסנית עבור קריאות לפונקציות. אחרת, מורכבות החלל של טכניקות אלה היא O(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); } /*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); } /*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(36); root->left = createNode(26); root->right = createNode(46); root->left->left = createNode(21); root->left->right = createNode(31); root->left->left->left = createNode(11); root->left->left->right = createNode(24); root->right->left = createNode(41); root->right->right = createNode(56); root->right->right->left = createNode(51); root->right->right->right = createNode(66); printf('
 The Preorder traversal of given binary tree is -
'); traversePreorder(root); printf('
 The Inorder traversal of given binary tree is -
'); traverseInorder(root); printf('
 The Postorder traversal of given binary tree is -
'); traversePostorder(root); return 0; } 

תְפוּקָה

תכנית: כתוב תוכנית ליישום טכניקות חציית עצים ב-C#.

 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 traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); Console.Write(node.value + ' '); traverseInorder(node.right); } void traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); Console.Write(node.value + ' '); } void traversePreorder() { traversePreorder(root); } void traverseInorder() { traverseInorder(root); } 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 Preorder traversal of given binary tree is - '); bt.traversePreorder(); Console.WriteLine(); Console.WriteLine('The Inorder traversal of given binary tree is - '); bt.traverseInorder(); Console.WriteLine(); Console.WriteLine('The Postorder traversal of given binary tree is - '); bt.traversePostorder(); } } 

תְפוּקָה

תכנית: כתוב תוכנית ליישום טכניקות חציית עצים ב-C++.

f סרטים

 #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 preorder*/ void traversePreorder(struct node* root) { if (root == NULL) return; cout&lt;<' '<element<left); traversepreorder(root->right); } /*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); } *function to traverse the nodes of binary tree in postorder* void traversepostorder(struct node* root) { if (root="=" null) return; traversepostorder(root->left); traversePostorder(root-&gt;right); cout&lt;<' '<element<left="createNode(28);" root->right = createNode(48); root-&gt;left-&gt;left = createNode(23); root-&gt;left-&gt;right = createNode(33); root-&gt;left-&gt;left-&gt;left = createNode(13); root-&gt;left-&gt;left-&gt;right = createNode(26); root-&gt;right-&gt;left = createNode(43); root-&gt;right-&gt;right = createNode(58); root-&gt;right-&gt;right-&gt;left = createNode(53); root-&gt;right-&gt;right-&gt;right = createNode(68); cout&lt;<'
 the preorder traversal of given binary tree is -
'; traversepreorder(root); cout<<'
 inorder traverseinorder(root); postorder traversepostorder(root); return 0; } < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/17/tree-traversal-inorder-6.webp" alt="Tree Traversal"> <p> <strong>Program:</strong> Write a program to implement tree traversal techniques in Java.</p> <pre> class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class Tree { Node root; /* root of the tree */ Tree() { root = null; } /*function to print the nodes of given binary in Preorder*/ void traversePreorder(Node node) { if (node == null) return; System.out.print(node.value + &apos; &apos;); traversePreorder(node.left); traversePreorder(node.right); } /*function to print the nodes of given binary in Inorder*/ void traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); System.out.print(node.value + &apos; &apos;); traverseInorder(node.right); } /*function to print the nodes of given binary in Postorder*/ void traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); System.out.print(node.value + &apos; &apos;); } void traversePreorder() { traversePreorder(root); } void traverseInorder() { traverseInorder(root); } void traversePostorder() { traversePostorder(root); } public static void main(String args[]) { Tree pt = new Tree(); 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(&apos;The Preorder traversal of given binary tree is - &apos;); pt.traversePreorder(); System.out.println(&apos;
&apos;); System.out.println(&apos;The Inorder traversal of given binary tree is - &apos;); pt.traverseInorder(); System.out.println(&apos;
&apos;); System.out.println(&apos;The Postorder traversal of given binary tree is - &apos;); 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/17/tree-traversal-inorder-7.webp" alt="Tree Traversal"> <h2>Conclusion</h2> <p>In this article, we have discussed the different types of tree traversal techniques: preorder traversal, inorder traversal, and postorder traversal. We have seen these techniques along with algorithm, example, complexity, and implementation in C, C++, C#, and java.</p> <p>So, that&apos;s all about the article. Hope it will be helpful and informative to you.</p> <hr></'
></'></'></'>

תְפוּקָה

לאחר ביצוע הקוד לעיל, הפלט יהיה -

סיכום

במאמר זה, דנו בסוגים השונים של טכניקות חציית עצים: חציית עץ מראש, חציית סדר ומעבר לאחר הזמנה. ראינו טכניקות אלו יחד עם אלגוריתם, דוגמה, מורכבות ויישום ב-C, C++, C# ו-java.

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