Generell oversikt over treet, implementering og mer

Mange prøvde nok å finne en generell trekonstruksjon, men søkemotoren fant bare binære... Binært søketre, binært treovergang og mange andre algoritmer.
Ja, faktisk, det generelle treet brukes ikke noe sted, gjennomgangen er treg, brukstilfellene er små.

Så jeg stilte meg selv dette spørsmålet, og nå vil jeg forklare hvordan treet er bygget. Så ideelt sett bør en generell trestruktur lagre tre variabler:

• peker på eldste sønn
• peker til bror
• dataene du skal lagre

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

La oss erklære en peker til toppunktet:

Node *tree = NULL;

Vi må avtale på forhånd hvordan vi legger inn toppunkter, dette er ikke et binært tre, og hvert toppunkt kan ha så mange barn som ønskelig.

• + 2 (eller +ssbb 2) - innsetting i et tre (for et generelt tre er banen gitt av linjen, der r er opprettelsen av en rot, s er en overgang til den eldste sønnen, b er en overgang til en bror);

La meg gi deg et eksempel:

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

Resultatet blir et tre som dette:

1
  2
    5
  3
    6
    7
  3

Først, la oss lage en funksjon som legger til et toppunkt, nemlig tildeler minne for toppunktet og sender en peker til dette toppunktet (i utgangspunktet ikke koblet til noe).

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

Du må også lage en funksjon som håndterer banestrengen (+bs...). Hver gang vi starter traverseringen fra roten, hvis den ikke er opprettet, sender vi ut NULL (vi kan ikke gjøre noe). Hvis det ikke er noe toppunkt, må vi lage det. Vi går til create tree-funksjonen og får en peker til roten.

Legg merke til at Node**treet passerer strukturen, ikke kopierer den. Dette gir oss muligheten til å endre ting som vi ikke kan gjøre med Node *tree-erklæringen.

Generelt må vi finne en peker til toppunktet som vi må legge 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;
    }
}

Slik bygger vi et tre.

P.S. min første artikkel, så vær så snill å ikke døm for hardt

Kilde: www.habr.com