ProHoster > Блог > interretaj novaĵoj > Ĝenerala vido de la arbo, efektivigo kaj pli

Ĝenerala vido de la arbo, efektivigo kaj pli

Verŝajne multaj homoj provis trovi ĝeneralan arbarkonstruaĵon, sed la serĉilo trovis nur binarajn... Duuman serĉarbon, binaran trapasadon kaj multajn aliajn algoritmojn.
Jes, ja, la ĝenerala arbo ne estas uzata ie, la trapasado estas malrapida, la uzkazoj estas malgrandaj.

Do, mi faris al mi ĉi tiun demandon kaj nun mi klarigos kiel la arbo estas konstruita. Do, ideale, ĝenerala arbstrukturo devus stoki tri variablojn:

  • montrilo al la plej aĝa filo
  • montrilo al frato
  • la datumoj, kiujn vi stokos 

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

Ni deklaru montrilon al la vertico:

Node *tree = NULL;

Ni devas anticipe interkonsenti kiel enigi verticojn; ĉi tio ne estas binara arbo, kaj ĉiu vertico povas havi tiom da infanoj kiom dezirate.

  • + 2 (aŭ +ssbb 2) - enmeto en arbon (por ĝenerala arbo, la vojo estas donita de la linio, kie r estas la kreado de radiko, s estas transiro al la plej aĝa filo, b estas transiro al frato);

Mi donu al vi ekzemplon: 

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

La rezulto estos arbo tia: 

1
  2
    5
  3
    6
    7
  3

Unue, ni kreu funkcion kiu aldonas verticon, nome, asignas memoron por la vertico kaj pasas montrilon al tiu ĉi vertico (komence ne ligita al io ajn).

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

Vi ankaŭ bezonas krei funkcion, kiu pritraktas la padoĉenon (+bs...). Ĉiufoje kiam ni komencas la trapasadon de la radiko, se ĝi ne estas kreita, tiam ni eligas NULL (ni ne povas fari ion ajn). Se ne estas vertico, tiam ni devas krei ĝin. Ni iras al la krea arbo-funkcio kaj ricevas montrilon al la radiko.

Notu, ke Nodo**arbo pasas la strukturon, ne kopias ĝin. Ĉi tio donas al ni la kapablon ŝanĝi aferojn, kiujn ni ne povas fari kun la Node *arba deklaro.

Ĝenerale, ni devas trovi montrilon al la vertico al kiu ni devas aldoni la filon:

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

Jen kiel ni konstruas arbon.

P.S. mia unua artikolo, do bonvolu ne juĝi tro severe

fonto: www.habr.com

Aldoni komenton