Vista general de l'arbre, implementació i més

Probablement molta gent va intentar trobar una construcció d'arbre general, però el motor de cerca només n'ha trobat de binaris... Arbre de cerca binari, recorregut d'arbre binari i molts altres algorismes.
Sí, de fet, l'arbre general no s'utilitza enlloc, el recorregut és lent, els casos d'ús són petits.

Per tant, em vaig fer aquesta pregunta i ara explicaré com es construeix l'arbre. Per tant, idealment, una estructura d'arbre general hauria d'emmagatzemar tres variables:

• punter al fill gran
• punter al germà
• les dades que vas a emmagatzemar

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

Anem a declarar un punter al vèrtex:

Node *tree = NULL;

Hem d'acordar prèviament com introduir els vèrtexs; aquest no és un arbre binari, i cada vèrtex pot tenir tants fills com es vulgui.

• + 2 (o +ssbb 2) - inserció en un arbre (per a un arbre general, el camí ve donat per la línia, on r és la creació d'una arrel, s és una transició al fill gran, b és una transició a un germà);

Permeteu-me que us posi un exemple:

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

El resultat serà un arbre com aquest:

1
  2
    5
  3
    6
    7
  3

Primer, creem una funció que afegeixi un vèrtex, és a dir, assigna memòria per al vèrtex i passa un punter a aquest vèrtex (inicialment no està connectat a res).

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

També heu de crear una funció que gestioni la cadena de ruta (+bs...). Cada vegada que comencem la travessa des de l'arrel, si no es crea, donem sortida a NULL (no podem fer res). Si no hi ha vèrtex, l'hem de crear. Anem a la funció de creació d'arbre i obtenim un punter a l'arrel.

Tingueu en compte que Node**tree passa l'estructura, no la copia. Això ens dóna la possibilitat de canviar coses que no podem fer amb la declaració de Node *tree.

En general, hem de trobar un punter al vèrtex al qual hem d'afegir el fill:

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

Així és com construïm un arbre.

P.S. el meu primer article, així que si us plau, no jutgis massa severament

Font: www.habr.com