c++树遍历深度

Question

我尝试遍历一棵树，深度优先。节点具有get_child（）和get_sibling（）。

这是我天真的方法，显然不起作用：

int traverseTree(const Node *node)
{
    printf("index: %d n", node->get_idx());
    const Node *child = node->get_child();
    const Node *sibling = node->get_sibling();
    if (child != NULL) {
        traverseTree(child);
    }
    else if (sibling != NULL)
    {
        traverseTree(sibling);
    }
    return 0;
}

编辑

这棵树是如何建造的：https://github.com/rggibson/open-pure-cfr/blob/master/betting_node.cpp#L137

Answer 1

你犯了一个小错误，造成了不利影响。。。

根据您的代码，您将遍历子对象或遍历兄弟对象，而不是两者都遍历。因此，您需要遍历子节点和兄弟节点。

这是一个完美的代码。

int traverseTree(const Node *node)
{
    printf("index: %d n", node->get_idx());
    const Node *child = node->get_child();
    const Node *sibling = node->get_sibling();
    /*First traverse through child up to full depth*/
    if (child != NULL) {
        traverseTree(child);
    }
    /* Traverse through sibling up to its full depth*/
    if (sibling != NULL)
    {
        traverseTree(sibling);
    }
    return 0;
}

这只适用于二叉树。对于非二叉树，您需要循环遍历子级和同级，因为它有多个子级和同级。