שאלה על עצים בינארים מדעי המחשב ב'

[Holy]

1. רשימה מקושרת

או

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

[isildur]

סתם רעיון

אפשר לבנות מערך בגודל מספר הרמות בעץ (מקסימום n מינימום logn ) כשכל תא במערך הוא מצביע לרשימה מקושרת, ואז אפשר פשוט לשרשר לכל תא את האיברים בכל רמה, פשוט מעבירים ברקורסיה משתנה שמכיל את הרמה של הצומת ואז יודעים לאן במערך לשרשר.

כל זה נעשה בסיבוכיות של (n) כאשר n הוא מספר האיברים, משום שחייבים לבקר בכל צומת לפחות פעם אחת

[Ghosthunter]

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

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

[Aurora Borealis]

לכל מי שמציע להשתמש במערך באורך מסויים.

זה בלתי אפשרי!

כי אי אפשר לקבוע את האורך של המערך כשהתוכנית רצה, ולכן כל הפתרון לא נכון.

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

[Holy]

מה אי אפשר?!

הכל אפשרי פשוט אתה לא יודע איך

על הקצאה דינאמית שמעת?

[isildur]

לכל מי שמציע להשתמש במערך באורך מסויים.

זה בלתי אפשרי!

כי אי אפשר לקבוע את האורך של המערך כשהתוכנית רצה, ולכן כל הפתרון לא נכון.

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

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

ושימוש ברשימה מקושרת בפתרון שהצעתי לא יעיל כי ברשימות מקושרות אין גישה ישירה, מה שמעלה את הסיבוכיות של הפתרון.

[Aurora Borealis]

יודע מה, אז מותר.

אז מסכים איתי שאז אתה צריך ליצור עוד מתודה כלשהיא שבאמת תספור את הגובה של העץ?

זה מאוד מטופש לעשות בבחינת בגרות דבר כזה (לכתוב 2 מתודות במקום אחת פשוטה).

אגב, אתה אומר שאפשר, בבקשה תראה לי איך (שום ציניות או משו בסגנון, אני באמת רוצה לדעת).

[Holy]

איך אפשר מה?

להקצות מערך עם גודל דינאמי?

[isildur]

יודע מה, אז מותר.

אז מסכים איתי שאז אתה צריך ליצור עוד מתודה כלשהיא שבאמת תספור את הגובה של העץ?

זה מאוד מטופש לעשות בבחינת בגרות דבר כזה (לכתוב 2 מתודות במקום אחת פשוטה).

אגב, אתה אומר שאפשר, בבקשה תראה לי איך (שום ציניות או משו בסגנון, אני באמת רוצה לדעת).

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

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

int **arrayptr;
arrayptr = (int**) malloc ( sizeof( int ) * n);

int** בגלל שזה מצביע למערך של מצביעים

וכמובן שכדי למנוע זליגת זיכרון צריך להשתמש free לאחר שמסיימים להשתמש במערך

[Holy]

אם כבר אז

int **arrayptr;
arrayptr = (int**) malloc ( sizeof( int* ) * n);

בשביל ליצור מערך של מצביעים או

int *arrayptr;
arrayptr = (int*) malloc ( sizeof( int ) * n);

בשביל ליצור מערך של int

לעשות מערך בגודל מספר האיברים בעץ זה פשוט ביזבוז אדיר של זיכרון

[isildur]

צודק זה int* בכל זאת הC שלי קצת חלודה בC++ זה יותר פשוט.

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

[beastie]

הנה משהו קטן שארגנתי שלפי דעתי עושה את העבודה...

procedure print_level_sums(T: tree_type);
(* prints the sum of each level in a tree. *)

begin
  for i:=0 to num_of_levels(T) do
    writeln('Level num ', i, ': ', level_sum(T, i));
end;


function num_of_levels(T: tree_type): integer;
(* returns the number of levels in a tree. *)
(* expects the tree to be initialized and non-empty. *)

begin
  if tree_is_empty(tree_lsub(T)) and tree_is_empty(tree_rsub(T)) then
    num_of_levels:= 1
  else
    num_of_levels:= 1 + max(num_of_levels(tree_lsub(T)), num_of_levels(tree_rsub(T)));
end;


function level_sum(T: tree_type; n: integer): integer;
(* returns the sum of all the members in the level n. *)
(* assumes that there is a level n in the tree. *)

var
  x: tree_info_type;

begin
  if n=0 then
    tree_root_retrieve(T,x)
  else
    x:= level_sum(tree_lsub(T), n-1) + level_sum(tree_rsub(T), n-1);

  level_sum:= x;
end;

בברכה.