היפוך עץ בינארי בג'אווה
1. סקירה כללית
היפוך עץ בינארי הוא אחת הבעיות שאולי נתבקש לפתור במהלך ראיון טכני.
במדריך מהיר זה נראה כמה דרכים שונות לפתור בעיה זו.
2. עץ בינארי
עץ בינארי הוא מבנה נתונים שבו לכל אלמנט לכל היותר שני ילדים, המכונים הילד השמאלי והילד הימני. האלמנט העליון של העץ הוא צומת השורש, ואילו הילדים הם הצמתים הפנימיים.
למרות זאת, אם לצומת אין ילד, זה נקרא עלה.
עם זאת, בואו ניצור את האובייקט שלנו שמייצג צומת:
מחלקה ציבורית TreeNode {ערך int פרטי; TreeNode פרטי rightChild; TreeNode פרטי leftChild; // גטרים וקובעים}לאחר מכן, בואו ניצור את העץ שבו נשתמש בדוגמאות שלנו:
TreeNode leaf1 = TreeNode חדש (1); TreeNode leaf2 = TreeNode חדש (3); TreeNode leaf3 = TreeNode חדש (6); TreeNode leaf4 = TreeNode חדש (9); TreeNode nodeRight = TreeNode חדש (7, עלה 3, עלה 4); TreeNode nodeLeft = TreeNode חדש (2, עלה 1, עלה 2); שורש TreeNode = TreeNode חדש (4, nodeLeft, nodeRight); בשיטה הקודמת יצרנו את המבנה הבא:
על ידי היפוך העץ משמאל לימין, בסופו של דבר יהיה לנו המבנה הבא:
3. היפוך העץ הבינארי
3.1. שיטה רקורסיבית
בדוגמה הראשונה, נשתמש ברקורסיה כדי להפוך את העץ.
ראשית כל, אנו קוראים לשיטה שלנו באמצעות שורש העץ, ואז נשתמש בה בשמאל ובילדים הנכונים בהתאמה עד שנגיע לעלי העץ:
בטל פומבי reverseRecursive (TreeNode treeNode) {if (treeNode == null) {return; } Temp של TreeNode = treeNode.getLeftChild (); treeNode.setLeftChild (treeNode.getRightChild ()); treeNode.setRightChild (temp); reverseRecursive (treeNode.getLeftChild ()); reverseRecursive (treeNode.getRightChild ()); }3.2. שיטה איטרטיבית
בדוגמה השנייה, נפנה את העץ בגישה איטרטיבית. בשביל זה, אנחנו הולכים להשתמש ב- רשימה מקושרת, אותו אנו מאותחלים עם שורש העץ שלנו.
לאחר מכן, על כל צומת שאנו סוקרים מהרשימה, אנו מוסיפים את ילדיה לרשימה לפני שנחליף אותם.
אנו ממשיכים להוסיף ולהסיר מה- רשימה מקושרת עד שנגיע לעלי העץ:
חלל ציבורי reverseIterative (TreeNode treeNode) {תור לרשימה = LinkedList חדש (); אם (treeNode! = null) {queue.add (treeNode); } בעוד (! queue.isEmpty ()) {TreeNode node = queue.poll (); אם (node.getLeftChild ()! = null) {queue.add (node.getLeftChild ()); } אם (node.getRightChild ()! = null) {queue.add (node.getRightChild ()); } TreeNode temp = node.getLeftChild (); node.setLeftChild (node.getRightChild ()); node.setRightChild (temp); }}4. מסקנה
במאמר מהיר זה בדקנו את שתי הדרכים להפוך עץ בינארי. התחלנו באמצעות שיטה רקורסיבית כדי להפוך אותה. ואז, בסופו של דבר, השתמשנו בצורה איטרטיבית להשגת אותה תוצאה.
את קוד המקור השלם של דוגמאות אלה ומקרים לבדיקת יחידות ניתן למצוא באתר Github.
