Дарактын жалпы көрүнүшү, ишке ашыруу жана башкалар

Көптөгөн адамдар, балким, жалпы дарактын курулушун табууга аракет кылышкан, бирок издөө системасы экиликтерди гана тапты ... Бинардык издөө дарагы, экилик дарактарды өтүү жана башка көптөгөн алгоритмдер.
Ооба, чынында эле, жалпы дарак эч жерде колдонулбайт, өтүү жай, колдонуу учурлары чектелүү.

Ошентип, мен өзүмө ушул суроону бердим жана азыр дарактын кантип курулганын түшүндүрөм. Демек, идеалдуу түрдө, жалпы дарактын түзүмү үч өзгөрмөлөрдү сактоо керек:

• улуу уулуна көрсөткүч
• бир тууганга көрсөткүч
• сиз сактай турган маалыматтар

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

Келгиле, чокуга көрсөткүч жарыялайлы:

Node *tree = NULL;

Биз түйүндөргө кантип кирүүнү алдын ала макулдашышыбыз керек, анткени бул бинардык дарак эмес жана ар бир түйүндөн каалаган сандагы уулдары болушу мүмкүн.

• + 2 (же +ssbb 2) — даракка киргизүү (жалпы дарак үчүн жол жип менен белгиленет, мында r тамырды түзөт, s - улуу уулга өтүү, б - бир тууганга өтүү);

Мен бир мисал келтирейин:

+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 * дарак декларациясы менен мүмкүн эмес.

Жалпысынан, биз уулун кошуу керек болгон чокусуна көрсөткүчтү табышыбыз керек:

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

Биз даракты ушинтип курабыз.

P.S. Бул менин биринчи макалам, андыктан мени катуу айыптабаңыз.

Source: www.habr.com