Üldine puu struktuur, rakendused ja rohkem

Paljud on ilmselt püüdnud leida üldise puu koostamist, kuid otsingumootor leidis ainult binaarsed... Binaarne otsingupuu, binaarsete puude läbimine ja palju muid algoritme.
Jah, tõepoolest, üldist puu ei kasutata kusagil, läbimine on aeglane ja kasutusvõimalused on väikesed.

Nii et ma küsisin endalt seda küsimust ja nüüd selgitan, kuidas puu koostamine ikkagi käib. Niisiis, ideaalis peaks üldise puu struktuur sisaldama kolme muutujaid:

• näitaja vanema pojani
• näitaja vennale
• andmed, mida kavatsete salvestada

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

Deklarime näitaja tipu jaoks:

Node *tree = NULL;

Peame eelnevalt kokku leppima, kuidas tippe sisestada, see ei ole ju binaarne puu, ning igal tipul võib olla suvaline arv poegi.

• + 2 (või +ssbb 2) — puusse lisamine (üldise puu puhul antakse tee stringina, kus r tähistab juure loomist, s — ülemise poja juurde minekut, b — venna juurde minekut);

Toon näite:

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

Tulemuseks on selline puu:

1
  2
    5
  3
    6
    7
  3

Esmakordina funktsioon, mis lisab sõlme, eraldades mälu ja edastades viite sellele sõlmele (alguses ei ole seostatud millegagi).

Node *create_tree(int v) {
  Node *Tree = (Node *) malloc(sizeof(Node));
  Tree->key = v;
  // lähtestame viidatud vennad ja pojad, iseseisev sõlm, mis hoiab väärtust
  Tree->son = NULL;
  Tree->brother = NULL;
  return Tree;
}

Samuti on vajalik luua funktsioon, mis töötleb teepunkti (+bs…). Iga kord alustame läbimist juurest; kui see ei ole loodud, siis väljastame NULL (me ei saa midagi teha). Kui sõlme ei ole, peame selle looma. Liigume funktsiooni, et luua puu, ja saame viite juurele.

Märkus: Node ** tree edastab struktuuri, mitte ei kopeeri. See annab meile võimaluse muudatusi teha, mida ei saa teha Node *tree kuulutamise korral.

Kokkuvõttes peame leidma viite sõlmele, kuhu tuleb lisada poeg:

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); // loome juure
            t = *tree;
            return *tree;
          }
        if (a[i] == 's') {
          if (t = to_son(t)) // funktsioon, mis tagastab poja aadressi
            continue;
          return NULL; // muidu NULL
        }
        if (a[i] == 'b') {
          if (t = to_brother(t)) // tagastab t venna aadressi
            continue;
          return NULL;
        }
    }
    if (t->son != NULL) {
    t = last_son(t); // oleme jõudnud tipu juurde, kuhu tahtsime
   // ja nüüd liigume tema viimase poja poole,
   // et lisada nimekirja lõppu
    t->brother = create_tree(value);
    return t->brother;
    }
    else {// kui poega ei ole, loome selle
      t->son = create_tree(value);
      return t->son;
    }
}

Nii ehitame me puu.

P.S. see on minu esimene artikkel, nii et palun mitte liiga karmilt hinnata

Allikas: habr.com