Üldine vaade puule, rakendamine ja mitte ainult

Paljud, arvatavasti, on proovinud leida üldise puu ülesehitust, kuid otsingumootor leidis ainult binaarseid… Binaarne otsingupuu, binaarse puu läbimine ja paljud teised algoritmid.
Jah, tõesti, üldist puu ei kasutata kusagil, läbimine on aeglane, kasutusvõimalused on väikesed.

Nii et, ma küsisin endalt seda küsimust ja nüüd selgitan, kuidas puu tegelikult ehitatakse. Nii et ideaalis peaks üldise puu struktuur hoidma kolme muutuja:

• viit vanemale pojale
• viit vennale
• andmed, mida kavatsete salvestada

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

Deklareerime viite juurele:

Node *tree = NULL;

Me peame eelnevalt kokku leppima, kuidas sisestada tippe, sest see ei ole binaarne puu ja igal tipul võib olla suvaline arv poegi.

• + 2 (või +ssbb 2) — lisamine puusse (üldise puu puhul määratakse tee stringiga, kus r on juure loomine, s — liikumine vanema poja juurde, b — liikumine venna juurde);

Tõin näite:

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

Tulemusena saab selline puu:

1
  2
    5
  3
    6
    7
  3

Käivitame funktsiooni, mis lisab tippu, nimelt eraldab mälu tipule ja edastab viite sellele tipule (alguses ei ole see millegagi seotud).

Node *create_tree(int v) {
  Node *Tree = (Node *) malloc(sizeof(Node));
  Tree->key = v;
  // nullime viidikud vendadele ja poegadele, sõltumatu tipp, mis salvestab väärtuse
  Tree->son = NULL;
  Tree->brother = NULL;
  return Tree;
}

Samuti on vajalik luua funktsioon, mis töötleb teepäringut (+bs…). Iga kord alustame läbitöötamist juurest, kui see ei ole loodud, siis väljastame NULL (me ei saa mitte midagi teha). Kui tippu ei ole, peame selle looma. Liigume funktsiooni luua puu ja saame viite juurele.

Märkusena, Node ** tree edastab struktuuri, mitte kopeerib. See annab meile võimaluse muuta, mida ei saa teha Node *tree deklareerimisega.

Kokkuvõttes peame leidma viite tipule, kellele poja lisamine on vajalik:

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); // luuakse juur
            t = *tree;
            return *tree;
          }
        if (a[i] == 's') {
          if (t = to_son(t)) // funktsioon, mis tagastab poja punkti
            continue;
          return NULL; // muidu NULL
        }
        if (a[i] == 'b') {
          if (t = to_brother(t)) // tagastab viite venna t 
            continue;
          return NULL;
        }
    }
    if (t->son != NULL) {
    t = last_son(t); // oleme jõudnud tippu, kuhu tahtsime 
   // ja nüüd suundume viimasele pojale,
   // et lisada see nimekirja lõppu
    t->brother = create_tree(value);
    return t->brother;
    }
    else {// kui poega ei ole, siis loome selle
      t->son = create_tree(value);
      return t->son;
    }
}

Nii ehitame puu.

P.S. see on minu esimene artikkel, palun ärge hinnake mind liiga karmilt

Allikas: habr.com