Binary Tree

binarytree.cpp

#include <iostream>
#include <vector>
using namespace std;

template <class T> class TreeTraversal;

template <class T>
class TreeNode
{
public:
	T value;
	TreeNode<T> *lchild;
	TreeNode<T> *rchild;
	TreeNode<T> *parent;
	TreeNode<T> *next_sibling;
	TreeTraversal<T> *traverse_strategy;

	TreeNode(void):rchild(NULL), lchild(NULL), next_sibling(NULL), parent(this){};

	TreeNode(T value):TreeNode()
	{
		this->value = value;
	}

	bool setTraversal(TreeTraversal<T> *t)
	{
		this->traverse_strategy = t;
	}

	bool traverse(bool (*func)(TreeNode<T> *))
	{
		this->traverse_strategy->traverse(this,func);
		return true;
	}


	virtual bool addNode(T value) = 0;
//	bool delNode(T value) = 0;
};

template <class T>
class BinarySearchTreeNode: public TreeNode<T>
{
public:

	BinarySearchTreeNode(void):TreeNode<T>()
	{
	}

	BinarySearchTreeNode(T value):TreeNode<T>(value)
	{
	}
	bool addNode(BinarySearchTreeNode<T> *node)
	{
		if (node->value < this->value)
		{
			if (this->lchild)
				static_cast<BinarySearchTreeNode<T>*>(this->lchild)->addNode(node);
			else
				this->lchild = node;
		}
		else
		{
			if (this->rchild)
				static_cast<BinarySearchTreeNode<T>*>(this->rchild)->addNode(node);
			else
				this->rchild = node;
		}
	}

	bool addNode(T value)
	{
		BinarySearchTreeNode<T> *node = new BinarySearchTreeNode<T>(value);
		addNode(node);
	}

};

template <class T>
class TreeTraversal
{
public:
	virtual void traverse( TreeNode<T> *t, bool (*func)(TreeNode<T> *)) = 0;
};

template <class T>
class InorderTraversal: public TreeTraversal<T>
{
public:
	void traverse( TreeNode<T> *t, bool (*func)(TreeNode<T> *))
	{
		if (t->lchild)
		{
			traverse(t->lchild, func);
		}

		func(t);

		if (t->rchild)
		{
			traverse(t->rchild, func);
		}
	}
};

template <class T>
class PreorderTraversal: public TreeTraversal<T>
{
public:
	void traverse( TreeNode<T> *t, bool (*func)(T *))
	{

		func(t);

		if (t->lchild)
		{
			traverse(t->lchild, func);
		}

		if (t->rchild)
		{
			traverse(t->rchild, func);
		}
	}
};

template <class T>
class PostorderTraversal: public TreeTraversal<T>
{
public:
	void traverse( TreeNode<T> *t, bool (*func)(T *))
	{

		if (t->lchild)
		{
			traverse(t->lchild, func);
		}

		if (t->rchild)
		{
			traverse(t->rchild, func);
		}

		func(t);

	}
};


int main()
{
	BinarySearchTreeNode<int> *node = new BinarySearchTreeNode<int>(10);
	InorderTraversal<int> *t = new InorderTraversal<int>();
	node->addNode(100);
	node->addNode(5);
	node->setTraversal(t);
	node->traverse([](TreeNode<int>*n){ cout << n->value <<endl; return true;});
}