没有递归的遍历树和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是为了防止它在返回时重新命中父节点。
通常，您将使用自己的堆栈数据结构来存储节点列表（如果您想要进行级别订单遍历，则使用队列）。
首先将任何给定的起始节点推入堆栈。 然后进入主循环，直到堆栈为空。 从堆栈中弹出每个节点后，如果不为空，则推送其下一个节点和子节点。
您可以使用指针反转方法。 缺点是您需要在节点内保存一些信息，因此不能在const数据结构上使用它。
这看起来像我25年前在工程学院做过的练习。 我认为这称为树包络算法，因为它绘制了树的包络。
我简直不敢相信。 我一定在某个地方犯了一个不经意的错误。 任何错误，我相信包络策略是正确的。 如果代码是错误的，只需将其视为伪代码。
while current node exists{ go down all the way until a leaf is reached; set current node = leaf node; visit the node (do whatever needs to be done with the node); get the next sibling to the current node; if no node next to the current{ ascend the parentage trail until a higher parent has a next sibling; } set current node = found sibling node; }
代码：
void traverse(Node* node){ while(node!=null){ while (node->child!=null){ node = node->child; } visit(node); node = getNextParent(Node* node); } } /* ascend until reaches a non-null uncle or * grand-uncle or ... grand-grand...uncle */ Node* getNextParent(Node* node){ /* See if a next node exists * Otherwise, find a parentage node * that has a next node */ while(node->next==null){ node = node->parent; /* parent node is null means * tree traversal is completed */ if (node==null) break; } node = node->next; return node; }
您必须将其存储在可迭代列表中。 带索引的基本列表将起作用。 然后你只需从0开始查看数据。
如果要避免递归，则需要保留树中每个对象的引用。