使用 std::map::iterators 对树进行层序遍历

Level order traversal of a tree using std::map::iterators

我有一个由节点组成的树结构。每个节点都有一个 ID 和一个 std::map 对所有子节点的引用。

struct Node
{
    Node(std::string id) : id(id) {}
    std::string id;

    Node& operator [] (std::string id)
    {
        iterator it = map.find(id);
        if(it != map.end()) return it->second;
        else
        {
            Node* null = new Node("null");
            return *null;
        }
    }

    void addChild(std::string id)
    {
        Node* child = new Node(id);
        map.insert(std::pair<std::string,Node&>(id,*child));
    }

private:
    std::map<std::string,Node&> map;
};

示例树如下所示

    Node root("root");
    root.addChild("Documents");
    root.addChild("Pictures");
    root.addChild("Music");
    root["Documents"].addChild("Work");
    root["Documents"].addChild("Private");
    root["Documents"].addChild("Home");
    root["Documents"]["Work"].addChild("Finance");
    root["Documents"]["Work"].addChild("Engineering");
    root["Documents"]["Work"]["Finance"].addChild("Week1.xml");
    root["Documents"]["Work"]["Finance"].addChild("Week2.xml");
    root["Documents"]["Work"]["Finance"].addChild("Week3.xml");
    root["Documents"]["Work"]["Finance"].addChild("Week4.xml");
    root["Pictures"].addChild("Tree.jpg");
    root["Pictures"].addChild("Dog.jpg");

我想做一个Level顺序遍历(广度优先遍历)打印出每个节点的id。即,打印 root 下所有节点的名称,然后打印 root 下第一个节点下的所有节点名称,然后打印 root 下第二个节点下的所有节点名称,等等。我希望能够使用一个for循环和迭代器,如下图:

    //ASSIGNEMNT; CONDITION; OPPERATION
    for(Node::iterator it = root.begin(); it != root.end(); root.traverse(it))
    {
        std::cout << it->first << std::endl;
    }

我试图在节点 class 中定义一个算法来实现这一点。该算法如下所示:

    typedef std::map<std::string,Node&>::iterator iterator;

    iterator begin()    {return map.begin();}
    iterator end()      {return map.end();}

    iterator traverse(iterator& it)
    {
        std::cout << "Traversing " << this->id << "..." << std::endl;
        it++;
        if(it != it->second.end()) return it;
        else
        {
            iterator next = it->second.begin();
            return next->second.traverse(next);
        }
    }

但是这个函数只是遍历root然后退出for循环。实现我想要的正确算法是什么?

完整节点 class 和主要功能:

#include <iostream>
#include <map>

using namespace std;

struct Node
{
 Node(std::string id) : id(id) {}
 std::string id;

 typedef std::map<std::string,Node&>::iterator iterator;

 iterator begin() {return map.begin();}
 iterator end()  {return map.end();}

 iterator traverse(iterator& it)
 {
  std::cout << "Traversing " << this->id << "..." << std::endl;
  it++;
  if(it != it->second.end()) return it;
  else
  {
   iterator next = it->second.begin();
      return next->second.traverse(next);
  }
 }

 Node& operator [] (std::string id)
 {
  iterator it = map.find(id);
  if(it != map.end()) return it->second;
        else
        {
            Node* null = new Node("null");
            return *null;
        }
 }

 void addChild(std::string id)
 {
  Node* child = new Node(id);
  map.insert(std::pair<std::string,Node&>(id,*child));
 }

private:
 std::map<std::string,Node&> map;
};

int main()
{
 Node root("root");
 root.addChild("Documents");
 root.addChild("Pictures");
 root.addChild("Music");
 root["Documents"].addChild("Work");
 root["Documents"].addChild("Private");
 root["Documents"].addChild("Home");
 root["Documents"]["Work"].addChild("Finance");
 root["Documents"]["Work"].addChild("Engineering");
 root["Documents"]["Work"]["Finance"].addChild("Week1.xml");
 root["Documents"]["Work"]["Finance"].addChild("Week2.xml");
 root["Documents"]["Work"]["Finance"].addChild("Week3.xml");
 root["Documents"]["Work"]["Finance"].addChild("Week4.xml");
 root["Pictures"].addChild("Tree.jpg");
 root["Pictures"].addChild("Dog.jpg");

 for(Node::iterator it = root.begin(); it != root.end(); root.traverse(it))
 {
  std::cout << it->first << std::endl;
 }


 return 0;
}

您不能使用地图的迭代器,因为您在每个节点中都有不同的地图。您必须定义自己的迭代器 class,它可以跟踪当前正在迭代的节点,并在到达该节点的地图末尾时切换到下一个节点。

您的 traverse 函数已关闭,但将跳过 next 中的第一个迭代器。当它到达最后一个节点(或其映射中没有条目的任何节点)时,它也会 运行 进入未定义行为,因为您将增加 end 迭代器。

一旦遍历移动到其中一个子节点,也会出现未定义行为,因为您随后将比较来自不同容器的迭代器。