ProHoster > Blog > ахбори интернет > Намоиши умумии дарахт, татбиқ ва ғайра

Намоиши умумии дарахт, татбиқ ва ғайра

Эҳтимол бисёр одамон кӯшиш карданд, ки сохтори умумии дарахтро пайдо кунанд, аммо системаи ҷустуҷӯӣ танҳо дуӣ пайдо кард... Дарахти ҷустуҷӯи дуӣ, гузариши дарахти бинарӣ ва бисёр алгоритмҳои дигар.
Бале, дар хакикат, дарахти умумй дар ягон чо истифода намебарад, харакат суст, ходисахои истифодабарй каманд.

Инак, ман ин саволро ба худ додам ва ҳоло ман мефаҳмонам, ки дарахт чӣ гуна сохта мешавад. Ҳамин тавр, идеалӣ, сохтори умумии дарахт бояд се тағирёбандаро нигоҳ дорад:

  • ишора ба писари калонӣ
  • ишора ба бародар
  • маълумоте, ки шумо захира кардан мехоҳед 

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

Биёед ишоракунакро ба қулла эълон кунем:

Node *tree = NULL;

Мо бояд пешакӣ мувофиқа кунем, ки чӣ тавр ба қуллаҳо ворид карда шавад; ин дарахти бинарӣ нест ва ҳар як қулла метавонад ба қадри дилхоҳ кӯдак дошта бошад.

  • + 2 (ё +ssbb 2) - ворид кардан ба дарахт (барои дарахти умумӣ, роҳ тавассути хат дода мешавад, ки дар он r эҷоди реша, s гузариш ба писари калонӣ, b гузариш ба бародар);

Ман як мисол меорам: 

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

Дар натиҷа дарахт чунин хоҳад буд: 

1
  2
    5
  3
    6
    7
  3

Аввалан, биёед функсияеро созем, ки қулларо илова мекунад, яъне хотираро барои қулла ҷудо мекунад ва нишондодро ба ин қулла мегузаронад (аввал ба ҳеҷ чиз пайваст набуд).

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

Шумо инчунин бояд функсияеро созед, ки сатри роҳро идора мекунад (+bs...). Ҳар дафъае, ки мо гузаришро аз реша оғоз мекунем, агар он сохта нашавад, мо NULL-ро мебарорем (мо ҳеҷ кор карда наметавонем). Агар вертекс вуҷуд надошта бошад, пас мо бояд онро эҷод кунем. Мо ба функсияи сохтани дарахт меравем ва ба реша ишоракунанда мегирем.

Дар хотир доред, ки Node**tree аз сохтор мегузарад, на нусхабардорӣ. Ин ба мо имкон медиҳад, ки чизҳоеро тағир диҳем, ки мо бо эъломияи Node * Tree карда наметавонем.

Умуман, мо бояд як нишондодеро ба қуллае пайдо кунем, ки ба он писарро илова кардан лозим аст:

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

Ҳамин тавр мо дарахт месозем.

PS ин мақолаи аввалини ман аст, аз ин рӯ лутфан ба таври дағалӣ доварӣ накунед

Манбаъ: will.com

Илова Эзоҳ