Как перебрать связанные узлы, которые имеют два узла

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::queue для итеративного обхода всех узлов.

Это известно как Поиск в ширину , и важно отметить, что порядок обхода будет отличаться от порядка рекурсии, которыйреализация Поиск в глубину .

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 2

Самое простое решение - использовать рекурсивность. Поскольку глубина (сбалансированного) двоичного дерева равна O(ln(n)), можно смело предполагать, что вы не получите переполнение стека.

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

Answer 3

Я бы предложил использовать два цикла while по одному для каждой стороны`

Node *n = &start;
while(n){
  std::cout << "New node: " << n->value << std::endl;
  n = n->node_left;
}

n = &start;
while(n){
  std::cout << "New node: " << n->value << std::endl;
  n = n->node_right;
}

`

Answer 4

Используемая вами структура данных - это двоичное дерево . Чтобы пройти через ваше двоичное дерево без рекурсии, используйте подход в ширину , который включает использование очереди для удержания каждого узла и его обработки.

Добавление значения .discovered в класс Node предотвратит обработку любого узла дважды. Сбросьте это обнаруженное значение после обработки всех узлов, если вы хотите повторно использовать эту функцию. Использование этого значения необходимо только в том случае, если вы не можете гарантировать, что какой-либо узел указывает на узел-предок или указывает на самого себя.

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

Answer 5

Рекурсивное посещение каждого узла может сделать это: следующее приведет к первому поиску по глубине

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для набора типа