Перебирать узлы в дереве
Я хочу сделать итератор, который может обрабатывать мои самодельные структуры:
struct node {
int n; //data element
node * parent;
node * left;
node * right;
node (int elem): n(elem){ //create root
parent = NULL; left = NULL; right = NULL;
}
node (int elem, node* p): n(elem), parent(p) { //addchild
left = NULL;
right = NULL;
}
node(int elem, node * p, node * l, node * r): n(elem), parent(p), left(l), right(r){ //insert element
}
};
Во-первых, возможно ли это? Если да: как мне начать создавать итератор, проходящий по дереву. Если нет: что вы предлагаете мне сделать, если я хочу получить доступ к элементам данных в списке.
Решение
Да.
Подсказка: ваш итератор при продвижении должен перейти к родителю и выяснить, является ли он левым или правым потомком этого родителя. Это скажет вам, куда идти дальше.
Другие решения
Да, учитывая структуру узла, которую вы обрисовали right указатель (который предположительно указывает на следующий узел в порядке обхода), реализация прямого итератора должна быть достаточно легкой.
основной идея примерно такая:
template <class Node>
class iterator {
Node *pos;
public:
iterator(Node *tree = nullptr) : pos(tree) {}
iterator operator++() { pos = pos->right; return *this; }
Node &operator*() { return *pos; }
bool operator!=(iterator const &other) const { return pos != other.pos; }
};
Хотя в настоящем итераторе есть немного больше, чем это. В частности, вы обычно (всегда?) Хотите указать такие вещи, как value_type, reference_type и категория итератора. Большинство из них довольно близко к чистому шаблону, и вы можете справиться с большинством из них, получая из std::iterator,
Вы также (как правило) хотите поддерживать несколько больше операций, чем я показал здесь, таких как приращение после исправления, operator==и т. д. Учитывая это как «основу», я думаю, что заполнение этих пробелов должно быть достаточно простым.
Я должен также указать на существование Увеличить итераторы библиотека. Это упрощает задачу реализации итератора (несколько) и сокращает шаблон, который вы должны написать (совсем немного).