tree.hh - обход C ++ листьев

Question

Вывод следующего кода неверен. Должны выводиться только листья в дереве:

tree<Node> gameTree;
tree<Node>::iterator root = gameTree.insert(gameTree.begin(),Node(14));
tree<Node>::iterator first = gameTree.append_child(root,Node(32.0));
tree<Node>::iterator second = gameTree.append_child(root,Node(64.0));
gameTree.append_child(second,Node(21.0));
gameTree.append_child(second,Node(24.0));

tree<Node>::iterator begin = gameTree.begin_leaf();
tree<Node>::iterator end = gameTree.end_leaf();
int x = 0;
while (begin != end) 
{ 
    cout << begin->value << endl; 
    begin++;
}

Но выводит:

32
64
21
24

когда вывод ДОЛЖЕН быть:

32
21
24

Answer 1

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

btw,спасибо за публикацию этого я только начал в поиске контейнера дерева

hth

Answer 2

То, что происходит, - то, что класс итератора - фактически просто определение типа для класса pre_order_traversal. Поэтому, когда вы устанавливаете результат gameTree.beginLeaf() (который возвращает leaf_iterator) для итератора, он вызывает конструктор копирования pre_order_iterator, потому что есть конструктор, определенный для pre_order_traversal(const iterator_base&) (iterator_base является суперклассом для всех других итераторов, включая leaf_iterator) , так что это создает новый pre_order_iterator из leaf_iterator. Затем, когда вы используете этот итератор, он выполняет обход в глубину, а не перебирает листья. Если вы переключитесь на leaf_iterator вместо итератора, проблема исчезнет.

Именно поэтому прямая форма, упомянутая в комментарии ниже (где значение не присваивается итератору), работает правильно.

Answer 3

Я не знаю, что такое tree<>, и при этом я не знаю семантику append_child, но из того, что я вижу, 32, 64, 21 и 24 все находятся ниже корня иерархии (дети и внукииз 14);Я не вижу проблемы.

Почему именно пропустить 64, а не 24?