The Big Programming Thread - Page 77

#include <cstdio>
#include <iostream>
#include <queue>

#define null NULL
#define int32 int

using namespace std;

/**
*	Binary tree node class
**/

template <class T>
class Node
{
	public:

	/*	Public Constructors	*/

		Node () :
			left (null),
			right (null),
			value ()
		{}

		explicit Node (T x) :
			left (null),
			right (null),
			value (x)
		{}

	/*	Public Attributes	*/

		Node* left;
		Node* right;
		T value;

};

/**
*	This exception is thrown when the flattener & cycle detector algorithm encounters a cycle
**/

class CycleException
{

	public:

	/*	Public Constructors	*/

		CycleException () {}
		virtual ~CycleException () {}

};

/**
*	This functions flattens an alleged binary tree, throwing a new CycleException when encountering a cycle. Returns the root of the flattened binary tree.
**/

template <class T>
Node<T>* flatten (Node<T>* current)
{
	//	Count steps (well, kinda) to determine runtime
	int32 steps = 0;
	//	Keep track of the root node so the tree is not lost
	Node<T>* root = current;
	//	Keep track of the parent of the current node since it is needed for insertions
	Node<T>* parent = null;

	//	Loop while there are subtrees to process 
	while( current->left != null or current->right != null ){

		steps++;

		//	There is a left subtree, so current has a predecessor, which we will call "bottom" of the subtree
		if( current->left != null ){
			Node<T>* top = current->left;
			Node<T>* bottom;
			//	The top and the bottom is one and the same
			if( top->right == null ){
				bottom = top;
			}
			//	The bottom is buried in the right subtree of top
			if( top->right != null ){
				//	Find it using Floyd's cycle detection algorithm applied to right childs
				Node<T>* turtle = top;
				Node<T>* hare = top->right;
				while( hare->right != null ){
					if( turtle == hare ){
						throw new CycleException();
					}
					if( hare->right != null ){
						steps++;
						hare = hare->right;
					}
					if( hare->right != null ){
						steps++;
						hare = hare->right;
					}
					turtle = turtle->right;
				}
				bottom = hare;
			}
			//	Remove subtree from current
			current->left = null;
			//	Insert subtree between the current node and its parent, if there is any
			if( parent != null ){
				parent->right = top;
			}
			bottom->right = current;
			//	If the current node is the root then the top is the new root
			if( root == current ){
				root = top;
			}
			//	Step up to process the top, parent remains the same
			current = top;
			continue;
		}

		//	There is only a right subtree, Floyd's cycle detection algorithm must be applied to find a node that has a left subtree
		if( current->left == null and current->right != null ){
			cout << "Visited " << dec << current->value << " @ 0x" << hex << reinterpret_cast<int32>(current) << endl;
			Node<T>* hare = current->right;
			Node<T>* hareParent = current;
			Node<T>* turtle = current;
			while( hare->left == null and hare->right != null ){
				if( turtle == hare ){
					throw new CycleException();
				}
				if( hare->left == null and hare->right != null ){
					cout << "Visited " << dec << hare->value << " @ 0x" << hex << reinterpret_cast<int32>(hare) << endl;
					steps++;
					hare = hare->right;
					hareParent = hareParent->right;
				}
				if( hare->left == null and hare->right != null ){
					cout << "Visited " << dec << hare->value << " @ 0x" << hex << reinterpret_cast<int32>(hare) << endl;
					steps++;
					hare = hare->right;
					hareParent = hareParent->right;
				}
				turtle = turtle->right;
			}
			current = hare;
			parent = hareParent;
			continue;
		}

	}

	cout << "Visited " << dec << current->value << " @ 0x" << hex << reinterpret_cast<int32>(current) << endl;
	cout << "Steps taken: " << dec << steps << endl;

	//	there are no more subtrees to process, we are finished, the tree does not contain cycles
	return root;

}

template <class T>
void traverseFlat (Node<T>* current)
{
	while( current != null ){
		cout << dec << current->value << " @ 0x" << hex << reinterpret_cast<int32>(current) << endl;
		current = current->right;
	}
}

template <class T>
Node<T>* makeCompleteBinaryTree (int32 maxNodes)
{
	Node<T>* root = new Node<T>();
	queue<Node<T>*> q;
	q.push(root);
	int32 nodes = 1;
	while( nodes < maxNodes ){
		Node<T>* node = q.front();
		q.pop();
		node->left = new Node<T>();
		q.push(node->left);
		nodes++;
		if( nodes < maxNodes ){
			node->right = new Node<T>();
			q.push(node->right);
			nodes++;
		}
	}
	return root;
}

template <class T>
void inorderLabel (Node<T>* root)
{
	int32 label = 0;
	inorderLabel(root, label);
}

template <class T>
void inorderLabel (Node<T>* root, int32& label)
{
	if( root == null ){
		return;
	}
	inorderLabel(root->left, label);
	root->value = label++;
	inorderLabel(root->right, label);
}


int32 main (int32 argc, char* argv[])
{
	if(argc||argv){}

	typedef Node<int32> Node;

	//	Make binary tree and label it in-order
	Node* root = makeCompleteBinaryTree<int32>(1 << 16);
	inorderLabel(root);

	//	Try to flatten it
	try{
		root = flatten(root);
	}catch(CycleException*){
		cout << "Oh noes, cycle detected!" << endl;
		return 0;
	}

	//	Traverse its flattened form
	traverseFlat(root);

}