我一直在尝试开发/寻找一种非常具体的方法来遍历树结构。我真的只熟悉 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;
}
这段代码当然只是对起始节点以下的所有内容执行自上而下的遍历。当我尝试添加代码将访问者推到树上并从那里进行自上而下的遍历时，问题就出现了。在访问 child 之前调用 Parent->Accept(pVisitor) 显然不会产生预期的结果。在访问子节点后调用 Parent->Accept(pVisitor) 只会在入口节点的情况下产生所需的结果。对于每个其他节点，它都会导致问题。
我想知道是否有人对这些类型的树遍历方法有任何经验，我是否真的有足够的信息来进行这种遍历。同样重要的是，我不跟踪任何以前访问过的项目的列表。充其量我可以在函数本身中跟踪先前访问过的节点。也许这是一种广为人知且被广泛记录的遍历方法，但我只是不知道其名称。
提前致谢!
最佳答案
这段代码似乎实现了您的要求。这项工作的关键是访问第一个节点(无论是什么)被视为 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, { &data[ 1], &data[ 2], }, },
{ "AA", -3, &data[0], { &data[ 3], &data[ 4], }, },
{ "AB", +3, &data[0], { &data[ 5], &data[ 6], }, },
{ "AAA", -4, &data[1], { &data[ 7], &data[ 8], }, },
{ "AAB", +4, &data[1], { &data[ 9], &data[10], }, },
{ "ABA", -4, &data[2], { &data[11], &data[12], }, },
{ "ABB", +4, &data[2], { &data[13], &data[14], }, },
{ "AAAA", 0, &data[3], { 0, 0, }, },
{ "AAAB", +5, &data[3], { 0, 0, }, },
{ "AABA", -5, &data[4], { 0, 0, }, },
{ "AABB", +5, &data[4], { 0, 0, }, },
{ "ABAA", -5, &data[5], { 0, 0, }, },
{ "ABAB", +5, &data[5], { 0, 0, }, },
{ "ABBA", -5, &data[6], { 0, 0, }, },
{ "ABBB", +5, &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 [%2d] N = %p; P = %p\n", 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 && 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 && 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 %s\n", tag);
dfs_traverse(up_down, node, skip);
}
int main(void)
{
Node *aaa = &data[3];
Node *root = &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, &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
关于algorithm - 很具体的树遍历方法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24337059/