ʻO kaʻike nui o ka lāʻau, ka hoʻokō a me nā mea'ē aʻe

Nui paha ka poʻe i hoʻāʻo e ʻimi i kahi kūkulu lāʻau maʻamau, akā ʻike ka ʻenekini i nā mea binary wale nō ... Binary search tree, binary tree traversal a me nā algorithms ʻē aʻe.
ʻAe, ʻoiaʻiʻo, ʻaʻole hoʻohana ʻia ka lāʻau maʻamau ma nā wahi āpau, lohi ka hele ʻana, liʻiliʻi nā mea hoʻohana.

No laila, ua nīnau au iaʻu iho i kēia nīnau a i kēia manawa e wehewehe au i ke ʻano o ke kūkulu ʻia ʻana o ka lāʻau. No laila, ʻo ka mea kūpono, pono e mālama i kahi ʻano lāʻau maʻamau i ʻekolu mau ʻano:

• kuhikuhi i ke keiki hiapo
• kuhikuhi i ke kaikunane
• ka ʻikepili āu e mālama ai

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

E haʻi aku i kahi kuhikuhi i ka piko:

Node *tree = NULL;

Pono mākou e ʻae mua i ke komo ʻana i nā vertices; ʻaʻole kēia he kumulāʻau binary, a hiki i kēlā me kēia vertex ke loaʻa nā keiki he nui e like me ka makemake.

• + 2 (a i ʻole +ssbb 2) - hoʻokomo i loko o kahi kumulāʻau (no ka lāʻau maʻamau, hāʻawi ʻia ke ala e ka laina, kahi r ka hana ʻana o kahi kumu, s he hoʻololi i ke keiki hiapo, b he hoʻololi i he kaikunane);

E hāʻawi wau i kekahi laʻana:

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

ʻO ka hopena e like me kēia:

1
  2
    5
  3
    6
    7
  3

ʻO ka mea mua, e hana i kahi hana e hoʻohui i kahi vertex, ʻo ia hoʻi, hoʻokaʻawale i ka hoʻomanaʻo no ka vertex a hāʻawi i kahi kuhikuhi i kēia vertex (ʻaʻole pili i kekahi mea).

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

Pono ʻoe e hana i kahi hana e mālama i ke kaula ala (+bs...). I kēlā me kēia manawa mākou e hoʻomaka i ka traversal mai ke kumu, inā ʻaʻole i hana ʻia, a laila hoʻopuka mākou i ka NULL (ʻaʻole hiki iā mākou ke hana i kekahi mea). Inā ʻaʻohe vertex, pono mākou e hana. Hele mākou i ka hana kumu lāʻau a loaʻa kahi kuhikuhi i ke kumu.

E hoʻomaopopo i ka hele ʻana o ka lāʻau Node** i ka hale, ʻaʻole kope ʻia. Hāʻawi kēia iā mākou i ka hiki ke hoʻololi i nā mea hiki ʻole iā mākou ke hana me ka ʻōlelo Node *lāʻau.

Ma keʻano laulā, pono mākou e ʻimi i kahi kuhikuhi i ka vertex kahi e pono ai mākou e hoʻohui i ke keiki:

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

Penei mākou e kūkulu ai i lāʻau.

P.S. kaʻu ʻatikala mua, no laila, mai hoʻohewa ʻino loa

Source: www.habr.com