Как реализовать методы begin() и end() в итераторе для binary-search tree?
Как реализовать методы begin() и end() в итераторе для binary-search tree? Не понимаю, на что указывает эти итераторы для BST. Хочу реализовать обход BST как абстрактного контейнера в STL, примерно так
for(tree::iterator it = tree.begin(); it!= tree.end(); it++){
//какие-то действия
}
Ответы (1 шт):
В дополнение к вышеприведенному хочу поделиться соображениями по поводу end. Получение этого итератора может быть довольно нетривиальной учитывая структуру дерева. Как очевидное решение - хранить указатель на последню ноду в дереве, но это плохое решение, так как потребует дополнительной логики и проверок. Вместо этого лучше рассматривать ваше дерево как левое поддерево более крупного. Таким образом ваш итератор end будет как бы указывать на родителя корня вашего дерева - это позволит не внедрять вообще никакой дополнительной логики
не обязательно, можно обойтись без связей к родителю. Для этого в итераторе должен быть стэк посещённых узлов. Также добавление или удаление ноды инвалидирует такой итератор
https://ru.stackoverflow.com/questions/853723/Как-работает-итератор-в-дереве