Можно итеративно пройти по изменяемому упорядоченному дереву, записав родителя узла в выбранных вами ветвях и зная направление, в котором вы приближаетесь к узлу (вниз или вверх слева или справа, что является упорядоченным свойством дерево позволяет вам тестировать):
template <typename T, typename R>
void in_order ( BSTNode<T>* root, R (*routine)(T) ) {
typedef BSTNode<T>* Node;
Node current = root;
Node parent = 0;
bool going_down = true;
while ( current ) {
Node next = 0;
if ( going_down ) {
if ( current -> leftChild ) {
// navigate down the left, swapping prev with the path taken
Node next_child = current -> leftChild;
current -> leftChild = parent;
parent = current;
current = next_child;
} else if ( current -> rightChild ) {
// navigate down the right, swapping prev with the path taken
Node next_child = current -> rightChild;
current -> rightChild = parent;
parent = current;
current = next_child;
} else {
// leaf
routine ( current -> data );
going_down = false;
}
} else {
// moving up to parent
if ( parent ) {
Node next_parent = 0;
// came from the left branch
if ( parent -> data > current -> data ) {
// visit parent after left branch
routine ( parent -> data );
// repair parent
next_parent = parent -> leftChild;
parent -> leftChild = current;
// traverse right if possible
if ( parent -> rightChild ) {
going_down = true;
// navigate down the right, swapping prev with the path taken
Node next_child = parent -> rightChild;
parent -> rightChild = next_parent;
//parent = current;
current = next_child;
continue;
}
} else {
// came from the right branch
next_parent = parent -> rightChild;
parent -> rightChild = current;
}
current = parent;
parent = next_parent;
} else {
break;
}
}
}
}
Если вместо того, чтобы хранить дочерние элементы, вы сохраняете XOR родительского и дочернего элементов, то вы можете получить следующий узел в любом направлении, к которому вы подходите, без необходимости изменять дерево.
Я не знаю ничего, что автоматически превращало бы не хвостовые рекурсивные функции в такой код. Я знаю среды, в которых стек вызовов расположен в куче, которые прозрачно избегают переполнения стека в тех случаях, когда вы не можете выполнять такие мутации и иметь фиксированный небольшой размер стека. Обычно запись состояния в стеке занимает меньше места, чем в стеке вызовов, поскольку вы выбираете только существенное локальное состояние для записи, а не записываете адреса возврата или какие-либо регистры сохранения вызовов (если вы использовали функтор, а не функцию указатель, то более вероятно, что компилятор сможет встроить routine и, следовательно, не сохранять регистры сохранения вызывающей стороны в простом рекурсивном случае, что уменьшает количество стека, требуемого для каждой рекурсии. YMMV).
Поскольку вы используете шаблоны, вам нужно всего лишь один раз выполнить код обхода и объединить его с шаблонами стратегий, чтобы переключаться между режимами pre, post и inorder или любым другим итерационным режимом, который вы хотите.