ПроХостер > блог > интернет вести > Општи поглед на стабло, имплементација и још много тога

Општи поглед на стабло, имплементација и још много тога

Многи људи су вероватно покушавали да пронађу општу конструкцију стабла, али претраживач је пронашао само бинарне... Бинарно стабло претраге, бинарно стабло преласка и многе друге алгоритме.
Да, заиста, опште дрво се нигде не користи, прелазак је спор, случајеви употребе су мали.

Дакле, поставио сам себи ово питање и сада ћу објаснити како се гради дрво. Дакле, идеално, општа структура стабла треба да чува три варијабле:

  • показивач на најстаријег сина
  • показивач на брата
  • податке које ћете сачувати 

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

Хајде да декларишемо показивач на врх:

Node *tree = NULL;

Морамо се унапред договорити како да унесемо врхове; ово није бинарно стабло и сваки врх може имати онолико деце колико жели.

  • + 2 (или +ссбб 2) - уметање у дрво (за опште дрво, путања је дата линијом, где је р стварање корена, с је прелаз на најстаријег сина, б је прелаз на брат);

даћу пример: 

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

Такође морате да креирате функцију која рукује низом путање (+бс...). Сваки пут када започнемо обилазак из корена, ако није креиран, онда излазимо НУЛЛ (не можемо ништа да урадимо). Ако не постоји врх, онда га морамо креирати. Идемо до функције креирања стабла и добијамо показивач на корен.

Имајте на уму да Ноде**стабло прослеђује структуру, а не копира је. Ово нам даје могућност да променимо ствари које не можемо да урадимо са Ноде *стабло декларацијом.

Уопштено говорећи, морамо пронаћи показивач на врх коме треба да додамо сина:

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

Овако градимо дрво.

П.С. мој први чланак, па вас молим да не судите престрого

Извор: ввв.хабр.цом

Додај коментар