我想遍历此节点系统以确保命中每个节点，并且我不想使用递归。每个节点实际上都有两个链接的节点。我不知道这是否称为双向链接列表或其他名称。
一个节点看起来像
class Node {
private:
Node* next_node_type_a;
Node* next_node_type_b;
}
图
|next_node_type_a| ->
|next_node_type_a| -> |next_node_type_b| ->
|start-node| ->
|next_node_type_b| -> |next_node_type_a| ->
|next_node_type_b| ->
最初我没有看到第二个节点，所以我有
while(node){
DoStuffWithNode(node);
node = node->GetNextNodeTypeA();
}
但是如何修改它以仍然使用while循环遍历两个节点路径？
这里有一些示例代码可以使用
// Example program
#include <iostream>
#include <string>
class Node {
public:
Node* node_left;
Node* node_right;
std::string value;
Node();
};
Node::Node(){
node_left = 0;
node_right = 0;
}
int main()
{
Node start;
Node a;
Node b;
Node c;
Node d;
Node e;
Node f;
start.value = "start";
a.value = "a";
b.value = "b";
c.value = "c";
d.value = "d";
e.value = "e";
f.value = "f";
start.node_left = &a;
start.node_right = &b;
a.node_left = &c;
a.node_right = &d;
b.node_left = &e;
b.node_right = &f;
Node *n = &start;
while(n){
std::cout << "New node: " << n->value << std::endl;
n = n->node_left;
}
return 0;
}
编辑：我刚刚意识到这是一棵树。
递归是在二叉树上进行迭代的惯用方式，如其他答案所示，but如果需要迭代解决方案，则可以使用其他数据结构（例如std::queue）来迭代遍历所有节点。
[这被称为std::queue，需要注意的是遍历的顺序将与递归的顺序不同，后者是Breadth First Search的实现。
Depth First Search
同样的方法也适用于非二叉树。
最简单的解决方案是使用递归。由于（平衡的）二叉树的深度为std::queue<Node*> nodesToVisit;
nodesToVisit.push(&start);
while (nodesToVisit.size())
{
Node* n = nodesToVisit.front();
nodesToVisit.pop();
std::cout << "New node: " << n->value << std::endl;
if (n->node_left)
{
nodesToVisit.push(n->node_left);
}
if (n->node_right)
{
nodesToVisit.push(n->node_right);
}
}
，因此可以放心地假设不会出现堆栈溢出。
O(ln(n))递归地访问每个节点都可以做到：以下将导致深度优先搜索
void apply(Node* n)
{
if (n == nullptr) {
return;
}
DoStuffWithNode(n->node_left);
DoStuffWithNode(n->node_right);
}
当然，如果您的节点链接回它们自己，这可能会失败，因此请考虑将std::vector<Node*> BuildList(Node* root) {
vector<Node*> nodes;
if(root) {
nodes.push_back(root);
BuildList(root, nodes);
}
return nodes;
}
void BuildList(Node* node, std::vector<Node*> current) {
if(node->next_node_type_a) {
current.push_back(node->next_node_type_a);
BuildList(node->next_node_type_a, current);
}
if(node->next_node_type_b) {
current.push_back(node->next_node_type_b);
BuildList(node->next_node_type_b, current);
}
}
换成集合类型
您正在使用的数据结构是std::vector。要遍历二叉树without递归，请使用binary tree方法，该方法涉及使用breadth-first来保存每个节点并对其进行处理。