Обход узлов дерева листьев без полного обхода дерева
В общей структуре дерева с указателями родителя и потомка, возможно ли пройти узлы листа, не пройдя полное дерево? Например, начиная с самого левого конечного узла. Идея заключалась в том, чтобы оптимизировать на глубоких деревьях.
2 ответа
Нет. Чтобы добраться до каждого листа, вы должны пройти через каждый узел.
Поскольку дерево является ациклическим, нет избыточных путей. Поэтому нет "лишних" способов получить места, а значит, и ярлыков тоже не найти. Каждый узел является либо (а) листом, либо (б) на критическом пути к одному или нескольким листьям.
Структура данных должна была бы быть улучшена некоторым способом, чтобы оптимизировать обход листа.
Если вы представляете дерево в виде обычного указателя на C++ с корнем, указывающим на дочерние элементы, то достичь этого невозможно, так как дерево представляет собой ациклический граф.
Если вы представляете дерево по-разному (например, в виде кучи с использованием массива), вы можете пройти только по дочерним элементам, поскольку они имеют смещение в массиве.
Обратите внимание, что листья сбалансированного бинарного дерева составляют половину его размера, поэтому сложность не достигается при обходе только листьев. Фракция является большим числом для сбалансированных тройных и других почти полных n-арных деревьев.