Вопрос 17: Алгоритм пошагового обхода ДДП. (TRAVERSE)

Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов.

• INFIX_TRAVERSE (tr) — обойти всё дерево, следуя порядку (левое поддерево, вершина, правое поддерево). Элементы по возрастанию

• PREFIX_TRAVERSE (tr) — обойти всё дерево, следуя порядку (вершина, левое поддерево, правое поддерево). Элементы, как в дереве

• POSTFIX_TRAVERSE (tr) — обойти всё дерево, следуя порядку (левое поддерево, правое поддерево', вершина). Элементы в обратном порядке, как в дереве

INFIX_TRAVERSE:

Первая операция — INFIX_TRAVERSE — позволяет обойти все узлы дерева в порядке возрастания ключей и применить к каждому узлу заданную пользователем функцию обратного вызова f, операндом которой является адрес узла. Эта функция обычно работает только с парой (KEY, VALUE), хранящейся в узле. Операция INFIX_TRAVERSE может быть реализована рекурсивным образом: сначала она запускает себя для левого поддерева, потом запускает данную функцию для корня, потом запускает себя для правого поддерева.

Алгоритм:

Если дерево пусто, остановиться.
Иначе
   Рекурсивно обойти левое поддерево Т.
   Применить функцию f к корневому узлу.
   Рекурсивно обойти правое поддерево Т.

Код:

void printInorder(struct node* node)
{
     if (node == nullptr)
          return;

     /* first recur on left child */
     printInorder(node->left);

     /* then print the data of node */
     std::cout << node->data;

     /* now recur on right child */
     printInorder(node->right);
}

POSTFIX_TRAVERSE:

Алгоритм:

Если дерево пусто, остановиться.
Иначе
   Рекурсивно обойти левое поддерево Т.
   Рекурсивно обойти правое поддерево Т.
   Применить функцию f к корневому узлу.

Код:

void printPostorder(struct node* node)
{
     if (node == nullptr)
        return;

     // first recur on left subtree
     printPostorder(node->left);

     // then recur on right subtree
     printPostorder(node->right);

     // now deal with the node
     std::cout << node->data;
}

PREFIX_TRAVERSE:

Алгоритм:

Если дерево пусто, остановиться.
Иначе
   Применить функцию f к корневому узлу.
   Рекурсивно обойти левое поддерево Т.
   Рекурсивно обойти правое поддерево Т.

Код:

void printPreorder(struct node* node)
{
     if (node == nullptr)
          return;

     /* first print data of node */
     std::cout << node->data;

     /* then recur on left sutree */
     printPreorder(node->left);

     /* now recur on right subtree */
     printPreorder(node->right);
}