ProHoster > Blogi > internetiuudised > Üldvaade puust, teostus ja palju muud

Üldvaade puust, teostus ja palju muud

Tõenäoliselt üritasid paljud leida üldist puukonstruktsiooni, kuid otsingumootor leidis ainult kahendarvulisi... Binaarne otsingupuu, kahendpuu läbimine ja palju muid algoritme.
Jah, tõepoolest, üldpuud ei kasutata kuskil, läbimine on aeglane, kasutusjuhtumeid on vähe.

Niisiis, esitasin endale selle küsimuse ja nüüd selgitan, kuidas puu on ehitatud. Nii et ideaaljuhul peaks üldine puustruktuur salvestama kolm muutujat:

  • osuti vanemale pojale
  • osuti vennale
  • andmed, mida kavatsete salvestada 

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

Deklareerime tipule osuti:

Node *tree = NULL;

Peame eelnevalt kokku leppima, kuidas tippe sisestada; see ei ole kahendpuu ja igal tipul võib olla nii palju lapsi, kui soovite.

  • + 2 (või +ssbb 2) - puusse sisestamine (üldpuu puhul annab tee joon, kus r on juure loomine, s on üleminek vanimale pojale, b on üleminek vend);

Lubage mul tuua teile näide: 

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

Tulemuseks on selline puu: 

1
  2
    5
  3
    6
    7
  3

Kõigepealt loome funktsiooni, mis lisab tipu, nimelt eraldab tipule mälu ja annab sellele tipule (esialgu mitte millegagi ühendatud) kursori.

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

Samuti peate looma funktsiooni, mis käsitleb tee stringi (+bs...). Iga kord, kui alustame läbimist juurest, kui seda ei looda, siis väljastame NULL (me ei saa midagi teha). Kui tippu pole, siis peame selle looma. Läheme puu loomise funktsiooni juurde ja saame kursorit juurele.

Pange tähele, et sõlme**puu läbib struktuuri, mitte ei kopeeri seda. See annab meile võimaluse muuta asju, mida me ei saa teha sõlme *puu deklaratsiooniga.

Üldiselt peame leidma osuti tipule, millele peame poja lisama:

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

Nii ehitame puu.

P.S. minu esimene artikkel, nii et palun ärge otsustage liiga karmilt

Allikas: www.habr.com

Lisa kommentaar