Umbono ojwayelekile wesihlahla, ukuqaliswa nokunye

Abantu abaningi cishe bazama ukuthola ukwakhiwa kwesihlahla okujwayelekile, kodwa injini yokusesha ithole kanambambili kuphela ... Isihlahla sokusesha kanambambili, i-binary tree traversal kanye namanye ama-algorithms amaningi.
Yebo, ngempela, isihlahla esivamile asisetshenziswa noma kuphi, ukuhamba kancane, amacala okusebenzisa amancane.

Ngakho-ke, ngizibuze lo mbuzo futhi manje ngizochaza ukuthi isihlahla sakhiwe kanjani. Ngakho-ke, ngokufanelekile, isakhiwo sesihlahla esijwayelekile kufanele sigcine okuguquguqukayo okuthathu:

• ikhomba indodana endala
• ekhomba umfowethu
• idatha ozoyigcina

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

Ake simemezele i-pointer ku-vertex:

Node *tree = NULL;

Kufanele sivumelane kusenesikhathi ukuthi ifakwa kanjani phezulu; lesi akusona isihlahla kanambambili, futhi i-vertex ngayinye ingaba nezingane eziningi ngendlela ofisa ngayo.

• + 2 (noma +ssbb 2) - ukufakwa esihlahleni (esihlahleni esivamile, indlela inikezwa ngomugqa, lapho r kuwukudalwa kwempande, s kuwukushintshela endodaneni endala, u-b kuwukushintshela ku umfowethu);

Ake ngikunike isibonelo:

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

Umphumela uzoba isihlahla esinjengalesi:

1
  2
    5
  3
    6
    7
  3

Okokuqala, ake sakhe umsebenzi owengeza i-vertex, okungukuthi, ukwaba inkumbulo ku-vertex futhi sidlulise isikhombi kule vertex (ekuqaleni yayingaxhumekile kunoma yini).

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

Udinga futhi ukudala umsebenzi ophethe iyunithi yezinhlamvu zendlela (+bs...). Isikhathi ngasinye lapho siqala ukunqamula kusuka empandeni, uma kungadalwanga, khona-ke sikhipha i-NULL (asikwazi ukwenza lutho). Uma ingekho i-vertex, kufanele siyidale. Siya emsebenzini wokudala wesihlahla bese sithola i-pointer empandeni.

Qaphela ukuthi i-Node**sihlahla sidlula isakhiwo, asisikopishi. Lokhu kusinika amandla okushintsha izinto esingakwazi ukuzenza ngesimemezelo se-Node *tree.

Ngokuvamile, kufanele sithole i-pointer ku-vertex lapho sidinga ukungeza indodana:

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

Sakha kanje isihlahla.

P.S. isihloko sami sokuqala, ngakho ngicela ningahluleli ngokhahlo

Source: www.habr.com