Это зависит от того, что вы на самом деле хотите с ним сделать, - а также от возможного рефакторинга его для шаблонизации заказа или разделения трех типов обхода, вы можете захотеть превратить его во внутреннюю итерацию, позволяющую любому посещать данныев дереве:
enum order_t { PREORDER, INORDER, POSTORDER };
template<typename T, order_t order, typename F>
void traverse_binary_tree(BinaryTreeNode<T>* root, F f)
{
if( root == NULL ) return;
if(order == PREORDER) f(root->data);
traverse_binary_tree<T,order>(root->left,f);
if(order == INORDER) f(root->data);
traverse_binary_tree<T,order>(root->right,f);
if(order == POSTORDER) f(root->data);
}
template<typename T, typename F>
void traverse_binary_tree(BinaryTreeNode<T>* root, F f, order_t order = PREORDER)
{
switch (order) {
case PREORDER:
traverse_binary_tree<T,PREORDER>(root,f);
break;
case POSTORDER:
traverse_binary_tree<T,POSTORDER>(root,f);
break;
case INORDER:
traverse_binary_tree<T,INORDER>(root,f);
break;
}
}
(вы можете также захотеть использовать константные версии F & и F & вместо простого копирования, параметр функции передачи по значению, который позволит вам передавать функторы, которые могут изменяться и создаватьрезультат; по значению все в порядке, пока ваш функтор не имеет переменных-членов или конструктора)
Или вы можете создать итераторы, которые представляют три обхода, позволяя записывать вывод, используя std :: copy;однако, это будет намного больше кода и не будет сделано только для этой цели.Однако создание итератора позволит обрабатывать большие деревья без переполнения стека, так как вам придется либо иметь указатель 'parent' в каждом узле, либо иметь итератор для поддержки явного стека посещенных узлов.
Хотя сама функция становится очень простой:
std::ostream_iterator<std::string>(std::cout, " ");
std::copy(d.begin(order), d.end(), out);
Использование итератора не упрощает реализацию ни с точки зрения loc, ни с точки зрения возможности следить за происходящим:
#include<string>
#include<iostream>
#include<functional>
#include<algorithm>
#include<iterator>
#include<vector>
#include<stack>
enum order_t { PREORDER, INORDER, POSTORDER };
template <typename T>
class BinaryTreeNode {
public:
BinaryTreeNode(const T& data) : data(data), left(0), right(0) { }
BinaryTreeNode(const T& data, BinaryTreeNode<T>* left, BinaryTreeNode<T>* right) : data(data), left(left), right(right) { }
public:
BinaryTreeNode<T>* left;
BinaryTreeNode<T>* right;
T data;
class BinaryTreeIterator {
BinaryTreeNode <T>* current;
std::stack<BinaryTreeNode <T>*> stack;
order_t order;
bool descending;
public:
typedef T value_type;
typedef std::input_iterator_tag iterator_category;
typedef void difference_type;
typedef BinaryTreeIterator* pointer;
typedef BinaryTreeIterator& reference;
BinaryTreeIterator (BinaryTreeNode <T>* current, order_t order) : current(current), order(order), descending(true)
{
if (order != PREORDER)
descend();
}
BinaryTreeIterator () : current(0), order(PREORDER), descending(false)
{
}
private:
void descend() {
do {
if (current->left) {
stack.push(current);
current = current -> left;
descending = true;
} else if ((order!=INORDER) && current->right) {
stack.push(current);
current = current -> right;
descending = true;
} else {
descending = false;
break;
}
} while (order != PREORDER);
}
public:
bool operator== (const BinaryTreeIterator& other) {
if (current)
return current == other.current && order == other.order;
else
return other.current == 0;
}
bool operator!= (const BinaryTreeIterator& other) {
return !((*this)==other);
}
const T& operator * () const {
return current -> data;
}
BinaryTreeIterator& operator++ () {
// if the stack is empty, then go to the left then right
// if the descending flag is set, then try to descending first
if (descending)
descend();
// not descending - either there are no children, or we are already going up
// if the stack is not empty, then this node's parent is the top of the stack
// so go right if this is the left child, and up if this is the right child
if (!descending) {
do {
if (stack.size()) {
BinaryTreeNode <T>* parent = stack.top();
// for inorder traversal, return the parent if coming from the left
if ((order == INORDER) && (current == parent->left)) {
current = parent;
break;
}
// if this is the left child and there is a right child, descending into the right
// or if this is the parent (inorder)
if ((current == parent) && (parent -> right)) {
current = parent->right;
descend();
// simulate return from descent into left if only the right child exists
if ((current->left == 0)&&(current->right))
stack.push(current);
break;
}
// if this is the left child and there is a right child, descending into the right
if ((current == parent->left) && (parent -> right)) {
descending = true;
current = parent->right;
if (order != PREORDER)
descend();
break;
}
// either has come up from the right, or there is no right, so go up
stack.pop();
current = parent;
} else {
// no more stack; quit
current = 0;
break;
}
} while (order != POSTORDER);
}
return *this;
}
};
BinaryTreeIterator begin(order_t order) { return BinaryTreeIterator(this, order); }
BinaryTreeIterator end() { return BinaryTreeIterator(); }
};
int main () {
typedef BinaryTreeNode<std::string> Node;
std::ostream_iterator<std::string> out( std::cout, " " );
Node a("a");
Node c("c");
Node b("b", &a, &c);
Node e("e");
Node h("h");
Node i("i", &h, 0);
Node g("g", 0, &i);
Node f("f", &e, &g);
Node d("d", &b, &f);
std::copy(d.begin(INORDER), d.end(), out);
std::cout << std::endl;
std::copy(d.begin(PREORDER), d.end(), out);
std::cout << std::endl;
std::copy(d.begin(POSTORDER), d.end(), out);
std::cout << std::endl;
return 0;
}