🥇Algemene oorsig van die boom, implementering en meer

Baie mense het waarskynlik probeer om 'n algemene boomkonstruksie te vind, maar die soekenjin het slegs binêre gevind ... Binêre soekboom, binêre boomoorgang en baie ander algoritmes.
Ja, inderdaad, die algemene boom word nêrens gebruik nie, die deurkruising is stadig, die gebruiksgevalle is klein.

So, ek het myself hierdie vraag gevra en nou sal ek verduidelik hoe die boom gebou is. Dus, ideaal gesproke, moet 'n algemene boomstruktuur drie veranderlikes stoor:

wyser na oudste seun
wyser na broer
die data wat jy gaan stoor

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

Kom ons verklaar 'n wyser na die hoekpunt:

Node *tree = NULL;

Ons moet vooraf ooreenkom hoe om hoekpunte in te voer; dit is nie 'n binêre boom nie, en elke hoekpunt kan soveel kinders hê as wat jy wil.

+ 2 (of +ssbb 2) - invoeging in 'n boom (vir 'n algemene boom word die pad deur die lyn gegee, waar r die skepping van 'n wortel is, s 'n oorgang na die oudste seun is, b 'n oorgang na 'n broer);

Kom ek gee vir jou 'n voorbeeld:

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

Die resultaat sal 'n boom soos hierdie wees:

Eerstens, kom ons skep 'n funksie wat 'n hoekpunt byvoeg, naamlik om geheue vir die hoekpunt toe te ken en 'n wyser na hierdie hoekpunt deur te gee (aanvanklik nie aan enigiets gekoppel nie).

Node *create_tree(int v) {
  Node *Tree = (Node *) malloc(sizeof(Node));
  Tree->key = v;
  //обнуляем указатели к братьям и сыновьям, независимая вершина, которая хранит value
  Tree->son = NULL;
  Tree->brother = NULL;
  return Tree;
}

Jy moet ook 'n funksie skep wat die padstring (+bs...) hanteer. Elke keer as ons die deurkruising vanaf die wortel begin, as dit nie geskep is nie, voer ons NULL uit (ons kan niks doen nie). As daar geen hoekpunt is nie, dan moet ons dit skep. Ons gaan na die skep boom-funksie en kry 'n wyser na die wortel.

Let daarop dat Node** tree die struktuur verbygaan, nie kopieer dit nie. Dit gee ons die vermoë om dinge te verander wat ons nie met die Node *tree-verklaring kan doen nie.

Oor die algemeen moet ons 'n wyser vind na die hoekpunt waarby ons die seun moet byvoeg:

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); // создаем корень
            t = *tree;
            return *tree;
          }
        if (a[i] == 's') {
          if (t = to_son(t)) // функция, которая возвращает указатель на сына
            continue;
          return NULL; //иначе NULL
        }
        if (a[i] == 'b') {
          if (t = to_brother(t)) //возвращает указатель на брата t 
            continue;
          return NULL;
        }
    }
    if (t->son != NULL) {
    t = last_son(t); // мы перешли к вершине, к которой хотели 
   //и теперь идем к последнему ее сыну,
   //чтобы добавить в конец списка
    t->brother = create_tree(value);
    return t->brother;
    }
    else {//если сына нет, то создадим его
      t->son = create_tree(value);
      return t->son;
    }
}

Dit is hoe ons 'n boom bou.

P.S. my eerste artikel, so moet asseblief nie te hard oordeel nie

Bron: will.com

Algemene aansig van die boom, implementering en meer

Voeg 'n opmerking Kanselleer antwoord