Almenn mynd af trénu, útfærsla og fleira

Margir reyndu líklega að finna almenna trésmíði, en leitarvélin fann aðeins tvöfalda... Tvöfaldur leitartré, tvískipt tré og mörg önnur reiknirit.
Já, reyndar er almenna tréð hvergi notað, umferðin er hæg, notkunartilvikin eru lítil.

Svo ég spurði sjálfan mig þessarar spurningar og nú mun ég útskýra hvernig tréð er byggt. Svo helst ætti almenn trébygging að geyma þrjár breytur:

• vísa til elsta sonarins
• vísa til bróður
• gögnin sem þú ætlar að geyma

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

Við skulum lýsa yfir bendi á hornpunktinn:

Node *tree = NULL;

Við verðum að semja fyrirfram hvernig á að slá inn hornpunkta, þetta er ekki tvíundartré og hver hornpunktur getur haft eins mörg börn og óskað er.

• + 2 (eða +ssbb 2) - innsetning í tré (fyrir almennt tré er leiðin gefin af línunni, þar sem r er sköpun rótar, s er umskipti yfir í elsta soninn, b er umskipti til bróðir);

Leyfðu mér að gefa þér dæmi:

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

Útkoman verður tré eins og þetta:

1
  2
    5
  3
    6
    7
  3

Fyrst skulum við búa til fall sem bætir við hornpunkti, nefnilega úthlutar minni fyrir hornpunktinn og sendir bendi til þessa hornpunkts (upphaflega ekki tengdur neinu).

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

Þú þarft líka að búa til fall sem sér um slóðastrenginn (+bs...). Í hvert skipti sem við byrjum yfirferðina frá rótinni, ef hún er ekki búin til, þá sendum við NULL (við getum ekki gert neitt). Ef það er enginn hornpunktur, þá verðum við að búa það til. Við förum í create tree fallið og fáum bendi í rótina.

Athugaðu að Node**tree fer framhjá uppbyggingunni, ekki að afrita það. Þetta gefur okkur möguleika á að breyta hlutum sem við getum ekki gert með Node *tré yfirlýsingunni.

Almennt verðum við að finna bendil á hornpunktinn sem við þurfum að bæta soninum við:

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

Svona byggjum við tré.

P.S. fyrsta greinin mín, svo vinsamlegast ekki dæma of hart

Heimild: www.habr.com