没有递归的遍历树和C中的堆栈

Question

如何在没有C(无C++)递归的情况下有效地遍历树的每个节点？

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

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

• 这不是功课.
• 我更喜欢深度.
• 我不喜欢需要额外的数据结构(例如堆栈).
• 我更喜欢速度方面最有效的方式(而不是空间).
• 您可以更改或添加Nodestruct 的成员来存储其他信息.

Answer 1

如果您不想存储任何内容,并且可以使用深度优先搜索:

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是为了防止它在返回时重新命中父节点.

Answer 2

通常,您将使用自己的堆栈数据结构来存储节点列表(如果您想要进行级别订单遍历,则使用队列).

首先将任何给定的起始节点推入堆栈.然后进入主循环,直到堆栈为空.从堆栈中弹出每个节点后,如果不为空,则推送其下一个节点和子节点.