перебрать узлы в дереве

Question

Я хочу сделать итератор, который может обрабатывать мои самопроизведённые:

структуры

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 
} 
}; 

Прежде всего, это возможно? Если да: как я начинаю делать итератор, который пересекает дерево. Если нет: что вы предлагаете мне сделать, если я хочу получить доступ к элементам данных в списке.

Answer 1

Да.

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

Answer 2

Да, учитывая структуру узла, которую вы указали с помощью указателя 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== и т. Д. Учитывая это как «рамки», я думаю, что заполнение этих пробелов должно быть довольно просто.

Я должен, вероятно, также указать на существование библиотеки Boost iterators. Это упрощает задачу реализации итератора (несколько) и сокращает шаблон, который вы должны написать (совсем немного).