מבט כללי על העץ, יישום ועוד

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

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

• מצביע לבן הבכור
• מצביע לאח
• הנתונים שאתה הולך לאחסן

struct Tnode {
    int key;
    struct Tnode *son;
    struct Tnode *brother;
};
typedef struct Tnode Node;

בואו נכריז על מצביע לקודקוד:

Node *tree = NULL;

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

• + 2 (או +ssbb 2) - הכנסה לעץ (עבור עץ כללי, הנתיב ניתן על ידי הקו, כאשר r הוא יצירת שורש, s הוא מעבר לבן הבכור, b הוא מעבר אל אח);

אני אתן דוגמה:

+r 1
+ 2
+ 3
+ 3
+s 5
+sb 6
+sb 7

התוצאה תהיה עץ כזה:

1
  2
    5
  3
    6
    7
  3

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

Node *create_tree(int v) {
  Node *Tree = (Node *) malloc(sizeof(Node));
  Tree->key = v;
  //обнуляем указатели к братьям и сыновьям, независимая вершина, которая хранит value
  Tree->son = NULL;
  Tree->brother = NULL;
  return Tree;
}

אתה צריך גם ליצור פונקציה שמטפלת במחרוזת הנתיב (+bs...). בכל פעם שאנחנו מתחילים את המעבר מהשורש, אם הוא לא נוצר, אז נוציא NULL (אנחנו לא יכולים לעשות כלום). אם אין קודקוד, אז עלינו ליצור אותו. אנחנו הולכים לפונקציית create tree ומקבלים מצביע לשורש.

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

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

Node* add_node(Node **tree, const char *a) {
  Node* t = *tree;
  int value;
  scanf("%d", &value);
  int i = 0;
      while (a[++i] != ' ') {
        if (a[i] == 'r') {
            *tree = create_tree(value); // создаем корень
            t = *tree;
            return *tree;
          }
        if (a[i] == 's') {
          if (t = to_son(t)) // функция, которая возвращает указатель на сына
            continue;
          return NULL; //иначе NULL
        }
        if (a[i] == 'b') {
          if (t = to_brother(t)) //возвращает указатель на брата t 
            continue;
          return NULL;
        }
    }
    if (t->son != NULL) {
    t = last_son(t); // мы перешли к вершине, к которой хотели 
   //и теперь идем к последнему ее сыну,
   //чтобы добавить в конец списка
    t->brother = create_tree(value);
    return t->brother;
    }
    else {//если сына нет, то создадим его
      t->son = create_tree(value);
      return t->son;
    }
}

כך בונים עץ.

נ.ב. זה המאמר הראשון שלי, אז בבקשה אל תשפוט בחומרה

מקור: www.habr.com