חידה תכנותית : סריקת עץ בינארי על פי סדר הרמות
בהינתן השורש `root` של עץ בינארי, עליך לכתוב פונקציה שמחזירה את סדר הצמתים כאשר עוברים על העץ משמאל לימין רמה אחר רמה.
לדוגמה:
Input: root = [1, 2, 3, 4, 5, None, 7] Output: [[1], [2, 3], [4, 5, 7]]
דוגמאות נוספות:
Input: root = [1] Output: [[1]]
Input: root = [] Output: []
הרעיון שמאפשר לפתור את הבעיה ביעילות
בשביל לפתור את הבעיה צריך לבקר בצמתים ברמה נמוכה יותר לפני שעוברים לבקר בצמתים ברמה גבוהה יותר, מה שעושה ביעילות רבה אלגוריתם חיפוש לרוחב BFS שנעזר במבנה נתונים תור Queue לצורך קביעת סדר הביקור בצמתי העץ. כאשר מבקרים בצומת מסוים מסירים את הצומת הזה מהתור ומוסיפים את הילדים של הצומת לתור. דבר המבטיח ביקור בצמתים ההורים לפני שמבקרים בצמתים הילדים עבור כל רמה בנפרד. השימוש באלגוריתם BFS ובמבנה נתונים תור queue מאפשר סקירה שיטתית של העץ הבינארי, ומספק סדר לביקור בצמתים לפי סדר הרמות.
הפתרון וההסבר
להלן הפתרון המלא, ההסבר בהמשך:
class TreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def level_order_traversal(root):
levels = []
# Handle the case in which the tree is None
if not root:
return levels
# Initialize a queue for implementing BFS
q = [root]
while q:
# Each level takes a separate array in the results
level = []
# Capture the number of nodes in the current level
q_len = len(q)
# Traverse the current level
for _ in range(q_len):
# Dequeue the front node
current = q.pop(0)
# Use only if isn't None
if current:
level += [current.data]
# Enqueue the left and right children for the next iteration
q += [current.left]
q += [current.right]
# If the level is not empty, add it to the result
if level:
levels += [level]
return levels
נבחן את הפונקציה `level_order_traversal`:
# Binary tree to traverse
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
#root.right.left = Node(6)
root.right.right = Node(7)
root.right.right.left = Node(8)
print(level_order_traversal(root)) # [[1], [2, 3], [4, 5, 7], [8]]
root = Node(1)
print(level_order_traversal(root)) # [[1]]
root = None
print(level_order_traversal(root)) # []
נסביר.
-
הגדרת הפונקציה:
def level_order_traversal(root):
- הפונקציה level_order_traversal() מקבלת פרמטר `root`. ה-`root` הוא הצומת ממנו מתחילה סריקת העץ.
-
אתחול משתנים:
levels = []
- המשתנה `levels` מאותחל כרשימה ריקה אשר תשמש לאחסון הצמתים של העץ הבינארי בכל רמה.
נאתחל בנוסף משתנה תור Queue:
q = [root]
-
הרשימה `q` מאותחלת עם צומת ה-`root`. רשימה זו משמשת בתור Queue כדי ליישם את אלגוריתם חיפוש לרוחב (BFS). תור הוא מבנה נתונים שפועל לפי סדר FIFO (First-In, First-Out). במקרה זה, התור ישמש ליישום חיפוש לרוחב (BFS), שהוא שיטה למעבר על עץ רמה אחר רמה. צומת השורש מתווסף לתור כדי לאתחל את המעבר.
-
עיקר העבודה של האלגוריתם BFS מתבצע בתוך לולאה שתמשיך לרוץ כל עוד התור Queue אינו ריק מה שאומר שהלולאה תמשיך לרוץ כל עוד קיימים צמתים שטרם ביקרנו בהם:
while q:
בתוך הלולאה החיצונית:
-
הדבר הראשון שעושים בתוך הלולאה הוא לאתחל מערך ריק לאחסון הצמתים של הרמה הנוכחית:
level = []
-
נאתחל משתנה שיאחסן את מספר הפריטים העכשוויים בתור במספר זה נשתמש להגבלת מספר הפעמים שהלולאה הפנימית תרוץ:
q_len = len(q)
-
מעבר על הרמה הנוכחית בתוך לולאה פנימית:
for _ in range(q_len):
- שורה זו מתחילה לולאה פנימית שתעבור על כל הצמתים ברמה הנוכחית של העץ. המשתנה `_` הוא מחזיק מקום במקום משתנה.
בתוך הלולאה הפנימית:
-
מסירים את הצומת הקדמי מהתור ומציבים במשתנה `current`:
current = q.pop(0)
-
במידה והצומת הנוכחי אינו `None` נוסיף אותו למערך הרמה הנוכחית:
if current: level += [current.data]
-
נוסיף את צאצאי הצומת הנוכחי הימני והשמאלי לתור בשביל שהלולאה תמשיך לרוץ:
q += [current.left] q += [current.right]
-
ביציאה מהלולאה הפנימית, במידה ומערך הרמה הנוכחית אינו ריק, נוסיף אותו למערך התוצאות הסופי:
if level: levels += [level]
-
-
לבסוף, הפונקציה מחזירה את מערך התוצאות הסופי:
return levels
הערכת ביצועים
מורכבות זמן: O(N) כאשר `N` הוא מספר הצמתים בעץ הבינארי מכיוון שהשימוש בתור Queue ואלגוריתם BFS מבטיח ביקור בכל אחד מצמתי העץ בדיוק פעם אחת.
מורכבות מקום: O(N) כאשר N הוא מספר הצמתים בעץ הבינארי כאשר מורכבות המקום נובעת משני משתנים `q` המהווה את התור ו-levels שהוא התוצאה המוחזרת. האורך של שניהם מוגבל ל-`N` פריטים לכל היותר.
מדריכים נוספים בסדרה ללימוד פייתון שעשויים לעניין אותך
חידה תכנותית : מציאת האב המשותף הרחוק ביותר LCA בעץ בינארי
תורים Queues - הבנה ויישום בפייתון
יישום עץ בינארי בפייתון - המדריך למתחילים
לכל המדריכים בסדרה ללימוד פייתון
אהבתם? לא אהבתם? דרגו!
0 הצבעות, ממוצע 0 מתוך 5 כוכבים
המדריכים באתר עוסקים בנושאי תכנות ופיתוח אישי. הקוד שמוצג משמש להדגמה ולצרכי לימוד. התוכן והקוד המוצגים באתר נבדקו בקפידה ונמצאו תקינים. אבל ייתכן ששימוש במערכות שונות, דוגמת דפדפן או מערכת הפעלה שונה ולאור השינויים הטכנולוגיים התכופים בעולם שבו אנו חיים יגרום לתוצאות שונות מהמצופה. בכל מקרה, אין בעל האתר נושא באחריות לכל שיבוש או שימוש לא אחראי בתכנים הלימודיים באתר.
למרות האמור לעיל, ומתוך רצון טוב, אם נתקלת בקשיים ביישום הקוד באתר מפאת מה שנראה לך כשגיאה או כחוסר עקביות נא להשאיר תגובה עם פירוט הבעיה באזור התגובות בתחתית המדריכים. זה יכול לעזור למשתמשים אחרים שנתקלו באותה בעיה ואם אני רואה שהבעיה עקרונית אני עשוי לערוך התאמה במדריך או להסיר אותו כדי להימנע מהטעיית הציבור.
שימו לב! הסקריפטים במדריכים מיועדים למטרות לימוד בלבד. כשאתם עובדים על הפרויקטים שלכם אתם צריכים להשתמש בספריות וסביבות פיתוח מוכחות, מהירות ובטוחות.
המשתמש באתר צריך להיות מודע לכך שאם וכאשר הוא מפתח קוד בשביל פרויקט הוא חייב לשים לב ולהשתמש בסביבת הפיתוח המתאימה ביותר, הבטוחה ביותר, היעילה ביותר וכמובן שהוא צריך לבדוק את הקוד בהיבטים של יעילות ואבטחה. מי אמר שלהיות מפתח זו עבודה קלה ?
השימוש שלך באתר מהווה ראייה להסכמתך עם הכללים והתקנות שנוסחו בהסכם תנאי השימוש.