אפשר בבקשה קוד של מעבר על עץ *לא* בינארי

ליה

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

צבי-ש

פוסט זה נמחק!

chagold

@ליה כתב באפשר בבקשה קוד של מעבר על עץ *לא* בינארי:

מעבר על עץ

https://algoritmim.co.il/interview-practice/how-to-do-a-tree-walk/
(בהתחשב בכתוב)

ליה

@chagold אין שם קוד לעץ לא בינארי

yossiz

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

OdedDvir

@ליה בעץ לא בינארי, מספר הצאצאים שיוצאים מכל צומת יכול להיות גדול מ-2. דרך אחת לאחסן את ההפניות לצאצאים הוא ע"י מערך, לכן צריך לסרוק את כל הצמתים במערך.
לדוגמא (#C):

public class Node {
   public string Value {get; set;}
   public Node[] Nodes {get; set;}
}
// ...
public void traverseNode(Node root) {
   Console.Writeline(root.Value); // print node's value
   foreach (Node n in root.Nodes) {
      traverseNode(n);
    }
}

ליה

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

chagold

@ליה כתב באפשר בבקשה קוד של מעבר על עץ *לא* בינארי:

רק שהתסבכתי ואולי בכלל יש דרך לסרוק את המערך לא כמו עץ

באיזה שפה?

ליה

@chagold JS תודה

dovid

@ליה מעבר על מאפייני אובייקט נעשה בעזרת Object.keys שנותן את שמות המפתחות, או לולאת for .. in שנותנת גם את שמות המפתחות, או מתודת Object.entries שמחזירה אוסף של זוגות מפתח-ערך, ועוד.
לשםמעבר עמוק, כלומר שבכל מפתח בודקים את הערך ואם הוא אובייקט יורדים גם לרמה שלו, אפשר להשתמש ברקורסיה. הנה דוגמה:

     function iterateDeep(obj)
     { 
       if (Object(obj) === obj)
         for (const [k, v] of Object.entries(obj))
           iterateDeep(v);
       else
         console.log("item: " + obj);
     }

הפונקציה הזו בודקת קודם אם הערך הוא אובייקט או משהו אחר, אם זה אובייקט היא עוברת על הערכים של הצאצאים (מאפיינים בנים בלבד) וקוראת עבור כל ערך לפונקציה הזו בעצמה. אם הצאצא הוא אובייקט העבודה תחזור על עצמה.
בכזו פונקציה יש בעיה של אינסופיות, כי לאובייקט יכול להיות חבר למשל שמצביע על על עצמו, או על אביו/אחיו, ואז יהיה מעגל אינסופי. בשביל למנוע את זה אפשר להוסיף דגל בתוך האובייקט במהלך המעבר:

  if (Object(obj) === obj) {
    for (const [k, v] of Object.entries(obj))
      if(!v.passLoop){
         iterateDeep(v, [...keys, k]); 
         v.passLoop = true;
      }
  } else
     console.log("item: " + obj);

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

function iterateDeep(obj, keys = [])
{ 
  if (Object(obj) === obj) {
    for (const [k, v] of Object.entries(obj))
      if(!v.passLoop){
         iterateDeep(v, [...keys, k]); 
         v.passLoop = true;
      }
  } else
    console.log(`${keys.join('.')}: ${obj}`);
}

dovid

בגירסת גנרטור (הלולאה מתקדמת רק על פי בקשה של for ..of)

function* iterateDeep(obj, keys = [])
{ 
  if (Object(obj) === obj) {
    for (const [k, v] of Object.entries(obj))
      if(!v.passLoop){
         yield* iterateDeep(v, [...keys, k]); 
         v.passLoop = true;
      }
  } else
    yield [keys.join('.'), obj];
}

yossiz

@dovid תודה! למדתי כמה דברים שלא הכרתי מהתשובה!

הערה קטנה:

if(!v.passLoop){
... 
v.passLoop = true;

שורות אלו נכשלים במקרה ש-v הוא null
אולי אפשר לתקן כך:

if(!v?.passLoop){
...
if (v) v.passLoop = true;

או שיש צורה יותר אלגנטית

dovid

@yossiz תודה!

if(v && !v.passLoop)

ליה

@dovid היי עדיין לא הסתדרתי ואני מרגישה שאני מתפוצצת. אני לא מבינה מה אני מפספסת

המערך שלי כולו מכיל אובייקטים, שחלקם מכילים בתוכם גם אובייקטים:

זה המערך:

[
  {
    "id": "1",
    "name": "sara",
    "children": [
      {
        "id": "2",
        "name": "dian"
      },
      {
        "id": "3",
        "name": "michael",
        "children": [
          {
            "id": "4",
            "name": "dkny"
          },
          {
            "id": "5",
            "name": "Anne"
          }
        ]
      }

    ]
  },
  {
    "id": "6",
    "name": "Tommy"
  },
  {
    "id": "7",
    "name": "danken",
    "children": [
      {
        "id": "8",
        "name": "biria"
      }
    ]
  }

]

תודה על היחס.

ליה

@dovid אני רוצה לעבור עליו ולהדפיס את האבא ובתוכו את הבן ובתוך הבן את הנכד, את התגיות אני עושה בHTML (את זה לפחות אני יודעת חח)
תודה רבה

chagold

@ליה https://jsfiddle.net/g4tsejc9/

dovid

@ליה באיזה פרימוורק את משתמשת? אנגולר?

תחומים - פורום חרדי מקצועי

אפשר בבקשה קוד של מעבר על עץ לא בינארי