במאמר זה, נדון במעבר הזמנה מראש במבנה הנתונים. למבני נתונים ליניאריים כגון מחסנית, מערך, תור וכו', יש רק דרך אחת לעבור את הנתונים. אבל במבנה נתונים היררכי כגון עֵץ , ישנן מספר דרכים לעבור את הנתונים.
במעבר בהזמנה מוקדמת, תחילה מבקרים בצומת השורש, לאחר מכן מבקרים בעץ המשנה השמאלי ולאחר מכן בעץ המשנה הימני. תהליך מעבר הזמנה מראש יכול להיות מיוצג כ-
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' הוא הגודל של עץ בינארי.
ואילו, מורכבות החלל של מעבר הזמנה מראש היא O(1) , אם לא ניקח בחשבון את גודל המחסנית עבור קריאות לפונקציות. אחרת, מורכבות החלל של מעבר הזמנה מראש היא O(h) , כאשר '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.
עץ חיפוש בינארי]
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(); } } תְפוּקָה
לאחר ביצוע הקוד לעיל, הפלט יהיה -
אז, זה הכל לגבי המאמר. מקווה שהמאמר יהיה מועיל ואינפורמטיבי עבורך.