🥇 Kev pom dav dav ntawm tsob ntoo, kev siv thiab lwm yam

Ntau tus neeg zaum sim nrhiav cov ntoo siv dav dav, tab sis lub tshuab tshawb nrhiav pom tsuas yog binary sawv daws yuav ... Binary nrhiav ntoo, binary ntoo traversal thiab ntau lwm yam algorithms.
Yog, qhov tseeb, tsob ntoo dav dav tsis siv nyob qhov twg, txoj kev hla qeeb qeeb, kev siv me me.

Yog li, kuv nug kuv tus kheej lo lus nug no thiab tam sim no kuv yuav piav qhia yuav ua li cas tsob ntoo tsim. Yog li, qhov zoo tshaj plaws, cov qauv ntoo dav dav yuav tsum khaws peb qhov sib txawv:

taw tes rau tus tub hlob
taw tes rau kwv tij
cov ntaub ntawv koj yuav khaws cia

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

Cia peb tshaj tawm tus taw tes rau lub vertex:

Node *tree = NULL;

Peb yuav tsum pom zoo ua ntej yuav nkag mus rau vertices; qhov no tsis yog tsob ntoo binary, thiab txhua qhov vertex tuaj yeem muaj ntau tus menyuam raws li qhov xav tau.

+ 2 (los yog + ssbb 2) - nkag rau hauv tsob ntoo (rau tsob ntoo dav dav, txoj hauv kev yog muab los ntawm kab, qhov twg r yog kev tsim cov hauv paus, s yog kev hloov mus rau tus tub hlob, b yog kev hloov mus rau tus kwv);

Cia kuv muab piv txwv rau koj:

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

Qhov tshwm sim yuav yog tsob ntoo zoo li no:

Ua ntej, cia peb tsim ib qho kev ua haujlwm uas ntxiv ib qho vertex, uas yog, faib lub cim xeeb rau lub vertex thiab hla tus taw tes rau qhov vertex (thaum pib tsis txuas nrog dab tsi).

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

Koj kuj yuav tsum tsim kom muaj kev ua haujlwm uas tswj txoj hlua txoj hlua (+bs...). Txhua lub sij hawm peb pib traversal los ntawm lub hauv paus, yog hais tias nws tsis yog tsim, ces peb tso tawm NULL (peb tsis ua dab tsi). Yog tias tsis muaj vertex, ces peb yuav tsum tsim nws. Peb mus rau qhov tsim tsob ntoo muaj nuj nqi thiab tau txais tus taw tes rau hauv paus.

Nco ntsoov tias Node ** tsob ntoo hla tus qauv, tsis luam nws. Qhov no ua rau peb muaj peev xwm hloov tej yam uas peb tsis tuaj yeem ua nrog Node * tsob ntoo tshaj tawm.

Feem ntau, peb yuav tsum nrhiav tus taw tes rau lub vertex uas peb xav tau ntxiv tus tub:

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

Nov yog peb ua ib tsob ntoo.

P.S. kuv thawj tsab ntawv, yog li thov tsis txhob txiav txim hnyav dhau

Tau qhov twg los: www.hab.com

Kev pom dav dav ntawm tsob ntoo, kev siv thiab lwm yam

Ntxiv ib saib Отменить ответ