如何在没有C(无C ++)递归的情况下有效地遍历树的每个节点?
假设我有该树的以下节点结构:
struct Node { struct Node* next; /* sibling node linked list */ struct Node* parent; /* parent of current node */ struct Node* child; /* first child 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开始查看数据。
如果要避免递归,则需要保留树中每个对象的引用。
需要了解更多c/c++开发分享没有递归的遍历树和C中的堆栈,也可以关注C/ C++技术分享栏目—计算机技术网(www.ctvol.com)!
以上就是c/c++开发分享没有递归的遍历树和C中的堆栈相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/980147.html