如何遍历具有两个节点的链接节点

Question

我想遍历这个节点系统以确保命中每个节点，我不想使用递归。每个节点实际上有两个链接节点。不知道这个叫双向链表还是什么

一个节点看起来像

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

编辑：我刚刚意识到这是一棵树。

Answer 1

递归访问每个节点可以做到：以下将导致深度优先搜索

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

当然，如果您的节点 link 回到它们自己，这可能会失败，因此请考虑将 std::vector 换成集合类型

Answer 2

最简单的解决方案是使用递归。由于（平衡的）二叉树的深度是 O(ln(n))，你可以放心地假设你不会得到堆栈溢出。

void apply(Node* n)
{
    if (n == nullptr) {
        return;
    }
    DoStuffWithNode(n);
    apply(n->node_left);
    apply(n->node_right);
}

Answer 3

递归是迭代二叉树的惯用方法，如其他答案所示，但是如果您需要迭代解决方案，则可以使用其他数据结构，例如a std::queue 迭代遍历所有节点。

这被称为 Breadth First Search and it's important to note that the order of traversal will be different than that of recursion, which is an implementation of 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);
    }
}

同样的方法也适用于非二叉树，但需要额外的代码来处理循环图，例如跟踪 std::set.

中所有访问过的节点。

Answer 4

您使用的数据结构是 binary tree. To traverse through your binary tree without recursion, use the breadth-first approach, which involves using a queue 来保存每个节点并对其进行处理。

在节点 class 上添加 .discovered 值将防止处理任何节点两次。如果要重用此功能，请在处理完所有节点后重置此发现值。仅当您不能保证任何节点指向祖先节点或指向自身时才需要使用此值。

#include <iostream> 
#include <queue> 
using namespace std;

void BreadthFirst(Node start) {
    Queue<Node> Q;
    start.discovered = true;
    Q.push(start)
    while (!Q.isEmpty()) {
        Node n = Q.pop()
        cout << n.value << endl;
        if (n->next_node_type_a != null) {
            if(n->next_node_type_a.discovered == false) {
                n->next_node_type_a.discovered = true;
                Q.push(n->next_node_type_a);
            }
        }
        if (n->next_node_type_b != null) {
            if(n->next_node_type_b.discovered == false) {
                n->next_node_type_b.discovered = true;
                Q.push(n->next_node_type_b);
            }
        }
    }
}

如何遍历具有两个节点的链接节点

How to loop through linked nodes that have two nodes

c++

binary-tree

tree-traversal