c - 遍历树，没有递归并且在C中堆叠

如何有效遍历树的每个节点而无需在C中递归(无C++)？

假设我具有该树的以下节点结构:

struct Node
{
    struct Node* next;   /* sibling node linked list */
    struct Node* parent; /* parent of current node   */
    struct Node* child;  /* first child node         */
}

这不是家庭作业。

我更喜欢深度。

我希望不需要其他数据结构(例如堆栈)。

就速度(而不是空间)而言，我更喜欢最有效的方法。

您可以更改或添加Node结构的成员以存储其他信息。

最佳答案

如果您不想存储任何东西，并且可以进行深度优先搜索，那就可以了:

process = TRUE;
while(pNode != null) {
    if(process) {
        //stuff
    }
    if(pNode->child != null && process) {
         pNode = pNode->child;
         process = true;
    } else if(pNode->next != null) {
         pNode = pNode->next;
         process = true;
    } else {
         pNode = pNode->parent;
         process = false;
    }
}

会穿过那棵树； process是为了防止它在备份旅行时重击父节点。

关于c - 遍历树，没有递归并且在C中堆叠，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3214312/