Обход двоичного дерева
Обход дерева в глубину
В отличие от линейных структур типа односвязного списка и массива, у которых есть каноничный, прямой способ обхода, деревья можно обходить несколькими способами, в зависимости от поставленной задачи. Начиная с корня, можно применять необходимое действия (именуемое в дальнейшем "визит") как к самому узлу, так и к его левой или правой ветви. Порядок, в котором операции применяются, и будет определять способ обхода.
Наиболее простыми и понятными являются рекурсивные алгоритмы. При сведении к итеративному алгоритму, так как дерево предполагает несколько путей обхода, часть узлов придётся "откладывать" для дальнейшей обработки, для чего будут использоваться стек или очередь.
Существует три основных способа обхода в глубину.
- Прямой (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, только задом наперёд.
Обход бесконечных деревьев
Бывают ситуации, когда необходимо обработать бесконечное дерево. Дерево может генерироваться, когда мы обращаемся к нему (например, мы обходим сайт, страницы которого генерируются сервером во время обращения), либо его размер просто не известен (и возможно велик).
Если дерево растёт бесконечно в глубину, то его можно обрабатывать, используя проход в ширину. То есть, известно, что если спускаться вниз по ветви, то до конца мы не дойдём, но на данном уровне дерево имеет конечный размер.
Если дерево растёт бесконечно в ширину, но при этом имеет конечную глубину (то есть, у узла не два наследника, а из бесконечно много), то можно использовать поиск в глубину.
Обработку бесконечного дерева можно заканчивать например, когда обработано достаточно большое количество узлов или их значения достигли какой-то величины.
Пусть робот "шмугл" индексирует страницы на сайте. Количество ссылок на странице конечно. (т.к. страница конечна). То есть можно рассматривать страницы как узел, ссылки с которой ведут к другим узлам. Конечно, есть ссылки, которые ведут на предыдущие страницы, есть кросс-ссылки между страницами на одном уровне вложенности и т.д., сейчас всех тонкостей рассматривать не будем. То есть, есть дерево, у каждого узла которого конечное число наследников. В лучшем случае количество ссылок конечно и охватывает весь сайт. Однако, может попасться страница, на которой есть календарь, ссылки с которого генерируются автоматически. Программист забыл, что ссылки в будущее надо запретить, поэтому в глубину мы получаем бесконечно дерево, каждый новый узел которого генерируется автоматически. Обход этого дерева закончится, например, когда будет забит канал или превышен лимит по ссылкам.
