Обход в ширину с деревом, реализованный с помощью векторов - PullRequest
Новая
       8

Обход в ширину с деревом, реализованный с помощью векторов

0 голосов
/ 11 мая 2018 
    class Employee {
    public:
        const std::string const getName();
        const std::vector<Employee>& const getSubordinates();
    private:
        std::string name;
        std::vector<Employee> subordinates;
    };

    void printEmployeeLevels(Employee e)
    {
    }

Предполагается, что моя программа сможет использовать обход в ширину для распечатки имен сотрудников в иерархии.Например, данный сотрудник e может иметь подчиненных a и b.Сотрудник a может иметь подчиненных c и d, а сотрудник b может иметь подчиненных f.Тогда подчиненный c может иметь подчиненный g.

Моя проблема в том, что я не уверен, как применить это к бинарному дереву, которое на самом деле не имеет структуры узлов с атрибутами левого и правого дочернего элемента.Мой главный вопрос, который у меня возникает, заключается в следующем: если я использую очередь для этого обхода, я должен сделать ее очередью объектов Employee или очередью вектора объектов Employee? 

    void printEmployeeLevels(Employee e)
    {
        Queue<Employee> q;

        q.enqueue(e);

        while (1){
        while(!q.isEmpty())
        {
            Employee k = q.front();
            std::vector<Employee> v = k.getSubordinates();
            for (int i = 0; i < k.getSubordinates().size(); ++i)
            {
                q.enqueue(v[i]);
                std::cout << v[i].getName() << " ";
            }
            q.dequeue();
            std::cout << '\n';
        }
        }
    }

Ожидаемый результатявляется: (учитывая сценарий выше, где порядок дочерних узлов не имеет значения)

e
ab
cdf
g

...