Обход двоичного дерева
Обход дерева в глубину
В отличие от линейных структур типа односвязного списка и массива, у которых есть каноничный, прямой способ обхода, деревья можно обходить несколькими способами, в зависимости от поставленной задачи. Начиная с корня, можно применять необходимое действия (именуемое в дальнейшем "визит") как к самому узлу, так и к его левой или правой ветви. Порядок, в котором операции применяются, и будет определять способ обхода.
Наиболее простыми и понятными являются рекурсивные алгоритмы. При сведении к итеративному алгоритму, так как дерево предполагает несколько путей обхода, часть узлов придётся "откладывать" для дальнейшей обработки, для чего будут использоваться стек или очередь.
Существует три основных способа обхода в глубину.
- Прямой (pre-order)
Посетить корень
Обойти левое поддерево
Обойти правое поддеревоПрямой обход двоичного дерева - Симметричный или поперечный (in-order)
Обойти левое поддерево
Посетить корень
Обойти правое поддеревоСимметричный обход двоичного дерева - В обратном порядке (post-order)
Обойти левое поддерево
Обойти правое поддерево
Посетить кореньОбратный обход двоичного дерева
Рекурсивное решение полностью соответствует описанию алгоритма
void preOrderTravers(Node* root) { if (root) { printf("%d ", root->data); preOrderTravers(root->left); preOrderTravers(root->right); } } void inOrderTravers(Node* root) { if (root) { inOrderTravers(root->left); printf("%d ", root->data); inOrderTravers(root->right); } } void postOrderTravers(Node* root) { if (root) { postOrderTravers(root->left); postOrderTravers(root->right); printf("%d ", root->data); } }
Переделаем функции, чтобы они могли работать с узлами. Для этого понадобится передавать функцию, которая могла бы работать с узлом и получать дополнительные параметры. Эти параметры будут передаваться указателем типа void. Если нам понадобится передать параметры, всегда можно будет их передать указателем на структуру.
void preOrderTravers(Node* root, void (*visit)(Node*, void*), void *params) { if (root) { visit(root, params); preOrderTravers(root->left, visit, params); preOrderTravers(root->right, visit, params); } } void inOrderTravers(Node* root, void (*visit)(Node*, void*), void *params) { if (root) { inOrderTravers(root->left, visit, params); visit(root, params); inOrderTravers(root->right, visit, params); } } void postOrderTravers(Node* root, void (*visit)(Node*, void*), void *params) { if (root) { postOrderTravers(root->left, visit, params); postOrderTravers(root->right, visit, params); visit(root, params); } }
В качестве функции visit можно передавать, например, такую функцию
void printNode(Node *current, void *args) { printf("%d ", current->data); }
Вызов функции
inOrderTravers(root, printNode, NULL);
Рассмотрим теперь результат каждого из обходов.
inOrderTraversal выводит сначала самый левый узел, потом средний, потом правый. Если слева находилось дерево, то алгоритм применяется к нему рекурсивно. Если мы обрабатываем двоичное дерево поиска, то самым левым будет самый маленький элемент, самым правым и самым последним при обработке будет самый большой элемент. Симметричный обход выведет дерево в отсортированном по возрастанию виде. Для того, чтобы отсортировать дерево в обратном порядке, нужно сначала обработать правую ветвь, то есть функция
void inOrderTraversRL(Node* root) { if (root) { inOrderTraversRL(root->right); printf("%d ", root->data); inOrderTraversRL(root->left); } }
выведет дерево в обратном порядке.
postOrderTraversal выводит узлы слева направо, снизу вверх. Это имеет ряд применений, сейчас рассмотрим только одно – удаление дерева. Обход дерева начинается снизу, с узлов, у которых нет родителей. Их можно безболезненно удалять, так как обращение root->left и root->right происходят до удаления объекта.
void deleteTree(Node **root) { if (*root) { deleteTree(&((*root)->left)); deleteTree(&((*root)->right)); free(*root); } }
Напомню, что если мы хотим изменить указатель, то нужно передавать указатель на указатель.
Итеративная реализация обхода в глубину требует использования стека. Он нужен для того, чтобы "откладывать" на потом обработку некоторых узлов (например тех, у кого есть необработанные наследники, или всех левых улов и т.д.).
Реализовывать стек будем с помощью массива, который при переполнении будет изменять свой размер. Напомню, что реализация стека требует двух функций - push, которая кладёт значение на вершину стека и pop, которая снимает значение с вершины стека и возвращает его. Кроме того, будем использовать функцию peek, которая возвращает значение с вершины, но не удаляет его.
#define STACK_INIT_SIZE 100 typedef struct Stack { size_t size; size_t limit; Node **data; } Stack; Stack* createStack() { Stack *tmp = (Stack*) malloc(sizeof(Stack)); tmp->limit = STACK_INIT_SIZE; tmp->size = 0; tmp->data = (Node**) malloc(tmp->limit * sizeof(Node*)); return tmp; } void freeStack(Stack **s) { free((*s)->data); free(*s); *s = NULL; } void push(Stack *s, Node *item) { if (s->size >= s->limit) { s->limit *= 2; s->data = (Node**) realloc(s->data, s->limit * sizeof(Node*)); } s->data[s->size++] = item; } Node* pop(Stack *s) { if (s->size == 0) { exit(7); } s->size--; return s->data[s->size]; } Node* peek(Stack *s) { return s->data[s->size-1]; }
После того, как у нас готова реализация стека, напишем обходы.
Прямой обход
iterativePreorder(node) parentStack = empty stack while (not parentStack.isEmpty() or node ≠ null) if (node ≠ null) visit(node) parentStack.push(node) node = node.left else node = parentStack.pop() node = node.right
Код на си
void iterPreorder(Node *root) { Stack *ps = createStack(); while (ps->size != 0 || root != NULL) { if (root != NULL) { printf("visited %d\n", root->data); if (root->right) { push(ps, root->right); } root = root->left; } else { root = pop(ps); } } freeStack(&ps); }
Поперечный обход
iterativeInorder(node) parentStack = empty stack while (not parentStack.isEmpty() or node ≠ null) if (node ≠ null) parentStack.push(node) node = node.left else node = parentStack.pop() visit(node) node = node.right
Код на си
void iterInorder(Node *root) { Stack *ps = createStack(); while (ps->size != 0 || root != NULL) { if (root != NULL) { push(ps, root); root = root->left; } else { root = pop(ps); printf("visited %d\n", root->data); root = root->right; } } freeStack(&ps); }
Обратный обход
iterativePostorder(node) parentStack = empty stack lastnodevisited = null while (not parentStack.isEmpty() or node ≠ null) if (node ≠ null) parentStack.push(node) node = node->left else peeknode = parentStack.peek() if (peeknode->right ≠ null and lastnodevisited ≠ peeknode->right) /* if traversing node from left child AND right child exists, move right */ node = peeknode->right else parentStack.pop() visit(peeknode) lastnodevisited = peeknode
Код на си
void iterPostorder(Node *root) { Stack *ps = createStack(); Node *lnp = NULL; Node *peekn = NULL; while (!ps->size == 0 || root != NULL) { if (root) { push(ps, root); root = root->left; } else { peekn = peek(ps); if (peekn->right && lnp != peekn->right) { root = peekn->right; } else { pop(ps); printf("visited %d\n", peekn->data); lnp = peekn; } } } freeStack(&ps); }
Обход в ширину
Обход в ширину подразумевает, что сначала мы посещаем корень, затем, слева направо, все ветви первого уровня, затем все ветви второго уровня и т.д.
Пусть мы находимся в корне дерева. Далее необходимо посетить всех наследников корня. Таким образом, нужно засунуть в контейнер сначала узел, затем его наследников, при этом узел далее должен быть обработан первым. То есть, элемент, который вошёл первым должен быть обработан первым. Это очередь, и в этом примере мы будем использовать готовую реализацию очереди с помощью двусвязного списка.
breadthFirst(root) q = empty queue q.enqueue(root) while not q.empty do node := q.dequeue() visit(node) if node.left ≠ null then q.enqueue(node.left) if node.right ≠ null then q.enqueue(node.right)
Реализация на си
void breadthFirst(Node* root) { DblLinkedList *q = createDblLinkedList(); //Для начала поместим в очередь корень pushBack(q, root); while (q->size != 0) { Node *tmp = (Node*) popFront(q); printf("%d ", tmp->data); //Если есть левый наследник, то помещаем его в очередь для дальнейшей обработки if (tmp->left) { pushBack(q, tmp->left); } //Если есть правый наследник, то помещаем его в очередь для дальнейшей обработки if (tmp->right) { pushBack(q, tmp->right); } } deleteDblLinkedList(&q); }
Заменим очередь на стек
void breadthFirstWakaWaka(Node* root) { DblLinkedList *q = createDblLinkedList(); pushFront(q, root); while (q->size != 0) { Node *tmp = (Node*) popFront(q); printf("%d ", tmp->data); if (tmp->left) { pushFront(q, tmp->left); } if (tmp->right) { pushFront(q, tmp->right); } } deleteDblLinkedList(&q); }
Теперь функция обходит узлы как Post-Order, только задом наперёд.
Обход бесконечных деревьев
Бывают ситуации, когда необходимо обработать бесконечное дерево. Дерево может генерироваться, когда мы обращаемся к нему (например, мы обходим сайт, страницы которого генерируются сервером во время обращения), либо его размер просто не известен (и возможно велик).
Если дерево растёт бесконечно в глубину, то его можно обрабатывать, используя проход в ширину. То есть, известно, что если спускаться вниз по ветви, то до конца мы не дойдём, но на данном уровне дерево имеет конечный размер.
Если дерево растёт бесконечно в ширину, но при этом имеет конечную глубину (то есть, у узла не два наследника, а из бесконечно много), то можно использовать поиск в глубину.
Обработку бесконечного дерева можно заканчивать например, когда обработано достаточно большое количество узлов или их значения достигли какой-то величины.
Пусть робот "шмугл" индексирует страницы на сайте. Количество ссылок на странице конечно. (т.к. страница конечна). То есть можно рассматривать страницы как узел, ссылки с которой ведут к другим узлам. Конечно, есть ссылки, которые ведут на предыдущие страницы, есть кросс-ссылки между страницами на одном уровне вложенности и т.д., сейчас всех тонкостей рассматривать не будем. То есть, есть дерево, у каждого узла которого конечное число наследников. В лучшем случае количество ссылок конечно и охватывает весь сайт. Однако, может попасться страница, на которой есть календарь, ссылки с которого генерируются автоматически. Программист забыл, что ссылки в будущее надо запретить, поэтому в глубину мы получаем бесконечно дерево, каждый новый узел которого генерируется автоматически. Обход этого дерева закончится, например, когда будет забит канал или превышен лимит по ссылкам.
