שני פיצ'רים של פייתון שמסתדרים יופי יחד הם ה Generators והרקורסיות. בתרגיל של היום רציתי לשלב את שניהם כדי לחפש מידע במבנה נתונים של עץ. במבנה של עץ יש לכל צומת ערך ואוסף של ילדים אליהם אפשר להגיע מאותו צומת. ב Python אפשר לתאר את כל המבנה בצורה רקורסיבית עם המחלקה הבאה:

@dataclass
class Node:
    value: int
    children: List['Node']

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

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

root = Node(10, [
    Node(5, [
        Node(99, [
            Node(101, []),
            Node(102, []),
            Node(103, []),
            ]),
        Node(9, [
            Node(25, [])
            ]),
        ]),
    Node(8, [])
    ])

עכשיו אפשר להמשיך ולשאול "מה המתקן הכי שווה בפארק?". קל לראות בעין שהערך של המתקן הכי מוצלח הוא 103. עכשיו נראה איך פייתון היה יכול למצוא את זה:

def dfs(node):
    yield node.value
    for child in node.children:
        yield from dfs(child)

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

print(max(dfs(root)))

עכשיו נסו אתם שני תרגילי הרחבה:

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

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

הקוד המלא שכתבתי כתוכנית אחת למי שרוצה לקחת כבסיס לתרגילי ההרחבה הוא:

from dataclasses import dataclass
from typing import List


@dataclass
class Node:
    value: int
    children: List['Node']


def dfs(node):
    yield node.value
    for child in node.children:
        yield from dfs(child)


root = Node(10, [
    Node(5, [
        Node(99, [
            Node(101, []),
            Node(102, []),
            Node(103, []),
            ]),
        Node(9, [
            Node(25, [])
            ]),
        ]),
    Node(8, [])
    ])

print(max(dfs(root)))
print("---")

for v in dfs(root):
    print(v)