Уровень порядка обхода дерева с использованием std :: map :: iterators - PullRequest
Новая
       39

Уровень порядка обхода дерева с использованием std :: map :: iterators

0 голосов
/ 04 июня 2019

У меня есть древовидная структура, состоящая из узлов. Каждый узел имеет идентификатор и карту ссылок std :: на все его дочерние узлы. 

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

Я хочу сделать обход уровня (обход в ширину) и распечатать идентификатор каждого узла. то есть, распечатать все имена узлов под 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;
    }

Я попытался определить алгоритм внутри класса узла, который достигнет этого. Этот алгоритм показан ниже: 

    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. Какой правильный алгоритм для достижения того, что я хочу?

Полный класс узла и основная функция: 

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

1 Ответ

1 голос
/ 04 июня 2019

Вы не можете использовать итератор карты, так как у вас есть разные карты в каждом узле.Вам нужно определить свой собственный класс итератора, который может отслеживать, какой узел он итерирует в данный момент, и переходить к следующему узлу, когда он доберется до конца карты для этого узла.

Ваш *Функция 1003 * близка, но пропустит первый итератор в next.Он также столкнется с неопределенным поведением, когда достигнет последнего узла (или любого узла без записей на своей карте), потому что вы увеличите итератор end.

Существует также неопределенное поведение после перемещенияк одному из подузлов, поскольку вы будете сравнивать итераторы из разных контейнеров.

...