Посмотрите на это так:
0 00 000 | (0,0) (0,1) (0,2)
001 | (1,2)
1 10 100 | (2,0) (2,1) (2,2)
101 | (3,2)
11 | (4,1)
Я использовал тот же синтаксис, что и вы, чтобы называть узлы (левая сторона) и соответствующую позицию "(строка, столбец)" в сетке (правая сторона).Здесь есть два отдела высшего уровня, 0 и 1. Вы можете пометить свои узлы координатами ((x, y)) с первым посещением по глубине для каждого дерева / отдела верхнего уровня.Всякий раз, когда вы переходите от отца к ребенку, вы должны увеличивать номер столбца на 1. Каждый раз, когда вы посещаете нового родного брата, ваш индекс строки должен ссылаться на новый, пустой индекс (в этом примере брат 10 равен 11, но вы можетене помещайте это в (3,1), потому что строка 3 уже занята отделом 101).
Я написал бы алгоритм, следуя этим рекомендациям.Следите за текущим (x, y) двумя переменными, которые передаются как параметры рекурсивного посещения в глубину, вместе с текущим узлом / отделом, который необходимо посетить.Убедитесь, что функция редактирует, как требуется, представление Excel, но возвращает максимальный использованный индекс строки (чтобы вы могли использовать его, чтобы узнать, какая следующая строка при посещении нового брата - как в предыдущем примере).Каждый раз, когда вы делаете рекурсивный вызов, вы должны вызывать его с координатами (x, y + 1), потому что это новый столбец.Аналогичным образом, когда вы посещаете нового родного брата, вы вызываете его с помощью (ords prev_call_retn + 1, y), потому что это новая строка (гдеordins_prev_call_retn - это значение последнего рекурсивного вызова предыдущего родственного брата).Вспомогательная функция будет вызывать рекурсивную функцию для корневого узла и использовать в качестве базовых координат (0,0), или что угодно, с чего вы хотите начать.
#include <iostream>
#include <list>
#include <string>
using namespace std;
class Dept {
public:
string id;
list<Dept*> *subDepts;
Dept(string id) {
this->id = id;
this->subDepts = new list<Dept*>();
}
Dept *addChild(Dept *d) {
this->subDepts->push_back(d);
return d;
}
Dept *addChild(string id) {
Dept *d = new Dept(id);
return this->addChild(d);
}
};
void visit(Dept *d, int row, int col) {
cout << "Dept " << d->id << ": (" << row << ", " << col << ")\n";
}
int label(Dept *d, int row, int col) {
if (d == 0) return row;
visit(d, row, col);
list<Dept*> *lst = d->subDepts;
for (list<Dept*>::iterator it = lst->begin() ; it != lst->end(); it++)
{
row = label(*it, row, col+1) + 1;
}
if (lst->size() > 0) row--;
return row;
}
int label(Dept *d) {
label(d, 0, 0);
}
В этом коде C ++ label () являетсяинтересующая вас функция.
Предполагается, что параметры row и col являются правильными координатами отдела * d, чтобы мы могли немедленно посетить узел.
Цикл рекурсивно вызываетметка () на каждом потомке (если есть).Обратите внимание, что я использую переменную строку, чтобы отслеживать последнюю использованную строку + 1.
Наконец, мы должны вернуть последнюю использованную строку функцией, но будьте осторожны, чтобы вычесть одну, если d-> subDepts не пустой.Это связано с тем, что цикл for добавляет 1 дополнительную строку в последней итерации.
Вот пример main:
int main(int argc, char **argv) {
Dept *d0 = new Dept("0");
Dept *d00 = d0->addChild("00");
Dept *d01 = d0->addChild("01");
Dept *d000 = d00->addChild("000");
Dept *d001 = d00->addChild("001");
Dept *d002 = d00->addChild("002");
Dept *d010 = d01->addChild("010");
Dept *d02 = d0->addChild("02");
label(d0);
return 0;
}
А вот и результат:
bash-4.2$ g++ dept.cpp && ./a.out
Dept 0: (0, 0)
Dept 00: (0, 1)
Dept 000: (0, 2)
Dept 001: (1, 2)
Dept 002: (2, 2)
Dept 01: (3, 1)
Dept 010: (3, 2)
Dept 02: (4, 1)
Надеюсь, это поможет.