כיצד לחצות עץ חיפוש בינארי

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

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

Inorder Traversal

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

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

אלגוריתם של מעבר לא-סדר

חזור כדי לעבור את כל הצמתים של ה-BST:

1. חצו באופן רקורסיבי את תת-העץ השמאלי.
2. בקר בצומת השורש.
3. חצו באופן רקורסיבי את תת-העץ הימני.

ויזואליזציה של מעבר לא סדר

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

בעץ החיפוש הבינארי הזה, 56 הוא צומת השורש. ראשית, עליך לעבור את תת-העץ השמאלי 32, לאחר מכן את צומת השורש 56, ולאחר מכן את תת-העץ הימני 62.

עבור תת-העץ 32, חצו תחילה את תת-העץ השמאלי, 28. לתת-עץ הזה אין ילדים, אז לאחר מכן חצו את הצומת 32. לאחר מכן, חצו את תת-העץ הימני, 44, שגם לו אין ילדים. לכן סדר המעבר של תת-העץ המושרש ב-32 הוא 28 -> 32 -> 44.

לאחר מכן, בקר בצומת השורש, 56.

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

אז האלגוריתם מבקר בצמתים של העץ בסדר הבא:

28 -> 32 -> 44 -> 56 -> 58 -> 62 -> 88

יישום של Inorder Traversal

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

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

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

אלגוריתם של מעבר הזמנה מראש

חזור כדי לעבור את כל הצמתים של ה-BST:

1. בקר בצומת השורש.
2. חצו באופן רקורסיבי את תת-העץ השמאלי.
3. חצו באופן רקורסיבי את תת-העץ הימני.

ויזואליזציה של מעבר הזמנה מראש

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

בעץ החיפוש הבינארי הזה, התחל בעיבוד צומת השורש, 56. לאחר מכן חצו את תת-העץ השמאלי, 32, ואחריו תת-העץ הימני, 62.

עבור תת-העץ השמאלי, עבד את הערך בצומת השורש, 32. לאחר מכן, חצו את תת-העץ השמאלי, 28, ואז לבסוף את תת-העץ הימני, 44. זה משלים את המעבר של תת-העץ השמאלי המושרש ב-32. המעבר מתרחש בסדר הבא: 56 -> 32 -> 28 -> 44.

עבור תת-העץ הימני, עבד את הערך בצומת השורש, 62. לאחר מכן, חצו את תת-העץ השמאלי, 58, ואז לבסוף את תת-העץ הימני, 88. שוב, לאף צומת אין ילדים, כך שהמעבר הושלם בשלב זה.

עברת את העץ המלא בסדר הבא:

56 -> 32 -> 28 -> 44 -> 62 -> 58 -> 88

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

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

מעבר הזמנה

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

אלגוריתם של מעבר הזמנה

חזור כדי לעבור את כל הצמתים של ה-BST:

1. חצו באופן רקורסיבי את תת-העץ השמאלי.
2. חצו באופן רקורסיבי את תת-העץ הימני.
3. בקר בצומת השורש.

ויזואליזציה של מעבר הזמנה

האיור הבא מציג את מעבר הסדר של עץ החיפוש הבינארי:

התחל בחציית תת-העץ השמאלי, 32, ולאחר מכן את תת-העץ הימני, 62. סיים על ידי עיבוד צומת השורש, 56.

כדי לעבד את תת-העץ, המושרש ב-32, חצו את תת-העץ השמאלי שלו, 28. מכיוון של-28 אין ילדים, עבור אל תת-העץ הימני, 44. תהליך 44 מכיוון שגם לו אין ילדים. לבסוף, עבד את צומת השורש, 32. עברת תת-עץ זה בסדר 28 -> 44 -> 32.

עבד את תת-העץ הימני באמצעות אותה גישה לביקור בצמתים בסדר 58 -> 88 → 62.

לבסוף, עבד את צומת השורש, 56. אתה תחצה את העץ המלא בסדר הזה:

28 -> 44 -> 32 -> 58 -> 88 -> 62 -> 56

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

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

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

מורכבות זמן ומרחב של חציית עצי חיפוש בינאריים

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

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

קוד פייתון עבור חציית עץ חיפוש בינארי

להלן תוכנית Python לביצוע כל שלושת חציית עצי החיפוש הבינאריים:

# Node class is used to create individual nodes
# of the Binary Search Tree (BST)
classNode:
def__init__(self, element):
self.left = None
self.right = None
self.value = element
# Function to perform the inorder tree traversal
definorder(root):
 if root:
# Traverse left subtree
inorder(root.left)
# Traverse root
print(str(root.value) + ", ", end='')
# Traverse right subtree
inorder(root.right)
# Function to perform the postorder tree traversal
defpostorder(root):
 if root:
# Traverse left subtree
postorder(root.left)
# Traverse right subtree
postorder(root.right)
# Traverse root
print(str(root.value) + ", ", end='')
# Function to perform the preorder tree traversal
defpreorder(root):
 if root:
# Traverse root
print(str(root.value) + ", ", end='')
# Traverse left subtree
preorder(root.left)
# Traverse right subtree
preorder(root.right)
# Creating nodes of the tree
root = Node(56)
root.left = Node(32)
root.right = Node(62)
root.left.left = Node(28)
root.left.right = Node(44)
root.right.left = Node(58)
root.right.right = Node(88)
print("Inorder Traversal of BST: ")
inorder(root)
print()
print("Preorder Traversal of BST: ")
preorder(root)
print()
print("Postorder Traversal of BST: ")
postorder(root)

תוכנית זו אמורה להפיק את הפלט הבא:

אלגוריתמים שחובה לדעת למתכנתים

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