Vaaiga lautele o le laau, faʻatinoga ma isi mea

E toʻatele tagata atonu na taumafai e suʻe se fausiaina o laʻau lautele, ae na maua e le masini suʻesuʻe naʻo le binary ... Binary search tree, binary tree traversal ma le tele o isi algorithms.
Ioe, ioe, o le laau lautele e le faʻaaogaina i soʻo se mea, o le taʻavale e telegese, o mea faʻaoga e laiti.

O lea la, sa ou fesili ifo ia te aʻu lava i lenei fesili ma o lea o le a ou faʻamatalaina pe faʻapefea ona fausia le laau. O lea la, i le tulaga lelei, o se fausaga lautele e tatau ona teuina ni fesuiaiga se tolu:

• faasino i le atalii matua
• faasino i le uso
• fa'amaumauga o le a e teuina

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

Sei o tatou faailoa atu se faasinoala i le tumutumu:

Node *tree = NULL;

E tatau ona tatou malilie muamua pe faʻapefea ona ulu i luga ole laʻau; e le o se laʻau binary, ma e mafai e pito taʻitasi ona maua le tele o tamaiti e manaʻo ai.

• + 2 (poʻo +ssbb 2) - faʻaofi i totonu o se laau (mo se laau lautele, o le ala e tuʻuina atu e le laina, lea r o le fatuina o se aʻa, s o se suiga i le ulumatua, b o se suiga i le se uso);

Sei ou tuuina atu se faataitaiga:

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

O le taunuuga o se laau e pei o lenei:

1
  2
    5
  3
    6
    7
  3

Muamua, se'i o tatou faia se galuega e fa'aopoopoina ai se vertex, o lona uiga, tu'u le manatua mo le pito ma pasi atu se fa'asino ile pito lea (muamua e le'i feso'ota'i i se mea).

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

E te manaʻomia foʻi le fatuina o se galuega e faʻatautaia le manoa ala (+bs...). O taimi uma tatou te amataina ai le taʻavale mai le aʻa, pe a le faia, ona tatou faʻaalia lea o le NULL (e le mafai ona tatou faia se mea). Afai e leai se vertex, ona tatau lea ona tatou fatuina. Matou te o atu i le galuega o le fatu laau ma aumai se faasinoala i le a'a.

Manatua o Node** laau o loʻo pasia le fausaga, ae le o le kopiina. E maua ai e i tatou le tomai e sui ai mea e le mafai ona tatou faia i le Node * ta'utinoga laau.

I se tulaga lautele, e tatau ona tatou maua se faasinoala i le tumutumu lea tatou te manaomia e faaopoopo i ai le atalii:

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

O le ala lea tatou te fausia ai se laau.

P.S. la'u tala muamua, faamolemole aua le soona faamasino

puna: www.habr.com