יישום עץ בינארי בג'אווה

1. הקדמה

במאמר זה נעסוק בהטמעת עץ בינארי בג'אווה.

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

2. עץ בינארי

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

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

הנה ייצוג חזותי מהיר מסוג עץ בינארי זה:

לצורך היישום, נשתמש בעזר צוֹמֶת כיתה שתאחסן int ערכים ושמור על התייחסות לכל ילד:

class Node {int value; צומת שמאל; צומת מימין; צומת (ערך int) {this.value = value; ימין = אפס; שמאל = אפס; }}

לאחר מכן, בואו נוסיף את צומת ההתחלה של העץ שלנו, הנקרא בדרך כלל שורש:

מחלקה ציבורית BinaryTree {שורש הצומת; // ...}

3. פעולות נפוצות

עכשיו, בואו נראה את הפעולות הנפוצות ביותר שאנחנו יכולים לבצע על עץ בינארי.

3.1. הכנסת אלמנטים

הפעולה הראשונה שאנחנו הולכים לכסות היא הכנסת צמתים חדשים.

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

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

ראשית, ניצור שיטה רקורסיבית לביצוע ההכנסה:

צומת פרטי addRecursive (צומת הנוכחי, ערך int) {אם (הנוכחי == null) {להחזיר צומת חדש (ערך); } אם (value current.value) {current.right = addRecursive (current.right, value); } אחר {// ערך כבר קיים החזרת זרם; } להחזיר זרם; }

לאחר מכן ניצור את השיטה הציבורית שמתחילה את הרקורסיה מ- שורש צוֹמֶת:

הוסף חלל ציבורי (ערך int) {root = addRecursive (root, value); }

בואו נראה כיצד נוכל להשתמש בשיטה זו ליצירת העץ מהדוגמה שלנו:

פרטי BinaryTree createBinaryTree () {BinaryTree bt = BinaryTree חדש (); bt.add (6); bt.add (4); bt.add (8); bt.add (3); bt.add (5); bt.add (7); bt.add (9); החזר bt; }

3.2. מציאת אלמנט

בואו כעת נוסיף שיטה לבדוק אם העץ מכיל ערך ספציפי.

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

פרטי בוליאני containNodeRecursive (צומת הנוכחי, ערך int) {אם (הנוכחי == null) {להחזיר שקר; } אם (value == current.value) {return true; } ערך החזר <current.value? containNodeRecursive (current.left, value): containNodeRecursive (current.right, value); }

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

לאחר מכן, בואו ניצור את השיטה הציבורית שמתחילה מה- שורש:

public boolean containNode (int value) {return containNodeRecursive (root, value); }

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

@Test הציבור בטל שניתןABinaryTree_WhenAddingElements_ThenTreeContainsThoseElements () {BinaryTree bt = createBinaryTree (); assertTrue (bt.containsNode (6)); assertTrue (bt.containsNode (4)); assertFalse (bt.containsNode (1)); }

כל הצמתים שנוספו צריכים להיות כלולים בעץ.

3.3. מחיקת אלמנט

פעולה נפוצה נוספת היא מחיקת צומת מהעץ.

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

צומת פרטי deleteRecursive (צומת הנוכחי, ערך int) {if (current == null) {return null; } אם (value == current.value) {// צומת למחיקה נמצא // ... קוד למחיקת הצומת ילך לכאן} if (value <current.value) {current.left = deleteRecursive (current.left, ערך); זרם החזרה; } current.right = deleteRecursive (current.right, value); זרם החזרה; }

ברגע שנמצא את הצומת למחיקה, ישנם 3 מקרים שונים עיקריים:

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

בואו נראה כיצד נוכל ליישם את המקרה הראשון כאשר הצומת הוא צומת עלים:

אם (current.left == null && current.right == null) {return null; }

בואו נמשיך עם המקרה כאשר לצומת ילד אחד:

אם (current.right == null) {return current.left; } אם (current.left == null) {return current.right; }

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

לבסוף, עלינו לטפל במקרה בו לצומת יש שני ילדים.

ראשית, עלינו למצוא את הצומת שיחליף את הצומת שנמחק. נשתמש בצומת הקטן ביותר של הצומת למחיקת עץ העץ הימני:

פרטי int findSmallestValue (שורש הצומת) {להחזיר root.left == null? root.value: findSmallestValue (root.left); }

לאחר מכן, אנו מקצים את הערך הקטן ביותר לצומת למחיקה ולאחר מכן נמחק אותו מעץ המשנה הימני:

int smallestValue = findSmallestValue (current.right); current.value = smallestValue; current.right = deleteRecursive (current.right, smallestValue); זרם החזרה;

לבסוף, בואו ניצור את השיטה הציבורית שמתחילה את המחיקה מה- שורש:

מחיקה בטלנית ציבורית (ערך int) {root = deleteRecursive (root, value); }

עכשיו, בואו נבדוק שהמחיקה עובדת כצפוי:

@Test הציבור בטל שניתןABinaryTree_WhenDeletingElements_ThenTreeDoesNotContainThoseElements () {BinaryTree bt = createBinaryTree (); assertTrue (bt.containsNode (9)); מחק bt. (9); assertFalse (bt.containsNode (9)); }

4. חוצה את העץ

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

נשתמש באותו עץ בו השתמשנו בעבר ונציג את סדר המעבר לכל מקרה.

4.1. חיפוש עומק ראשון

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

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

המעבר לפי הסדר מורכב מביקור תחילה בעץ המשנה השמאלי, אחר כך בצומת השורש, ולבסוף בעץ המשנה הימני:

חלל ציבורי traverseInOrder (צומת צומת) {if (node! = null) {traverseInOrder (node.left); System.out.print ("" + node.value); traverseInOrder (node.right); }}

אם נקרא לשיטה זו, פלט הקונסולה יציג את המעבר לפי הסדר:

3 4 5 6 7 8 9

הזמנה מוקדמת של ביקור מבקרת תחילה בצומת הבסיס, אחר כך בעץ המשנה השמאלי ולבסוף בעץ העץ הימני:

חלל ציבורי traversePreOrder (צומת צומת) {if (node! = null) {System.out.print ("" + node.value); traversePreOrder (node.left); traversePreOrder (node.right); }}

ובואו לבדוק את המעבר להזמנה מראש בפלט המסוף:

6 4 3 5 8 7 9

מעבר לאחר ההזמנה מבקר בסוף העץ השמאלי, העץ הימני ובצומת השורש בסוף:

חלל ציבורי traversePostOrder (צומת צומת) {if (node! = null) {traversePostOrder (node.left); traversePostOrder (node.right); System.out.print ("" + node.value); }}

להלן הצמתים בהזמנה:

3 5 4 7 9 8 6

4.2. רוחב-חיפוש ראשון

זהו סוג נפוץ אחר של מעבר זה מבקר בכל צמתי הרמה לפני שעובר לשלב הבא.

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

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

חלל ריק traverseLevelOrder () {if (root == null) {return; } צמתים לתור = LinkedList חדש (); nodes.add (שורש); בעוד (! nodes.isEmpty ()) {Node node = nodes.remove (); System.out.print ("" + node.value); אם (node.left! = null) {nodes.add (node.left); } אם (node.right! = null) {nodes.add (node.right); }}}

במקרה זה, סדר הצמתים יהיה:

6 4 8 3 5 7 9

5. מסקנה

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

קוד המקור המלא של הדוגמאות זמין באתר GitHub.


$config[zx-auto] not found$config[zx-overlay] not found