template<typename T>
void traverse_binary_tree(BinaryTreeNode<T>* root,int order = 0)// 0:pre, 1:in , 2:post
{
if( root == NULL ) return;
if(order == 0) cout << root->data << " ";
traverse_binary_tree(root->left,order);
if(order == 1) cout << root->data << " ";
traverse_binary_tree(root->right,order);
if(order == 2) cout << root->data << " ";
}
Is there a better way to write this function?
You can move order to the template argument.
template<typename T, int order> // 0:pre, 1:in , 2:post
void traverse_binary_tree(BinaryTreeNode<T>* root)
{
if( root == NULL ) return;
if(order == 0) cout << root->data << " ";
traverse_binary_tree<T,order> (root->left);
if(order == 1) cout << root->data << " ";
traverse_binary_tree<T,order> (root->right);
if(order == 2) cout << root->data << " ";
}
Two of each if(order == will be compiled out in each instantiation of the function.
No.
Kidding. I think it looks pretty efficient.
I would enum the order values, for readability.
...
enum TOrder {ORDER_PRE, ORDER_IN, ORDER_POST};
template<typename T>
void traverse_binary_tree(BinaryTreeNode<T>* root,TOrder order = ORDER_PRE) {
...
@Vi, you will be in a corner with function specialization see http://stackoverflow.com/search?q=function+partial+specialization
Testing order is not efficient and not elegant, you shall delegate the traverse_binary_tree to a template class that will do only one job. (through specialization) This template class shall also as for member a BinaryTreeNode * to start the recursive algorithm.
Is there a better way to write this function?
If it's not a balanced binary tree, it could be prone to stack overflow. Writing it iteratively will avoid this. However, that's probably not what you are after as I suspect this is an academic exercise in recursion. If this was a real world project, you will probably be asked why you are implementing a binary tree when efficient set and associative containers already exist.
You could rewrite the function this way to coincide with single-entry, single-exit (trying to stick to your style):
template<typename T>
void traverse_binary_tree(BinaryTreeNode<T>* root,int order = 0)// 0:pre, 1:in , 2:post
{
if( root != NULL )
{
if(order == 0) cout << root->data << " ";
traverse_binary_tree(root->left,order);
if(order == 1) cout << root->data << " ";
traverse_binary_tree(root->right,order);
if(order == 2) cout << root->data << " ";
}
}
Some may find this to be better, though others would not (SESE cannot be practically enforced in most projects due to exception-handling).
If you really want to go above and beyond (still for academic purposes), you could implement tree iterators which do pre-order, in-order, and post-order traversal. This will iterate through the tree without recursion and allow you to decouple tree traversal details from printing out nodes. It's certainly not a trivial task, especially in C++ which has no language-level equivalent of generators/coroutines.
You could also avoid using magic numbers (0, 1, 2) for pre-order, in-order, and post-order traversal and use named constants instead.
It depends what you are wanting to do with it really - as well as possibly refactoring it to templatize the order, or separating the three traversal types, you might want to turn it into an internal iteration, allowing anything to visit the data in the tree:
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;
}
}
(you may also want const F& and F& versions rather than the simple copying, pass-by-value function parameter, which would let you pass in functors which are mutable and produce a result; by-value is fine as long as your functor has no member variables or constructor)
Or you could create iterators which represent the three traversals, allowing you to write the output using std::copy; however, this would be a lot more code and wouldn't be done just for that purpose. However, creating an iterator would allow large trees to be processed without stack overflow, as you would have to either have a 'parent' pointer in each node, or have the iterator maintain an explicit stack of visited nodes.
Although the function itself becomes very simple:
std::ostream_iterator<std::string>(std::cout, " ");
std::copy(d.begin(order), d.end(), out);
Using an iterator doesn't simplify the implementation, either in terms of loc or actually being able to follow what is going on:
#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;
}
I'd write it as three separate functions. This isn't simplification in terms of writing the code but simplification in terms of reading and understanding. You don't have look into the documentation every time to remember which int is which kind of traversal. (This gets remedied by using enums, of course.)
There is also a neglectable speed benefit with separating the if switches without using any kind of template magick. Keep it simple.
We can "reorder loops"
enum {post = 0x0101, in = 0x1001, pre = 0x1010};
template<typename T>
void traverse_binary_tree(BinaryTreeNode<T>* root,int order = pre)
{
if( root == NULL ) return;
if(order & 0x0001) traverse_binary_tree(root->left,order);
if(order & 0x0100) traverse_binary_tree(root->right,order);
cout << root->data << " ";
if(order & 0x0010) traverse_binary_tree(root->left,order);
if(order & 0x1000) traverse_binary_tree(root->right,order);
}
But it's more of making it funnier than simplier. :-) However, code is duplicated two times here, instead of three.
To avoid "magic numbers" you may write it like this:
enum {
left_before = 1 << 0,
left_after = 1 << 1,
right_before = 1 << 2,
right_after = 1 << 3,
};
int const pre = left_after | right_after ;
int const in = left_before | right_after ;
int const post = left_before | right_before;
/* The function body is fixed in the same way */
"Simple" is a matter of opinion. Apart from some stylistic matters (particularly using magic numbers rather than named constants), that's about as simple as you can get, given the spefication "traverse the tree and print its contents, giving a choice of order".
However, you can get more flexibility by separating out the two concerns: traversing the tree, and doing some operation on the data. You may want to analyse and manipulate the data in various ways as well as print it, and it's better not to duplicate the traversal logic for each operation. Instead, you could add extra template parameters to allow arbitrary combinations of pre-, post-, or in-order operations, along the lines of this:
// PRE, IN and POST operations are unary function objects which can
// take Node<T>* as their argument
template <typename T, typename PRE, typename IN, typename POST>
void traverse(Node<T>* root, PRE& pre, IN& in, POST& post)
{
if (!root) return;
pre(root);
traverse(root->left, pre, in, post);
in(root);
traverse(root->right, pre, in, post);
post(root);
}
// This can be used as a template argument to denote "do nothing".
struct Nothing { void operator()(void*) {} } nothing;
// Usage example - print the nodes, pre-ordered
void print(Node<int>* node) {std::cout << node->data << " ";}
traverse(root, print, nothing, nothing);
// Usage example - find the sum of all the nodes
struct Accumulator
{
Accumulator() : sum(0) {}
void operator()(Node<int>* node) {sum += node->data;}
int sum;
};
Accumulator a;
traverse(root, a, nothing, nothing);
std::cout << a.sum << std::endl;
I would probably so something like this: enum TraversalOrder{PreOrder, InOrder, PostOrder};
template<typename T>
void traverse_binary_tree_preorder(BinaryTreeNode<T>* root)
{
if( !root ) return;
cout << root->data << " ";
traverse_binary_tree_preorder(root->left,order);
traverse_binary_tree_preorder(root->right,order);
}
template<typename T>
void traverse_binary_tree_inorder(BinaryTreeNode<T>* root)
{
if( !root ) return;
traverse_binary_tree_inorder(root->left,order);
cout << root->data << " ";
traverse_binary_tree_inorder(root->right,order);
}
template<typename T>
void traverse_binary_tree_postorder(BinaryTreeNode<T>* root)
{
if( !root ) return;
traverse_binary_tree_postorder(root->left,order);
traverse_binary_tree_postorder(root->right,order);
cout << root->data << " ";
}
template<typename T>
void traverse_binary_tree(BinaryTreeNode<T>* root,TraversalOrder order = InOrder)
{
switch(order)
{
case PreOrder:
return traverse_binary_tree_preorder(root);
case PostOrder:
return traverse_binary_tree_postorder(root);
default:
return traverse_binary_tree_inorder(root);
}
}
Each function is as simple as you can get, and you can call the direct traversal function you want if you know at compile time which one you need.