Печать в ширину для дерева с несколькими дочерними узлами
У меня есть древовидная структура данных, в которой родительский узел может иметь любое количество дочерних узлов (> = 0). (См. Sample_tree.jpeg) Я хочу создать такое дерево. Один из возможных подходов, предложенных мной, — создание связанного списка, как показано на рисунке my_approach. Связанные списки связаны, как показано. Можете ли вы помочь е здесь написать ширину первой печати с этой структурой?
Пожалуйста, напишите код на C ++.
Если это невозможно, можете ли вы предложить подходящую структуру?
Решение
Хранение каждого отдельного узла в связанном списке было бы (вероятно) плохим способом управления им, так как вам нужно было бы знать, в каком порядке вы должны идти дальше, особенно если вы не добавляете их в том порядке, в котором хотите их указать. из.
Лучшей структурой данных было бы создание класса для каждого узла и предоставление ему закрытой переменной вектора или связанного списка его дочерних элементов.
Затем используйте другой класс, который будет управлять печатью каждого узла, поддерживая очередь FIFO для порядка их печати.
некоторый основной псевдокод, как это было некоторое время назад, я сделал это:
class Node {
public:
...
void addChildren(vector<Node*>*);private:
vector<Node*> _children;
};
void addChildren(vector<Node*>* queue) {
for (unsigned int i = 0; i < _children.size(); i++) {
queue->push_back(_children.at(i));
}
}
где переменная очереди — это просто вектор, поддерживаемый главной функцией (или другим классом, если вам нужна лучшая инкапсуляция), которая повторяется. Единственное, что вам, вероятно, придется явно добавить, это первый узел в очереди.
Тогда при печати из очереди:
vector<Node*> queue;
//create your nodes statically or dynamically
//populate the queue with the first node
for (unsigned int i = 0; i < queue.size(); i++) {
//print whatever you want from the node here
//This adds the current node's children to the end of the FIFO queue
queue.at(i)->getChildren(queue);
}
это должно пройти по всем узлам и сначала добавить их в ширину.
примечание: я изменил связанный список на вектор, потому что это быстрее, когда вам нужно только добавить данные в конец контейнера.
Другие решения
Других решений пока нет …
detector