Pamja e përgjithshme e drurit, realizimi dhe jo vetëm

Shumë ndoshta, kanë provuar të gjejnë ndërtimin e një tree të përgjithshëm, por motorët e kërkimit gjenin vetëm binar… Duarë të binarëve të kërkimit, kalimi i një tree binar dhe shumë algorithme të tjera.
Po, në të vërtetë, një tree i përgjithshëm nuk përdoret askund, kalimi është i ngadaltë, dhe mundësitë e përdorimit janë të vogla.

Pra, unë e kam bërë këtë pyetje dhe tani do të shpjegoj se si ndërtimi i tij do të jetë. Pra, në mënyrë ideale, struktura e një tree të përgjithshëm duhet të mbajë tre variabla:

• përshkruesin e djalit më të madh
• përshkruesin e vëllait
• të dhënat që dëshironi të ruani

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

Deklarojmë përshkruesin për majën:

Node *tree = NULL;

Duhet të pajtohemi paraprakisht sesi do të bëjmë hyrjen e majave, nuk është një tree binar dhe çdo maje mund të ketë aq djem sa të dojë.

• + 2 (ose +ssbb 2) — insertimi i një tree (për një tree të përgjithshëm, rruga caktë përshkruhet me një varg, ku r krijon majën, s — kalon te djali më i madh, b — kalon te vëllai);

Do të jap një shembull:

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

Si rezultat, do të dalë një tree i tillë:

1
  2
    5
  3
    6
    7
  3

Fillimisht krijojmë një funksion që kryen shtimin e një maje, duke rezervuar kujtesë për atë dhe duke kaluar përshkruesin për këtë maje (fillimisht e lidhur me asgjë).

Node *create_tree(int v) {
  Node *Tree = (Node *) malloc(sizeof(Node));
  Tree->key = v;
  //kemi zerozuar përshkruesit për vëllezërit dhe djemtë, një maje e pavarur që ruan vlerën
  Tree->son = NULL;
  Tree->brother = NULL;
  return Tree;
}

Duhet gjithashtu të krijojmë një funksion që trajton vargun e rrugës (+bs…). Çdo herë fillojmë kalimin nga maja, nëse ajo nuk është krijuar, atëherë nxjerrim NULL (nuk mund të bëjmë asgjë). Nëse maja nuk ekziston, atëherë duhet ta krijojmë. Kalojmë në funksionin e krijimit të tree dhe marrim përshkruesin për majën.

Për të vërejtur, Node ** tree përcjell strukturën, jo kopjon. Kjo na jep mundësinë të ndryshojmë, çka nuk mund të bëhet në krahasim me shpalljen Node *tree.

Në përgjithësi duhet të gjejmë përshkruesin për majën, për të cilën duhet të shtojmë një djalë:

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); // krijojmë majën
            t = *tree;
            return *tree;
          }
        if (a[i] == 's') {
          if (t = to_son(t)) // funksioni që kthen përshkruesin për djalin
            continue;
          return NULL; //ndryshe NULL
        }
        if (a[i] == 'b') {
          if (t = to_brother(t)) // kthen përshkruesin për vëllain t 
            continue;
          return NULL;
        }
    }
    if (t->son != NULL) {
    t = last_son(t); // kaluam në majën për të cilën doja 
   // dhe tani shkojmë tek djali i fundit,
   // për të shtuar në fund të listës
    t->brother = create_tree(value);
    return t->brother;
    }
    else { //nëse nuk ka djalë, do ta krijojmë
      t->son = create_tree(value);
      return t->son;
    }
}

Kështu e ndërtuam tree-në.

P.S. artikulli im i parë, kështu që ju lutem mos më gjykoni ashpër

Burimi: habr.com