View jeneral nan pye bwa a, aplikasyon ak plis ankò

Anpil moun pwobableman te eseye jwenn yon konstriksyon pyebwa jeneral, men motè rechèch la te jwenn sèlman binè yo... Binè rechèch pye bwa, binè pye bwa traversal ak anpil lòt algoritm.
Wi, tout bon, pye bwa jeneral la pa itilize nenpòt kote, traversal la ralanti, ka itilize yo piti.

Se konsa, mwen te poze tèt mwen kesyon sa a epi kounye a mwen pral eksplike ki jan pye bwa a se bati. Se konsa, depreferans, yon estrikti pyebwa jeneral ta dwe estoke twa varyab:

• konsèy sou pi gran pitit gason
• konsèy sou frè
• done ou pral estoke yo

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

Ann deklare yon konsèy sou somè a:

Node *tree = NULL;

Nou dwe dakò davans kijan pou antre nan somè; sa a se pa yon pye bwa binè, epi chak somè ka gen anpil pitit jan yo vle.

• + 2 (oswa +ssbb 2) - ensèsyon nan yon pye bwa (pou yon pye bwa jeneral, chemen an bay pa liy lan, kote r se kreyasyon yon rasin, s se yon tranzisyon nan pi gran pitit gason an, b se yon tranzisyon nan yon frè);

Kite m 'ba ou yon egzanp:

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

Rezilta a pral yon pye bwa tankou sa a:

1
  2
    5
  3
    6
    7
  3

Premyèman, se pou yo kreye yon fonksyon ki ajoute yon somè, sètadi, asiyen memwa pou somè a epi pase yon konsèy sou somè sa a (okòmansman pa konekte ak anyen).

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

Ou bezwen tou kreye yon fonksyon ki okipe kòd chemen an (+bs...). Chak fwa nou kòmanse traversal la soti nan rasin lan, si li pa kreye, Lè sa a, nou soti NULL (nou pa ka fè anyen). Si pa gen okenn somè, Lè sa a, nou dwe kreye li. Nou ale nan fonksyon kreye pyebwa epi jwenn yon konsèy sou rasin lan.

Remake byen ke Node**tree ap pase estrikti a, pa kopye li. Sa a ban nou kapasite pou chanje bagay ke nou pa ka fè ak deklarasyon an Node *tree.

An jeneral, nou dwe jwenn yon konsèy sou somè a kote nou bezwen ajoute pitit gason an:

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

Men ki jan nou bati yon pye bwa.

P.S. premye atik mwen an, donk tanpri pa jije twò sevè

Sous: www.habr.com