使用 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
迭代器。
一旦遍历移动到其中一个子节点,也会出现未定义行为,因为您随后将比较来自不同容器的迭代器。
我有一个由节点组成的树结构。每个节点都有一个 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
迭代器。
一旦遍历移动到其中一个子节点,也会出现未定义行为,因为您随后将比较来自不同容器的迭代器。