Pamja e përgjithshme e pemës, realizimi dhe jo vetëm

Shumë njerëz, ndoshta, kanë provuar të gjejnë ndërtimin e një peme të zakonshme, por motorët e kërkimit gjenin vetëm pemë binare... Pemë binare kërkimi, kalimi i pemës binare dhe shumë algoritmo të tjera.
Po, vërtet, pemë e zakonshme nuk përdoret askund, kalimi është i ngadalshëm, mundësitë e përdorimit janë të vogla.

Kështu, unë e kam bërë këtë pyetje dhe tani do të shpjegoj si ndërttohet pemë. Pra, në mënyrë ideale, struktura e pemës së zakonshme duhet të ruajë tre variabla:

• referenca në djalin e madh
• referenca në vëllain
• të dhënat që do të ruani

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

Deklarojmë referencën në majë:

Node *tree = NULL;

Duhet të bie dakord më parë se si do ta bëjmë futjen e majave, sepse nuk është një pemë binare, dhe çdo maje mund të ketë në mënyrë të pakufizuar djem.

• + 2 (ose +ssbb 2) — inserim në pemë (për pemën e zakonshme, rruga përcaktohet nga një varg, ku r krijon majën, s — kalon te djali i madh, b — kalon te vëllai);

Të jap një shembull:

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

Si rezultat do të dalë kjo pemë:

1
  2
    5
  3
    6
    7
  3

Për fillim, le të krijojmë një funksion që realizon shtimin e majës, konkretisht rezervon hapësirë për majën dhe kalon referencën në këtë majë (fillimisht pa lidhje me asgjë).

Node *create_tree(int v) {
  Node *Tree = (Node *) malloc(sizeof(Node));
  Tree->key = v;
  \/\/nullifikojmë referencat te vëllezërit dhe djemtë, është një maje e pavarur që ruan vlera
  Tree->son = NULL;
  Tree->brother = NULL;
  return Tree;
}

Duhet gjithashtu të krijojmë një funksion që trajton stringun e rrugës (+bs…). Çdo herë fillojmë kalimin nga maja, nëse ajo nuk është krijuar, atëherë kthejmë NULL (nuk mund të bëjmë asgjë). Nëse maja nuk ekziston, ne duhet ta krijojmë atë. Kalojmë te funksioni i krijimit të pemës dhe marrim referencën në majë.

Për vëmendje, Node ** tree kalon strukturën, e jo e kopjon. Kjo na jep mundësinë të ndryshojmë, gjë që nuk mund të bëhet në dallim nga deklarimi Node *tree.

Në përgjithësi, ne duhet të gjejmë referencën në majën ku duam të shtojmë djalin:

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ë rrënjën
            t = *tree;
            return *tree;
          }
        if (a[i] == 's') {
          if (t = to_son(t)) // funksioni që kthen treguesin te biri
            continue;
          return NULL; // ndryshe NULL
        }
        if (a[i] == 'b') {
          if (t = to_brother(t)) // kthen treguesin te vëllai t
            continue;
          return NULL;
        }
    }
    if (t->son != NULL) {
    t = last_son(t); // kemi kaluar te maja, ku do të donim 
   // dhe tani po shkojmë te biri i fundit,
   // për ta shtuar në fund të listës
    t->brother = create_tree(value);
    return t->brother;
    }
    else { // nëse s'ka bir, atëherë do ta krijojmë
      t->son = create_tree(value);
      return t->son;
    }
}

Kështu e ndërtuam pemën.

P.S. kjo është artikulli im i parë, prandaj ju lutem mos e gjykoni ashpër

Burimi: habr.com