Twelve ways to traverse a binary tree

Binary_Tree.cpp

#include <iostream>
#define DEBUG
#include "Binary_Tree.h"

int compare_int(int a, int b){
	if(a < b){
		return -1;
	} else if (a == b){
		return 0;
	} else {
		return 1;
	}
}

void print(int n){
	std::cout << n << " ";
}

int main(){
	Binary_Tree<int, compare_int> tree;
	tree.insert(6);
	tree.insert(5);
	tree.insert(7);
	tree.insert(1);
	tree.insert(2);
	tree.insert(9);
	tree.insert(10);
	tree.insert(3);
	tree.insert(8);
	tree.insert(4);
	tree.print(std::cout);
	
	std::cout << "-----Preorder-----" << std::endl;
	std::cout << "Recursive (Centralized):\t";
	std::cout << "[ ";
	tree.preorder_recursive_centralized(print);
	std::cout << "]" << std::endl;
	
	std::cout << "Recursive (Decentralized):\t";
	std::cout << "[ ";
	tree.preorder_recursive_decentralized(print);
	std::cout << "]" << std::endl;
	
	std::cout << "Iterative (Stack Based):\t";
	std::cout << "[ ";
	tree.preorder_iterative_stack_based(print);
	std::cout << "]" << std::endl;
	
	std::cout << "Iterative (Stack Free):\t\t";
	std::cout << "[ ";
	tree.preorder_iterative_stack_free(print);
	std::cout << "]" << std::endl;
	
	
	
	
	
	std::cout << "-----Inorder-----" << std::endl;
	std::cout << "Recursive (Centralized):\t";
	std::cout << "[ ";
	tree.inorder_recursive_centralized(print);
	std::cout << "]" << std::endl;
	
	std::cout << "Recursive (Decentralized):\t";
	std::cout << "[ ";
	tree.inorder_recursive_decentralized(print);
	std::cout << "]" << std::endl;
	
	std::cout << "Iterative (Stack Based):\t";
	std::cout << "[ ";
	tree.inorder_iterative_stack_based(print);
	std::cout << "]" << std::endl;
	
	std::cout << "Iterative (Stack Free):\t\t";
	std::cout << "[ ";
	tree.inorder_iterative_stack_free(print);
	std::cout << "]" << std::endl;
	
	
	
	
	
	std::cout << "-----Postorder-----" << std::endl;
	std::cout << "Recursive (Centralized):\t";
	std::cout << "[ ";
	tree.postorder_recursive_centralized(print);
	std::cout << "]" << std::endl;
	
	std::cout << "Recursive (Decentralized):\t";
	std::cout << "[ ";
	tree.postorder_recursive_decentralized(print);
	std::cout << "]" << std::endl;
	
	std::cout << "Iterative (Stack Based):\t";
	std::cout << "[ ";
	tree.postorder_iterative_stack_based(print);
	std::cout << "]" << std::endl;
	
	
	
	
	
	std::cout << "-----Levelorder-----" << std::endl;
	std::cout << "Iterative (Queue Based):\t";
	std::cout << "[ ";
	tree.levelorder(print);
	std::cout << "]" << std::endl;
	return 0;
}
/*
 *	Output:
 *	6 Left: 5 Right: 7
 *	5 Left: 1
 *	1 Right: 2
 *	2 Right: 3
 *	3 Right: 4
 *	4
 *	7 Right: 9
 *	9 Left: 8 Right: 10
 *	8
 *	10
 *	-----Preorder-----
 *	Recursive (Centralized):        [ 6 5 1 2 3 4 7 9 8 10 ]
 *	Recursive (Decentralized):      [ 6 5 1 2 3 4 7 9 8 10 ]
 *	Iterative (Stack Based):        [ 6 5 1 2 3 4 7 9 8 10 ]
 *	Iterative (Stack Free):         [ 6 5 1 2 3 4 7 9 8 10 ]
 *	-----Inorder-----
 *	Recursive (Centralized):        [ 1 2 3 4 5 6 7 8 9 10 ]
 *	Recursive (Decentralized):      [ 1 2 3 4 5 6 7 8 9 10 ]
 *	Iterative (Stack Based):        [ 1 2 3 4 5 6 7 8 9 10 ]
 *	Iterative (Stack Free):         [ 1 2 3 4 5 6 7 8 9 10 ]
 *	-----Postorder-----
 *	Recursive (Centralized):        [ 4 3 2 1 5 8 10 9 7 6 ]
 *	Recursive (Decentralized):      [ 4 3 2 1 5 8 10 9 7 6 ]
 *	Iterative (Stack Based):        [ 4 3 2 1 5 8 10 9 7 6 ]
 *	-----Levelorder-----
 *	Iterative (Queue Based):        [ 6 5 7 1 9 2 8 10 3 4 ]
*/

Binary_Tree.h

#ifndef _BINARY_TREE_H_
#define _BINARY_TREE_H_

#include <stack>
#include <queue>

template <typename T>
class Node{
	public:
		T data;
		Node *left;
		Node *right;
		Node(T data);
		~Node();
		void preorder(void (*process)(T));
		void inorder(void (*process)(T));
		void postorder(void (*process)(T));
};

template <typename T>
Node<T>::Node(T data) : data(data), left(nullptr), right(nullptr){}

template <typename T>
Node<T>::~Node(){
	if(left)
		delete left;
	if(right)
		delete right;
}

template <typename T>
void Node<T>::preorder(void (*process)(T)){
	process(data);
	if(left) left->preorder(process);
	if(right) right->preorder(process);
}

template <typename T>
void Node<T>::inorder(void (*process)(T)){
	if(left) left->inorder(process);
	process(data);
	if(right) right->inorder(process);
}

template <typename T>
void Node<T>::postorder(void (*process)(T)){
	if(left) left->postorder(process);
	if(right) right->postorder(process);
	process(data);
}







template <typename T, int (*F)(T,T)>
class Binary_Tree{
	Node<T> *root;
	//preorder
	void do_preorder_recursive_centralized(void (*process)(T), Node<T> *node);
	
	//inorder
	void do_inorder_recursive_centralized(void (*process)(T), Node<T> *node);
	
	//postorder
	void do_postorder_recursive_centralized(void (*process)(T), Node<T> *node);
	
	public:
		Binary_Tree<T, F>();
		~Binary_Tree<T, F>();
		void insert(T new_value);
		
		
		//preorder
		void preorder_recursive_centralized(void (*process)(T));
		void preorder_recursive_decentralized(void (*process)(T));
		void preorder_iterative_stack_based(void (*process)(T));
		void preorder_iterative_stack_free(void (*process)(T));
		
		//inorder
		void inorder_recursive_centralized(void (*process)(T));
		void inorder_recursive_decentralized(void (*process)(T));
		void inorder_iterative_stack_based(void (*process)(T));
		void inorder_iterative_stack_free(void (*process)(T));
		
		//postorder
		void postorder_recursive_centralized(void (*process)(T));
		void postorder_recursive_decentralized(void (*process)(T));
		void postorder_iterative_stack_based(void (*process)(T));
		
		//levelorder
		void levelorder(void (*process)(T));
		
		#ifdef DEBUG
		std::ostream& print(std::ostream &out);
		std::ostream& do_print(std::ostream &out, Node<T> *curr);
		#endif
};

template <typename T, int (*F)(T,T)>
Binary_Tree<T,F>::Binary_Tree() : root(nullptr){}

template <typename T, int (*F)(T,T)>
Binary_Tree<T,F>::~Binary_Tree(){
	delete root;
}

template <typename T, int (*F)(T,T)>
void Binary_Tree<T,F>::insert(T new_value){
	if(!root){
		root = new Node<T>(new_value);
		return;
	}
	Node<T> *curr = root;
	while(curr){
		if(F(new_value, curr->data) < 0) {
			if(curr->left == nullptr){
				curr->left = new Node<T>(new_value);
				return;
			} else {
				curr = curr->left;
			}
		} else {
			if(curr->right == nullptr){
				curr->right = new Node<T>(new_value);
				return;
			} else {
				curr = curr->right;
			}
		}
	}
}

//-------------------------
//       Preorder
//-------------------------
//centralized recursive
template <typename T, int (*F)(T,T)>
void Binary_Tree<T, F>::preorder_recursive_centralized( void (*process)(T) ){
	if(root) do_preorder_recursive_centralized(process, root);
}
template <typename T, int(*F)(T,T)>
void Binary_Tree<T, F>::do_preorder_recursive_centralized( void (*process)(T), Node<T> *node ){
	process(node->data);
	if(node->left) do_preorder_recursive_centralized(process, node->left);
	if(node->right) do_preorder_recursive_centralized(process, node->right);
}

//decentralized recursive
template <typename T, int (*F)(T,T)>
void Binary_Tree<T, F>::preorder_recursive_decentralized(void (*process)(T)){
	if(root) root->preorder(process);
}

//stack-based iterative
template <typename T, int (*F)(T,T)>
void Binary_Tree<T, F>::preorder_iterative_stack_based(void (*process)(T)){
	std::stack<Node<T>*> stack;
	stack.push(root);
	while(!stack.empty()){
		Node<T> *curr = stack.top();
		stack.pop();
		process(curr->data);
		if(curr->right) stack.push(curr->right);
		if(curr->left) stack.push(curr->left);
	}
}

//stack-free iterative
template <typename T, int (*F)(T,T)>
void Binary_Tree<T, F>::preorder_iterative_stack_free(void (*process)(T)){
	Node<T> *anchor = root;
	while(anchor){
		if(!anchor->left){
			process(anchor->data);
			anchor = anchor->right;
		} else {
			Node<T>* iop = anchor->left;
			while( iop && iop->right && ( F(iop->right->data, anchor->data) != 0 ) ) iop = iop->right;
			if(iop->right != anchor){
				process(anchor->data);
				iop->right = anchor;
				anchor = anchor->left;
			} else {
				iop->right = nullptr;
				anchor = anchor->right;
			}
		}
	}
}




//-------------------------
//        Inorder
//-------------------------
//centralized recursive
template <typename T, int (*F)(T,T)>
void Binary_Tree<T, F>::inorder_recursive_centralized( void (*process)(T) ){
	if(root) do_inorder_recursive_centralized(process, root);
}
template <typename T, int (*F)(T,T)>
void Binary_Tree<T, F>::do_inorder_recursive_centralized( void (*process)(T), Node<T> *node){
	if(node->left) do_inorder_recursive_centralized(process, node->left);
	process(node->data);
	if(node->right) do_inorder_recursive_centralized(process, node->right);
}

//decentralzied recursive
template <typename T, int (*F)(T,T)>
void Binary_Tree<T, F>::inorder_recursive_decentralized(void (*process)(T)){
	if(root) root->inorder(process);
}

//stack-based iterative
template <typename T, int (*F)(T,T)>
void Binary_Tree<T,F>::inorder_iterative_stack_based(void (*process)(T)){
	std::stack<Node<T>*> stack;
	Node<T>* curr = root;
	while(curr || !stack.empty()){
		if(curr){
			stack.push(curr);
			curr = curr->left;
		} else {
			curr = stack.top();
			process(curr->data);
			stack.pop();
			curr = curr->right;
		}
	}
}

//stack-free iterative
template <typename T, int (*F)(T,T)>
void Binary_Tree<T, F>::inorder_iterative_stack_free(void (*process)(T)){
	Node<T> *anchor = root;
	while(anchor){
		if(!anchor->left){
			process(anchor->data);
			anchor = anchor->right;
		} else {
			Node<T> *iop = anchor->left;
			while( iop && iop->right && (F(iop->right->data, anchor->data) != 0) ) iop = iop->right;
			if(iop->right != anchor){
				iop->right = anchor;
				anchor = anchor->left;
			} else {
				process(anchor->data);
				iop->right = nullptr;
				anchor = anchor->right;
			}
		}
	}
}


//-------------------------
//       Postorder
//-------------------------
//centralized
template <typename T, int (*F)(T,T)>
void Binary_Tree<T, F>::postorder_recursive_centralized( void (*process)(T) ){
	if(root) do_postorder_recursive_centralized(process, root);
}
template <typename T, int (*F)(T,T)>
void Binary_Tree<T, F>::do_postorder_recursive_centralized( void (*process)(T), Node<T> *node ){
	if(node->left) do_postorder_recursive_centralized( process, node->left);
	if(node->right) do_postorder_recursive_centralized( process, node->right);
	process(node->data);
}

//decentralized
template <typename T, int (*F)(T,T)>
void Binary_Tree<T, F>::postorder_recursive_decentralized(void (*process)(T)){
	if(root) root->postorder(process);
}

//stack-based iterative
template <typename T, int(*F)(T,T)>
void Binary_Tree<T, F>::postorder_iterative_stack_based(void (*process)(T)){
	std::stack<Node<T>*> stack;
	stack.push(root);
	Node<T> *curr = nullptr;
	Node<T> *prev = nullptr;
	while(!stack.empty()){
		curr = stack.top();
		//traversing downwards
		if(prev == nullptr || prev->left == curr || prev->right == curr){
			if(curr->left){
				stack.push(curr->left);
			}
			else if(curr->right){
				stack.push(curr->right);
			}
		//traversing upwards on the left side
		} else if (curr->left == prev){
			if(curr->right){
				stack.push(curr->right);
			}
		//traversing upwards on the right side
		} else {
			process(curr->data);
			stack.pop();
		}
		prev = curr;
	}
}






//-------------------------
//       Levelorder
//-------------------------
template <typename T, int(*F)(T,T)>
void Binary_Tree<T, F>::levelorder(void (*process)(T)){
	std::queue<Node<T>*> queue;
	queue.push(root);
	while(!queue.empty()){
		Node<T>* node = queue.front();
		queue.pop();
		process(node->data);
		if(node->left) queue.push(node->left);
		if(node->right) queue.push(node->right);
	}
}







#ifdef DEBUG
template <typename T, int (*F)(T,T)>
std::ostream& Binary_Tree<T, F>::print(std::ostream &out){
	return do_print(out, root);
}

template <typename T, int (*F)(T,T)>
std::ostream& Binary_Tree<T, F>::do_print(std::ostream &out, Node<T> *node){
	//print the current node
	out << node->data;
	if(node->left) out << " Left: " << node->left->data;
	if(node->right) out << " Right: " << node->right->data;
	out << std::endl;
	
	//recursively print node's children
	if(node->left) do_print(out, node->left);
	if(node->right) do_print(out, node->right);
	
	return out;
}
#endif

#endif