מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/עצי חיפוש בינריים: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 275:
==פעולות למעבר על כל איברי העץ==
לעתים רוצים לעבור על כל איברי העץ, אם כדי להדפיסם, ואם למטרה אחרת. נראה כעת שלוש שיטות (רקורסיביות) מקובלות למעבר על כל איברי העץ, ונשתמש בהדפסה כדוגמה. בשיעורי הבית תתבקש להראות שכל אחד מזמני הריצה של המעברים הוא לינארי במספר האיברים בעץ.
===מעבר Pre-Order===
בצורת מעבר זו, כאשר מגיעים לצומת:
#ראשית מדפיסים את (איבר) הצומת עצמו
#לאחר מכן עוברים על תת העץ הימני שלו
#לאחר מכן עוברים על תת-העץ השמאלי שלו
<source lang = "python">
Pre-Order(nd)
3 Print(nd.value)
4 Pre-Order(nd.l-child)
5 Pre-order(nd.r-child)
</source>
התרשים הבא מראה את סדר המעבר בצומת:
[[תמונה:dsa_binary_search_tree_pre_order.png|מרכז|100%|מעבר pre-order.]]
===מעבר Post-Order===
בצורת מעבר זו, כאשר מגיעים לצומת:
#ראשית עוברים על תת-העץ השמאלי שלו
#לאחר מכן עוברים על תת העץ הימני שלו
#לאחר מכן מדפיסים את (איבר) הצומת עצמו
<source lang = "python">
Post-Order(nd)
2 return
4 Post-Order(nd.l-child)
5 Post-order(nd.r-child)
3 Print(nd.value)
▲3 if child != Nil
</source>
התרשים הבא מראה את סדר המעבר בצומת:
▲5 if parent == Nil
[[תמונה:dsa_binary_search_tree_post_order.png|מרכז|100%|מעבר post-order.]]
▲7 return
===מעבר In-Order===
בצורת מעבר זו, כאשר מגיעים לצומת:
#ראשית עוברים על תת-העץ השמאלי שלו
#לאחר מכן מדפיסים את (איבר) הצומת עצמו
#לאחר מכן עוברים על תת העץ הימני שלו
<source lang = "python">
In-Order(nd)
1 if nd == Nil
2 return
3 In-Order(nd.l-child)
4 Print(nd.value)
5 In-order(nd.r-child)
</source>
התרשים הבא מראה את סדר המעבר בצומת:
[[תמונה:dsa_binary_search_tree_in_order.png|מרכז|100%|מעבר in-order.]]
בשיעורי הבית תתבקש להוכיח שצורת מעבר זו תדפיס את כל איברי העץ בסדר עולה.
===האלגוריתם===
| |||