Создание структуры дерева дерева - разный подход

Question

В прошедшем я задал много вопросов о древовидных структурах дерева, но, похоже, я не принял их правильно на C++.

В том, как я написал структуру данных, я не мог придумать ни одного способа, как иметь итератор «конец» или «начать». Таким образом, я перешел к подходу, чтобы включить все функции в качестве методов-членов. Вместо использования стандартного подхода итераторов & алгоритмов.

Теперь цель с моей древовидной структурой состоит в том, чтобы: 1) как можно быстрее перемещать ветку от 1 дерева к другому. 2) каждая ветвь должна быть деревом на своем собственном. И действия, работающие над деревом, также должны быть выполнены на ветке.

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

template <typename ValTy> 
class Tree { 
private: 
    std::vector<std::unique_ptr<Tree> > subtrees; 
    ValTy value; 
}; 

Как вы можете видеть, с этим я могу просто взять что-то из от subtrees - и используйте его либо как дерево, либо скопируйте его. Однако, поскольку дерево верхнего уровня не имеет указаний о том, сколько суб деревьев (или сколько уровней) есть, невозможно указать «конечный итератор»? И поскольку такие алгоритмы, как std :: find(), не будут перебирать все дерево (и все его поддеревья)?

Возможно ли использовать эти алгоритмы, сохраняя при этом структуру легкого «разветвления»?

Answer 1

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

Итератор end() для этого вектора просто будет пустым стеком.

Answer 2

Как вы можете видеть, я могу просто взять что-то из поддеревья - и использовать его либо как дерево, либо скопировать его. Однако, поскольку верхнее дерево уровня не имеет указаний о том, сколько подэлементов (или сколько уровней ) есть, невозможно указать «конечный итератор»? И как такие алгоритмы, как std :: find(), не будут перебирать по всему дереву (и все это поддеревья)?

Ну, проблема здесь скорее в концептуальной проблеме.

Я всегда решаю CRUD Функциональность внутри древовидных структур с рекурсией. Рекурсия не требует знания количества поддеревьев, и это одна из вещей, которая позволяет вставить, найти и удалить O(log n).

Пример вставки:

void insertNode(Node* &treeNode, Node *newNode) { 
    if (treeNode) treeNode = newNode; 
    else if (newNode->key < treeNode->key) insertNode(treeNode->left, newNode); 
    else insertNode(treeNode->right, newNode); 
} 

Если вам нужно знать, сколько уровней находятся на дереве просто идти влево ребенка до NULL. Вы можете легко разработать алгоритмы O(log n) для подсчета числа детей в дереве с использованием этих знаний.

---

Деревья предназначены для рекурсивного доступа. Если вы хотите нерекурсивный доступ, возможно, деревья не то, что вы ищете? - Какими данными будет занимать эта структура, на какой частоте доступа?