A fa általános nézete, a megvalósítás és egyebek

Valószínűleg sokan próbáltak általános fakonstrukciót találni, de a kereső csak binárisakat talált... Bináris keresőfa, bináris fa bejárás és sok más algoritmus.
Igen, valóban, az általános fa sehol nem használatos, a bejárás lassú, a használati esetek kicsik.

Feltettem magamnak ezt a kérdést, és most elmagyarázom, hogyan épül fel a fa. Ideális esetben tehát egy általános fastruktúrának három változót kell tárolnia:

• mutató a legidősebb fiúra
• mutat a testvérre
• a tárolni kívánt adatokat

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

Deklaráljunk egy mutatót a csúcsra:

Node *tree = NULL;

Előre meg kell állapodnunk a csúcsok bevitelében, ez nem egy bináris fa, és minden csúcsnak tetszőleges számú gyermeke lehet.

• + 2 (vagy +ssbb 2) - beillesztés egy fába (általános fánál az utat a vonal adja, ahol r a gyökér létrehozása, s átmenet a legidősebb fiúhoz, b átmenet testvér);

Mondok egy példát:

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

Az eredmény egy ilyen fa lesz:

1
  2
    5
  3
    6
    7
  3

Először hozzunk létre egy függvényt, amely hozzáad egy csúcsot, nevezetesen memóriát foglal a csúcs számára, és átad egy mutatót ennek a csúcsnak (kezdetben nem kapcsolódik semmihez).

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

Létre kell hoznia egy függvényt is, amely kezeli az elérési út karakterláncát (+bs...). Minden alkalommal, amikor a gyökérből indítjuk a bejárást, ha nem jön létre, akkor NULL-t adunk ki (nem tehetünk semmit). Ha nincs csúcs, akkor létre kell hoznunk. Megyünk a Create tree függvényhez, és kapunk egy mutatót a gyökérre.

Vegye figyelembe, hogy a csomópont** fa átadja a struktúrát, nem másolja azt. Ez lehetővé teszi számunkra, hogy olyan dolgokat változtassunk meg, amelyeket a Node *fa deklarációval nem tudunk megtenni.

Általában meg kell találnunk egy mutatót arra a csúcsra, amelyhez hozzá kell adnunk a fiát:

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

Így építünk fát.

P.S. az első cikkem, ezért kérlek, ne ítélj túl szigorúan

Forrás: will.com