🥇Generelt overblik over træet, implementering og mere

Mange mennesker har sikkert forsøgt at finde en generel trækonstruktion, men søgemaskinen fandt kun binære... Binært søgetræ, binært trægennemgang og mange andre algoritmer.
Ja, faktisk, det generelle træ bruges ikke nogen steder, gennemgangen er langsom, brugstilfældene er små.

Så jeg stillede mig selv dette spørgsmål, og nu vil jeg forklare, hvordan træet er bygget. Så ideelt set bør en generel træstruktur gemme tre variable:

pointer til ældste søn
pointer til bror
de data, du vil gemme

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

Lad os erklære en pointer til toppunktet:

Node *tree = NULL;

Vi skal aftale på forhånd, hvordan vi indtaster toppunkter; dette er ikke et binært træ, og hvert hjørne kan have så mange børn som ønsket.

+ 2 (eller +ssbb 2) - indsættelse i et træ (for et generelt træ er stien givet af linjen, hvor r er skabelsen af en rod, s er en overgang til den ældste søn, b er en overgang til en bror);

Lad mig give dig et eksempel:

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

Resultatet bliver et træ som dette:

Lad os først oprette en funktion, der tilføjer et toppunkt, nemlig tildeler hukommelse til toppunktet og sender en pointer til dette toppunkt (i første omgang ikke forbundet med noget).

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

Du skal også oprette en funktion, der håndterer stistrengen (+bs...). Hver gang vi starter traversalen fra roden, hvis den ikke er oprettet, udsender vi NULL (vi kan ikke gøre noget). Hvis der ikke er et toppunkt, så skal vi skabe det. Vi går til funktionen opret træ og får en pointer til roden.

Bemærk, at Node**-træet passerer strukturen, ikke kopierer den. Dette giver os mulighed for at ændre ting, som vi ikke kan gøre med Node *tree-erklæringen.

Generelt skal vi finde en pointer til toppunktet, som vi skal tilføje sønnen til:

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;
    }
}

Sådan bygger vi et træ.

P.S. min første artikel, så vær venlig ikke at dømme for hårdt

Kilde: www.habr.com

Generelt overblik over træet, implementering og mere

Tilføj en kommentar Annuller svar