Zuhaitzaren ikuspegi orokorra, ezarpena eta gehiago

Jende askok zuhaitz-eraikuntza orokor bat aurkitzen saiatu da ziurrenik, baina bilatzaileak bitarrak baino ez ditu aurkitu... Bilaketa-zuhaitz bitarra, zuhaitz bitarren zeharkaldia eta beste hainbat algoritmo.
Bai, izan ere, zuhaitz orokorra ez da inon erabiltzen, zeharkaldia motela da eta erabilera kasuak mugatuak dira.

Beraz, galdera hau egin nion neure buruari eta orain azalduko dut nola eraikitzen den zuhaitz bat. Idealki, zuhaitz-egitura orokor batek hiru aldagai gorde beharko lituzke:

• seme zaharrenaren erakuslea
• anaiaren erakuslea
• gordetzeko asmoa dituzun datuak

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

Deklara dezagun erpinerako erakusle bat:

Node *tree = NULL;

Aldez aurretik adostu behar dugu nodoak nola sartu, hau ez baita zuhaitz bitar bat, eta nodo bakoitzak nahi adina seme izan ditzakeelako.

• + 2 (edo +ssbb 2) — zuhaitz batean txertatzea (zuhaitz orokor batentzat, bidea kate batez zehazten da, non r-k erroa sortzen duen, s seme zaharrenerako trantsizioa den, b anaiarenerako trantsizioa den);

Adibide bat emango dizuet:

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

Emaitza honelako zuhaitz bat izango da:

1
  2
    5
  3
    6
    7
  3

Hasteko, erpin bat gehitzen duen funtzio bat sortuko dugu, hau da, erpinerako memoria esleituko du eta erpin horretara erakusle bat pasako du (hasieran ezeri lotuta ez dagoena).

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

Bide-katea (+bs…) prozesatzen duen funtzio bat ere sortu behar dugu. Aldi bakoitzean, errotik hasten gara zeharkatzen. Sortu ez bada, NULL irteera ematen dugu (ezin dugu ezer egin). Nodoa ez bada existitzen, sortu behar dugu. Ondoren, create tree funtzioa deitzen dugu eta errorako erakusle bat lortzen dugu.

Kontuan izan Node *tree-k egitura pasatzen duela, kopiatu beharrean. Horri esker, aldatu dezakegu, baina hori ezinezkoa da Node *tree deklarazioarekin.

Oro har, semea gehitu behar diogun erpinera erakusle bat aurkitu behar dugu:

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

Honela eraikitzen dugu zuhaitz bat.

P.S. Hau nire lehen artikulua da, beraz, mesedez, ez epaitu gogorregi.

Iturria: www.habr.com