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

Sokan valószínűleg próbáltak általános fa felépítést keresni, de a kereső csak binárisokat talált... Bináris keresőfa, bináris fa bejárása és sok más algoritmus.
Igen, valóban, az általános fa sehol sem használatos, a bejárás lassú, a felhasználási lehetőségek pedig kicsik.

Tehát, felvetettem ezt a kérdést, és most elmagyarázom, hogyan is épül fel a fa. Tehát ideálisan az általános fa struktúrájának három változót kellene tárolnia:

• mutató az első fiára
• mutató a testvérre
• az adatok, amelyeket tárolni szeretnél

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

Nyilvános mutatót a csúcsra:

Node *tree = NULL;

Előre meg kell állapodnunk arról, hogyan valósítjuk meg a csúcsok bevitelét, hiszen ez nem bináris fa, és minden csúcsnak tetszőleges számú fia lehet.

• + 2 (vagy +ssbb 2) — beszúrás a fába (az általános fa esetében az út egy olyan karakterláncot határoz meg, ahol r a gyökér létrehozása, s — az első fiúra lépés, b — a testvérre lépés);

Hoztam egy példát:

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

Ennek eredményeként egy ilyen fa jön létre:

1
  2
    5
  3
    6
    7
  3

Először készítsünk egy függvényt, amely a csúcs hozzáadását végzi, nevezetesen lefoglalja a memóriát a csúcs számára, és átadja a csúcsra mutató mutatót (kezdetben semmivel nem összekapcsolva).

Node *create_tree(int v) {
  Node *Tree = (Node *) malloc(sizeof(Node));
  Tree->key = v;
  //nullázzuk a testvérekre és fiókra mutató mutatókat, független csúcs, ami az értéket tárolja
  Tree->son = NULL;
  Tree->brother = NULL;
  return Tree;
}

Létre kell hozni egy funkciót is, amely a +bs... karakterláncot kezeli. Minden alkalommal a gyökérből indulunk, ha az nem létezik, NULL-t adunk vissza (nem tudunk mit kezdeni vele). Ha a csúcs nem létezik, akkor meg kell azt alkotnunk. Lépjünk a fá létrehozó funkcióba, és kapjunk mutatót a gyökérhez.

Megjegyzésként, a Node **tree a struktúrát adja át, és nem másolja. Ez lehetővé teszi számunkra, hogy módosítsuk, amit nem lehet megtenni a Node *tree nyilvánítása esetén.

Összességében meg kell találnunk a csúcsra mutató mutatót, amelyhez a fiát hozzá kell adni:

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); // létrehozzuk a gyökér
            t = *tree;
            return *tree;
          }
        if (a[i] == 's') {
          if (t = to_son(t)) // a funkció, amely visszaadja a fia pointerét
            continue;
          return NULL; // különben NULL
        }
        if (a[i] == 'b') {
          if (t = to_brother(t)) // visszaadja a t bátyját
            continue;
          return NULL;
        }
    }
    if (t->son != NULL) {
    t = last_son(t); // eljutottunk a csúcsra, amelyhez akartunk 
   // és most megyünk az utolsó fiához,
   // hogy hozzáadjuk a lista végéhez
    t->brother = create_tree(value);
    return t->brother;
    }
    else {// ha nincs fia, akkor létrehozzuk
      t->son = create_tree(value);
      return t->son;
    }
}

Így építjük fel a fát.

P.S. ez az első cikkem, szóval kérlek ne ítélj szigorúan

Forrás: habr.com