Ağacın ümumi görünüşü, icra və daha çoxu.

Çoxları, bəlkə də, ümumi tipli bir ağacın qurulmasını tapmağa çalışıb, amma axtarış sistemi yalnız ikili axtarış ağacı, ikili ağacın gedişi və bir çox digər alqoritmləri tapmışdı.
Bəli, həqiqətən də, ümumi tipli ağac nərə istifadə edilmir, gediş yavaşdır, istifadəsi üçün variantlar azdır.

Beləliklə, bu sualı verdim və indi necə qurulduğunu izah edəcəyəm. Beləliklə, ideal olaraq, ümumi tipli ağac strukturu üç dəyişəni saxlamaq üçün olmalıdır:

• böyük oğulun göstəricisi
• qardaşın göstəricisi
• saxlamaq istədiyiniz məlumatlar

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

Könüllü göstəricini elan edək:

Node *tree = NULL;

Biz əvvəlcədən razılaşmalıyıq ki, düyünlərin daxil edilməsi necə həyata keçiriləcək, çünki bu, ikili ağac deyil və hər düyün istədiyiniz qədər oğul apara bilər.

• + 2 (və ya +ssbb 2) — ağaca əlavə etmə (ümumi tipli ağac üçün yol bir sırada müəyyən edilir, burada r kök yaratmaq, s — böyük oğula keçmək, b — qardaşa keçmək);

Məsələn:

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

Nəticədə belə bir ağac çıxacaq:

1
  2
    5
  3
    6
    7
  3

Əvvəlcə bir düyün əlavə edən funksiyanı yaradaq, yəni düyün üçün yaddaş ayırır və bu düyünün göstəricisini ötürür (ilk olaraq heç bir şeylə bağlı deyil).

Node *create_tree(int v) {
  Node *Tree = (Node *) malloc(sizeof(Node));
  Tree->key = v;
  // qardaşlar və oğullara olan göstəriciləri sıfırlayırıq, dəyəri saxlayan müstəqil düyün
  Tree->son = NULL;
  Tree->brother = NULL;
  return Tree;
}

Həmçinin, +bs… yolunu işləyən bir funksiya yaratmaq lazımdır. Hər dəfə kökdən keçidə başlayırıq, əgər o yaradılmayıbsa, NULL görünür (heç bir şey edə bilmirik). Əgər düyün yoxdursa, onu yaratmalıyıq. Ağac yaratma funksiyasına keçirik və kök göstəricisini əldə edirik.

Diqqət yetirmək lazımdır ki, Node ** tree strukturu ötürür, lakin surətini çıxarmır. Bu, bizə dəyişiklik etməyə imkan tanıyır, bu da Node *tree elan edəndə mümkün deyil.

Ümumilikdə, oğul əlavə etmək istədiyimiz düyünün göstəricisini tapmalıyıq:

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); // kök yaradırıq
            t = *tree;
            return *tree;
          }
        if (a[i] == 's') {
          if (t = to_son(t)) // oğulun göstəricisini qaytaran funksiya
            continue;
          return NULL; // əks halda NULL
        }
        if (a[i] == 'b') {
          if (t = to_brother(t)) // t qardaşına göstəricisi qaytarır
            continue;
          return NULL;
        }
    }
    if (t->son != NULL) {
    t = last_son(t); // istədiyimiz düyünə keçdik
   // və indi son oğuluna gedirik,
   // siyahının sonuna əlavə etmək üçün
    t->brother = create_tree(value);
    return t->brother;
    }
    else { // əgər oğul yoxdursa, onu yaradacağıq
      t->son = create_tree(value);
      return t->son;
    }
}

Beləliklə, biz ağacı qururuq.

P.S. Bu, mənim ilk məqaləmdir, ona görə də sərt qiymətləndirməyinizi xahiş edirəm.

Mənbə: habr.com