遍历树，而无需使用C递归和堆栈 [英] Traverse tree without recursion and stack in C

问题描述

如何遍历树的每个节点没有有效使用C递归（没有C ++）？

How to traverse each node of a tree efficiently without recursion in C (no C++)?

假如我有树的以下节点结构：

Suppose I have the following node structure of that tree:

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

• 这不是功课。


• I preFER深度优先。


• I preFER需要（如堆栈）没有额外的数据结构。


• 我的速度（而不是空间）的长期preFER最有效的方式。


• 您可以更改或添加节点结构的成员，以存储更多的信息。


• It's not homework.
• I prefer depth first.
• I prefer no additional data struct needed (such as stack).
• I prefer the most efficient way in term of speed (not space).
• You can change or add the member of Node struct to store additional information.

推荐答案

如果你不希望有任何存储，并确定了深度优先搜索：

If you don't want to have to store anything, and are OK with a depth-first search:

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;
    }
}

将遍历树; 过程是要保持它重新打父节点，当它往回走。

Will traverse the tree; process is to keep it from re-hitting parent nodes when it travels back up.

这篇关于遍历树，而无需使用C递归和堆栈的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！