Ծառի ընդհանուր տեսքը, իրականացումը և այլն

Շատերը հավանաբար փորձել են գտնել ընդհանուր ծառի կոնստրուկցիա, բայց որոնողական համակարգը գտել է միայն երկուականները... Երկուական որոնման ծառ, երկուական ծառի անցում և շատ այլ ալգորիթմներ։
Այո, իսկապես, ընդհանուր ծառը ոչ մի տեղ չի օգտագործվում, անցումը դանդաղ է, օգտագործման դեպքերը փոքր են։

Այսպիսով, ես ինքս ինձ տվեցի այս հարցը և հիմա կբացատրեմ, թե ինչպես է կառուցված ծառը: Այսպիսով, իդեալականորեն, ընդհանուր ծառի կառուցվածքը պետք է պահպանի երեք փոփոխական.

• ցուցիչ դեպի ավագ որդուն
• ցուցիչ եղբորը
• տվյալները, որոնք դուք պատրաստվում եք պահել

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**tree-ն անցնում է կառուցվածքը, այլ ոչ թե պատճենում է այն: Սա մեզ հնարավորություն է տալիս փոխելու բաներ, որոնք մենք չենք կարող անել Node *tree հռչակագրի հետ:

Ընդհանուր առմամբ, մենք պետք է գտնենք ցուցիչ դեպի այն գագաթը, որին պետք է ավելացնենք որդին.

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;
    }
}

Ահա թե ինչպես ենք մենք ծառ կառուցում։

Հ.Գ. սա իմ առաջին հոդվածն է, ուստի խնդրում եմ շատ խիստ մի դատեք

Source: www.habr.com