подсчет узлов листа в дереве

Question

Предположим, у нас есть дерево, где каждый узел имеет предварительно заданный набор исходящих узлов. Можно ли придумать быстрый способ/оптимизацию, чтобы подсчитать количество листовых узлов с учетом значения уровня? Было бы здорово, если бы кто-то мог предложить любые идеи/ссылки/ресурсы, чтобы сделать то же самое.

Answer 1

Нет. Вам все равно придется пересекать все дерево. Невозможно предсказать точную структуру - или приблизить ее - только от числа дочерних узлов каждого узла дерева.

Помимо этого: просто держите счетчик и обновляйте его на каждой вставке. Далеко проще и не изменит сложность времени любой операции, кроме подсчета листьев, которая будет уменьшена до O(1).

Answer 2

Это может стать довольно сложной задачей. Поскольку он отличается от языка программирования, какова структура входных данных, это дерево двоичное или общее дерево (произвольное количество детей), размер дерева.

Самая общая идея - запустить DFS или BFS, начиная с корня, чтобы получить каждый уровень узла, а затем составить список наборов, где каждый набор содержит узлы одного уровня. Набор может быть любой структурой, стандартный список в порядке.

Предположим, вы работаете на C++, что является хорошим, если не лучшим практическим выбором, если вам нужна производительность (даже лучше, чем C).

Предположим, у нас есть общее дерево, а структура ввода - это список смежности, как вы упомянули.

Затем вы запускаете либо BFS, либо DFS, либо для дерева, сохраняя уровень для каждого узла. Уровень для следующего узла - это уровень его родителя плюс один.

Как только вы обнаружите уровень, вы помещаете узел таким образом.

vector<vector<int>> nodesPartitionedByLevels(nodeCount); 
//run bfs here 
//inside it you call 
nodesPartitionedByLevels[level].push_back(node) 

Это примерно.

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

в основном вы называете adjList[node].empty(). Если это правда, это листовой узел.