c - 使用链表结构遍历树

Question

我有一个结构节点，其中包含一个下一个节点和一个子节点。

struct Node{
Node *parent;
Node *next;
Node *child;
}

下图是树的结构。

我将如何编写遍历该树的函数？没有递归？

我脑子里有一个伪代码，但不确定它是否正确，因为每个节点都可以有一个 child ，我也需要使用那个 child 进行搜索

while ( root !=NULL)
{

root = root->next;
}

我想访问所有节点。

Answer 1

我猜你的树看起来像这样:

-> grandma
    -> dad
        -> me
        -> sister
            -> niece
        -> brother
    -> uncle
        -> cousin

其中缩进表示祖先级别。递归函数很简单:

void traverse_rec(const Node *node)
{
    if (node) {
        process(node);
        traverse_rec(node->child);
        traverse_rec(node->next);
    }
}

这可以改写为一个循环。如果当前节点有一个 child ，那就是下一个要访问的节点。否则，您想访问它的 sibling 。但是该节点实际上可能没有兄弟节点。因为你有一个到父节点的链接(并且根节点的父节点应该是'NULL')，你可以回溯树直到找到要跟随的兄弟节点或直到节点是NULL。 .

void traverse2(const Node *node)
{
    while (node) {
        puts(node->name);

        if (node->child) {
            node = node->child;
        } else {
            while (node && node->next == NULL) {
                node = node->parent;
            }

            if (node) node = node->next;
        }
    }
}

这比递归函数更复杂，但它可以转换为类似迭代器的代码，从中获取下一个节点:

const Node *next(const Node *node)
{
    if (node == NULL) return NULL;
    if (node->child) return node->child;

    while (node && node->next == NULL) {
        node = node->parent;
    }

    if (node) return node->next;
    return NULL;
}

有了这个“迭代器”，您就可以编写如下代码:

for (const Node *p = root; p; p = next(p)) {
    puts(p->name);
}