algorithm
деревья

замечания

Вступление

Деревья являются подтипом более общей структуры данных графа узлов.

Чтобы быть деревом, граф должен удовлетворять двум требованиям:

• Он ацикличен. Он не содержит циклов (или «циклов»).
• Это связано. Для любого заданного узла в графе каждый узел доступен. Все узлы доступны по одному пути на графике.

Структура данных дерева довольно распространена в информатике. Деревья используются для моделирования многих различных алгоритмических структур данных, таких как обычные двоичные деревья, красно-черные деревья, B-деревья, AB-деревья, 23-деревья, кучи и попытки.

обычно упоминается Дерево как Rooted Tree :

choosing 1 cell to be called `Root`
painting the `Root` at the top
creating lower layer for each cell in the graph depending on their distance from the root -the bigger the distance, the lower the cells (example above)

общий символ для деревьев: T

Типичное представление о древесном дереве

Обычно мы представляем анарное дерево (одно с потенциально неограниченными дочерними элементами на узел) как бинарное дерево (одно с ровно двумя детьми на узел). «Следующий» ребенок считается братом. Обратите внимание: если дерево двоично, это представление создает дополнительные узлы.

Затем мы перебираем братьев и сестер и рекурсируем детей. Поскольку большинство деревьев относительно мелкие - много детей, но только несколько уровней иерархии, это приводит к эффективному коду. Обратите внимание, что генеалогия человека является исключением (множество уровней предков, всего несколько детей на уровень).

При необходимости можно сохранить обратные указатели, чтобы дерево могло быть поднято. Их более сложно поддерживать.

Обратите внимание, что типично иметь одну функцию для вызова корня и рекурсивную функцию с дополнительными параметрами, в данном случае глубиной дерева.

  struct node
  {
     struct node *next;
     struct node *child;
     std::string data;
  }

  void printtree_r(struct node *node, int depth)
  {
     int i;

     while(node)
     {
         if(node->child)
         {
            for(i=0;i<depth*3;i++)
                printf(" ");
            printf("{\n"):
            printtree_r(node->child, depth +1);
            for(i=0;i<depth*3;i++)
                printf(" ");
            printf("{\n"):
    
            for(i=0;i<depth*3;i++)
               printf(" ");
             printf("%s\n", node->data.c_str());

             node = node->next;
          }
      }
  }

  void printtree(node *root)
  {
     printree_r(root, 0);
  }

Чтобы проверить, являются ли два двоичных дерева одинаковыми или нет

1. Например, если входы:

Пример: 1

а)

б)

Результат должен быть правдой.

Пример: 2

Если входы:

а)

б)

Результат должен быть ложным.

Псевдокод для этого же:

boolean sameTree(node root1, node root2){

if(root1 == NULL && root2 == NULL)
return true;

if(root1 == NULL || root2 == NULL)
return false;

if(root1->data == root2->data 
     && sameTree(root1->left,root2->left)
        && sameTree(root1->right, root2->right))
return true;

}