Bendras medžio vaizdas, įgyvendinimas ir kt

Tikriausiai daugelis bandė rasti bendrą medžio konstrukciją, bet paieškos sistema rado tik dvejetainius... Dvejetainis paieškos medis, dvejetainio medžio traversal ir daug kitų algoritmų.
Taip, tikrai, bendras medis niekur nenaudojamas, perėjimas lėtas, panaudojimo atvejų mažai.

Taigi, aš uždaviau sau šį klausimą ir dabar paaiškinsiu, kaip pastatytas medis. Taigi, idealiu atveju, bendroji medžio struktūra turėtų saugoti tris kintamuosius:

• rodyklė į vyriausią sūnų
• rodyklę į brolį
• duomenis, kuriuos ketinate saugoti

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

Paskelbkime rodyklę į viršūnę:

Node *tree = NULL;

Turime iš anksto susitarti, kaip įvesti viršūnes; tai nėra dvejetainis medis, ir kiekviena viršūnė gali turėti tiek vaikų, kiek nori.

• + 2 (arba +ssbb 2) - įterpimas į medį (bendrajam medžiui kelią nurodo linija, kur r yra šaknies sukūrimas, s yra perėjimas prie vyriausiojo sūnaus, b yra perėjimas į brolis);

Pateiksiu pavyzdį:

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

Rezultatas bus toks medis:

1
  2
    5
  3
    6
    7
  3

Pirma, sukurkime funkciją, kuri prideda viršūnę, ty paskiria viršūnei atmintį ir perduoda žymeklį šiai viršūnei (iš pradžių su niekuo nesusijusiai).

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

Taip pat turite sukurti funkciją, kuri apdorotų kelio eilutę (+bs...). Kiekvieną kartą, kai pradedame perėjimą nuo šaknies, jei jis nesukuriamas, išvedame NULL (nieko negalime padaryti). Jei viršūnės nėra, turime ją sukurti. Einame į funkciją sukurti medį ir gauname žymeklį į šaknį.

Atminkite, kad Node** medis perduoda struktūrą, o ne jos kopijuoja. Tai suteikia mums galimybę pakeisti dalykus, kurių negalime padaryti naudodami Mazgo *medžio deklaraciją.

Apskritai, turime rasti rodyklę į viršūnę, prie kurios turime pridėti sūnų:

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

Taip statome medį.

P.S. mano pirmasis straipsnis, todėl prašau nesmerkti per griežtai

Šaltinis: www.habr.com