Algemiene werjefte fan 'e beam, útfiering en mear

In protte minsken hawwe wierskynlik besocht om in algemiene beamkonstruksje te finen, mar de sykmasine fûn allinich binêre ... Binêre sykbeam, binêre beamtraversal en in protte oare algoritmen.
Ja, yndie, de algemiene beam wurdt net oeral brûkt, de trochgong is stadich, de gebrûksgefallen binne lyts.

Dat, ik frege mysels dizze fraach en no sil ik útlizze hoe't de beam boud is. Dus, ideaal soe in algemiene beamstruktuer trije fariabelen opslaan:

• oanwizer nei âldste soan
• oanwizer nei broer
• de gegevens dy't jo sille opslaan

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

Litte wy in oanwizer nei it toppunt ferklearje:

Node *tree = NULL;

Wy moatte foarôf iens wurde hoe't jo hoekpunten ynfiere; dit is gjin binêre beam, en elke hoekpunt kin safolle bern hawwe as jo wolle.

• + 2 (of +ssbb 2) - ynfoegje yn in beam (foar in algemiene beam wurdt it paad jûn troch de line, wêrby't r de skepping fan in woartel is, s in oergong is nei de âldste soan, b is in oergong nei in broer);

Lit my dy in foarbyld jaan:

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

It resultaat sil in beam wêze as dizze:

1
  2
    5
  3
    6
    7
  3

Lit ús earst in funksje oanmeitsje dy't in toppunt taheakket, nammentlik ûnthâld foar it toppunt allocearret en in oanwizer trochjaan oan dit toppunt (ynearsten net ferbûn mei wat).

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

Jo moatte ek in funksje meitsje dy't de paadstring (+bs...) behannelet. Elke kear begjinne wy ​​​​de trochgong fan 'e root, as it net oanmakke is, dan útfiere wy NULL (wy kinne neat dwaan). As der gjin hoekpunt is, dan moatte wy it oanmeitsje. Wy geane nei de funksje meitsje beam en krije in oanwizer nei de woartel.

Tink derom dat Node ** tree de struktuer trochjaan, it net kopiearret. Dit jout ús de mooglikheid om dingen te feroarjen dy't wy net kinne dwaan mei de Node *tree-deklaraasje.

Yn 't algemien moatte wy in oanwizer fine nei it toppunt dêr't wy de soan taheakje moatte:

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

Dit is hoe't wy in beam bouwe.

P.S. myn earste artikel, dus oardielje asjebleaft net te hurd

Boarne: www.habr.com