#algorithm #recursion #data-structures #tree #traversal
#алгоритм #рекурсия #структуры данных #дерево #обход
Вопрос:
Я пытался разработать / найти очень специфический способ обхода древовидной структуры. Я действительно знаком только с 2 ~ 3 наиболее часто используемыми методами обхода дерева, и я не знаю достаточно жаргона для эффективного поиска в Интернете, поэтому, пожалуйста, простите меня, если я спрашиваю что-то очень очевидное или базовое.
У меня есть следующая древовидная структура (не обязательно двоичное дерево):
(источник: renebokhorst.com )
Предположим, я вхожу в дерево в узле «AAA». Я бы хотел, чтобы метод сначала обходил свои базовые узлы, используя метод сверху вниз.
(источник: renebokhorst.com )
Однако после этого я бы хотел, чтобы метод перемещался вверх по дереву и обрабатывал все сверху вниз под ним, КРОМЕ той части, которую он уже сделал до этого.
(источник: renebokhorst.com )
Я хочу, чтобы он продолжал делать это, пока не достигнет верхнего узла и не завершится.
(источник: renebokhorst.com )
Очень специфическим требованием является то, что мы не можем «пропускать» узлы. Вход или возврат в узел должен выполняться либо из его родительского, либо из дочернего узла. Перед входом в узел я также регистрирую, перемещается ли посетитель вверх или вниз по дереву (это необходимая информация для некоторых посетителей). Аналогичным образом я могу также поднять флаги независимо от того, входим ли мы в дерево в первый раз или снова проходим мимо узла входа. Посетитель не может посещать какой-либо узел дважды, за исключением узла входа, который он может проходить несколько раз, пока поднят флаг RE_ENTRY. В идеале я не хочу отслеживать список узлов, которые я уже проходил в прошлом. Теперь я попробовал несколько разных подходов
case GLOBAL_SPREAD:
{
if ( pVisitor->LastVisited == NULL )
pVisitor->VisitDirection = ENTRY;
pVisitor->visit(this);
for ( uint32 i(0) ; i < Children.size() ; i = 1 )
{
pVisitor->VisitDirection = DOWN;
Children[i]->Accept(pVisitor);
}
break;
}
Этот фрагмент кода, конечно, не делает ничего другого, кроме как выполняет обход сверху вниз всего, что находится ниже начального узла. Проблемы возникли, когда я попытался добавить код, который поднимал бы посетителя вверх по дереву и оттуда выполнял обход сверху вниз. Вызов Parent->Accept(pVisitor) перед посещением дочерних элементов, очевидно, не приведет к желаемым результатам. Вызов Parent->Accept(pVisitor) после посещения дочерних элементов приведет к желаемым результатам только в случае узла ввода. Для любого другого узла это вызвало бы проблемы.
Мне было интересно, есть ли у кого-нибудь опыт работы с этими типами методов обхода дерева, и действительно ли у меня достаточно информации для выполнения такого рода обхода вообще. Опять же, важно, чтобы я не отслеживал какие-либо списки ранее посещенных элементов. В лучшем случае я могу отслеживать в самой функции, какой узел был ранее посещен. Возможно, это хорошо известный и широко документированный метод обхода, названия которого я просто не знаю.
Заранее спасибо!
Комментарии:
1. Итак, в основном поиск в глубину, за исключением того, что вы не обязательно начинаете с корневого узла дерева? Похоже, для этого было бы довольно простой модификацией DFS…
2. Получаете ли вы указатель на узел (AAA в примере) и должны работать с деревом, учитывая только этот узел, или вам дан корневой узел и начальное значение, и вы сначала выполняете поиск по дереву для значения, затем выполняете DFS из значения, затем модифицированный DFSдля остальной части дерева? Это важно, потому что, если вам дан только указатель на узел, у вас также должен быть указатель на родительский узел, чтобы иметь возможность возвращаться вверх по дереву (и вы должны решить, является ли родительский узел корневого узла нулевым или сам по себе). Есть ли в узлах поле, которое можно использовать для пометки «посещено»? Насколько велики деревья?
3. Кроме того, что представляет собой «перемещение вверх»? Это когда вы заканчиваете DFS на уровне и вам нужно перейти к родительскому элементу? Если это так, единственными случаями «обхода вверх» будет переход от AAA к AA и от AA к A? Учитывая, что это не обязательно двоичное дерево, как вы представляете узлы на заданном уровне? Несмотря на все эти вопросы, это кажется довольно простым упражнением в обходе дерева. Предположительно, последовательность поиска для начала с ABA такова: ABA, ABAA, ABAB, AB, ABB, ABBA, ABBB, A, AA, AAA, AAAA, AAAB, AAB, AABA, AABB.
4. @wallacer: ваш анализ верен, однако он прерывается вскоре после того, как приходится вносить довольно простую модификацию 🙂
5. @Jonathan: Вам предоставляется только начальный узел. Каждый узел имеет следующие элементы {Родительский элемент; Дочерние элементы Actor[]; void Accept(IVisitor); }. Корень может быть идентифицирован с помощью 3 методов: (1) его родительский элемент равен NULL, (2) он имеет тип «Root : Actor» и может иметь свою собственную реализациюфункция, (3) ее можно получить в любое время с помощью Root::getRoot() . Деревья могут варьироваться от маленьких до огромных. Именно для последнего предела я не хочу сохранять список ранее посещенных узлов. Другая причина заключается в том, что код является лишь небольшой частью процедуры, которая должна выполняться 60 раз в секунду.
Ответ №1:
Этот код, похоже, реализует то, что вы запрашиваете. Ключом к этой работе является то, что посещение первого узла (что бы это ни было) считается UP операцией. Функции print_tree() и print_preorder() реализуют обычный обход дерева в предварительном порядке; они используются, чтобы показать, что структура данных имеет правильную форму. Функции dfs_traversal() и dfs_traverse() реализуют ваш специальный обход DFS. Тестовый код проверяет два конкретных примера (узлы AAA и A ), а затем выполняет исчерпывающую проверку обхода из каждого узла в дереве.
Код
#include <stdio.h>
enum { MAX_CHILD = 2 };
enum { UP = 1, DOWN = 2 };
typedef struct Node Node;
struct Node
{
char name[8];
int number;
Node *parent;
Node *child[MAX_CHILD];
};
static Node data[] =
{
{ "A", 0, 0, { amp;data[ 1], amp;data[ 2], }, },
{ "AA", -3, amp;data[0], { amp;data[ 3], amp;data[ 4], }, },
{ "AB", 3, amp;data[0], { amp;data[ 5], amp;data[ 6], }, },
{ "AAA", -4, amp;data[1], { amp;data[ 7], amp;data[ 8], }, },
{ "AAB", 4, amp;data[1], { amp;data[ 9], amp;data[10], }, },
{ "ABA", -4, amp;data[2], { amp;data[11], amp;data[12], }, },
{ "ABB", 4, amp;data[2], { amp;data[13], amp;data[14], }, },
{ "AAAA", 0, amp;data[3], { 0, 0, }, },
{ "AAAB", 5, amp;data[3], { 0, 0, }, },
{ "AABA", -5, amp;data[4], { 0, 0, }, },
{ "AABB", 5, amp;data[4], { 0, 0, }, },
{ "ABAA", -5, amp;data[5], { 0, 0, }, },
{ "ABAB", 5, amp;data[5], { 0, 0, }, },
{ "ABBA", -5, amp;data[6], { 0, 0, }, },
{ "ABBB", 5, amp;data[6], { 0, 0, }, },
};
enum { NUM_NODES = sizeof(data) / sizeof(data[0]) };
static void visit(Node *node, int up_down)
{
printf("%4s: ", up_down == UP ? "UP" : "DOWN");
printf(" %5s [-] N = %p; P = %pn", node->name, node->number,
(void *)node, (void *)node->parent);
}
static void print_tree(Node *node)
{
if (node != 0)
{
visit(node, DOWN);
for (int i = 0; i < MAX_CHILD; i )
print_tree(node->child[i]);
}
}
static void print_preorder(const char *tag, Node *node)
{
printf("Tree starting from %s:n", tag);
print_tree(node);
}
static void dfs_traverse(int up_down, Node *node, Node *skip)
{
if (node != 0 amp;amp; node != skip)
{
visit(node, up_down);
for (int i = 0; i < MAX_CHILD; i )
dfs_traverse(DOWN, node->child[i], skip);
if (node->parent != 0 amp;amp; up_down == UP)
dfs_traverse(UP, node->parent, node);
}
}
static void dfs_traversal(const char *tag, int up_down, Node *node, Node *skip)
{
printf("DFS starting from %sn", tag);
dfs_traverse(up_down, node, skip);
}
int main(void)
{
Node *aaa = amp;data[3];
Node *root = amp;data[0];
print_preorder("root", root);
print_preorder("aaa", aaa);
dfs_traversal("aaa", UP, aaa, 0);
dfs_traversal("root", UP, root, 0);
for (int i = 0; i < NUM_NODES; i )
dfs_traversal(data[i].name, UP, amp;data[i], 0);
return 0;
}
Пример вывода
Tree starting from root:
DOWN: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
DOWN: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
DOWN: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
DOWN: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
Tree starting from aaa:
DOWN: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
DFS starting from aaa
UP: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
UP: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
DOWN: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
DFS starting from root
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
DOWN: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
DOWN: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
DOWN: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
DFS starting from A
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
DOWN: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
DOWN: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
DOWN: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
DFS starting from AA
UP: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
DOWN: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
DOWN: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
DFS starting from AB
UP: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
DOWN: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
DOWN: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
DFS starting from AAA
UP: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
UP: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
DOWN: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
DFS starting from AAB
UP: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
UP: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
DOWN: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
DFS starting from ABA
UP: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
UP: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
DOWN: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
DFS starting from ABB
UP: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
UP: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
DOWN: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
DFS starting from AAAA
UP: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
UP: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
UP: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
DOWN: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
DFS starting from AAAB
UP: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
UP: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
UP: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
DOWN: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
DFS starting from AABA
UP: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
UP: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
UP: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
DOWN: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
DFS starting from AABB
UP: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
UP: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
UP: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
DOWN: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
DFS starting from ABAA
UP: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
UP: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
UP: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
DOWN: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
DFS starting from ABAB
UP: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
UP: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
UP: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
DOWN: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
DFS starting from ABBA
UP: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
UP: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
UP: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
DOWN: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
DFS starting from ABBB
UP: ABBB [ 5] N = 0x10dbab270; P = 0x10dbab130
UP: ABB [ 4] N = 0x10dbab130; P = 0x10dbab090
DOWN: ABBA [-5] N = 0x10dbab248; P = 0x10dbab130
UP: AB [ 3] N = 0x10dbab090; P = 0x10dbab040
DOWN: ABA [-4] N = 0x10dbab108; P = 0x10dbab090
DOWN: ABAA [-5] N = 0x10dbab1f8; P = 0x10dbab108
DOWN: ABAB [ 5] N = 0x10dbab220; P = 0x10dbab108
UP: A [ 0] N = 0x10dbab040; P = 0x0
DOWN: AA [-3] N = 0x10dbab068; P = 0x10dbab040
DOWN: AAA [-4] N = 0x10dbab0b8; P = 0x10dbab068
DOWN: AAAA [ 0] N = 0x10dbab158; P = 0x10dbab0b8
DOWN: AAAB [ 5] N = 0x10dbab180; P = 0x10dbab0b8
DOWN: AAB [ 4] N = 0x10dbab0e0; P = 0x10dbab068
DOWN: AABA [-5] N = 0x10dbab1a8; P = 0x10dbab0e0
DOWN: AABB [ 5] N = 0x10dbab1d0; P = 0x10dbab0e0
Комментарии:
1. Ваша реализация верна, поэтому я вознагражу вас очками. Я также придумал реализацию, в которой мне пришлось передать указатель узла на «Пропустить». Я разместил вопрос здесь, потому что надеялся, что существует стандартный способ сделать это без введения вспомогательных параметров. Кажется, нет никакого способа обойти это. Хотя я использовал OO и полиморфизм, реализация функции почти точно такая же.
2. Спасибо. Основной альтернативой параметру ‘skip’ было бы поле флага в каждом узле дерева. Проблема в том, что вам придется сканировать все дерево один раз, чтобы установить для него значение «не посещено»; затем вам нужно будет устанавливать его в каждом узле по мере его посещения. Это более беспорядочно, чем параметр skip. Или вы могли бы использовать список посещенных узлов, который может легко привести к квадратичному поведению при поиске, чтобы узнать, был ли посещен узел, который вы планируете посетить. Параметр skip настолько чист, насколько я могу себе представить; он позволяет избежать изменения самой структуры данных.