Dîtina gelemperî ya darê, pêkanîn û bêtir

Dibe ku gelek kesan hewl dane ku avahiyek darek gelemperî bibînin, lê motora lêgerînê tenê yên binary dîtin... Dara lêgerînê ya binar, gera dara binary û gelek algorîtmayên din.
Erê, bi rastî, dara gelemperî li her deverê nayê bikar anîn, rêwitî hêdî ye, dozên karanîna piçûk in.

Ji ber vê yekê, min ev pirs ji xwe kir û niha ez ê şirove bikim ka dar çawa tê çêkirin. Ji ber vê yekê, bi îdeal, strukturek darek gelemperî divê sê guhêrbar hilîne:

• nîşana kurê mezin
• nîşana bira
• daneyên ku hûn ê hilînin

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

Werin em nîşankerek ji bo vertexê ragihînin:

Node *tree = NULL;

Divê em ji berê de li hev bikin ka meriv çawa têkevin vertîkan ev ne darek binary e, û her verteks dikare bi qasî ku tê xwestin hebe.

• + 2 (an +ssbb 2) - ketina nav darekê (ji bo darek gelemperî, rê ji hêla rêzê ve tê dayîn, ku r afirandina kokek e, s veguheztina kurê mezin e, b veguheztinek e bira);

Ez ji we re mînakek bidim:

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

Encam dê darek bi vî rengî be:

1
  2
    5
  3
    6
    7
  3

Pêşîn, em fonksiyonek biafirînin ku vekêşek lê zêde bike, ango, bîranînê ji bo vertexê veqetîne û nîşanek ji vê vekêşanê re derbas bike (di destpêkê de ne bi tiştek ve girêdayî ye).

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

Her weha hûn hewce ne ku fonksiyonek ku rêzika rê (+bs...) digire biafirînin. Her gava ku em dest bi gerokê ji kokê dikin, heke ew neyê afirandin, wê hingê em NULL derdixin (em nikarin tiştek bikin). Ger vertex tune be, wê hingê divê em wê biafirînin. Em diçin fonksiyona dara afirandinê û nîşanek ji kokê re digirin.

Bala xwe bidinê ku Node**dara strukturê derbas dike, wê kopî nake. Ev ji me re şiyana guheztina tiştên ku em nikanin bi danezana Node * darê bikin, dide me.

Bi gelemperî, pêdivî ye ku em nîşanek ji vertexê re bibînin ku divê em kurê lê zêde bikin:

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

Bi vî awayî em darekê çêdikin.

PS ev gotara min a yekem e, ji kerema xwe pir tund dadbar nekin

Source: www.habr.com