#include 
#include 
using namespace std;
#include 
#include 

template
struct BinaryTreeNode
{
	BinaryTreeNode* _left;
	BinaryTreeNode* _right;
	T _data;

	BinaryTreeNode(const T& x)
		:_left(NULL)
		,_right(NULL)
		,_data(x)
	{}
};

template
class BinaryTree
{
public:
	BinaryTree()
		:_root(NULL)
	{}

	BinaryTree(const T* a, size_t size, const T& invalid)
	{
		size_t index = 0;
		_root = _CreateTree(a, size, index, invalid);
	}

	~BinaryTree()
	{
		_DestroyTree(_root);
		_root = NULL;
	}

	BinaryTree(const BinaryTree& t)
	{
		_root = _CopyTree(t._root);
	}

	//赋值运算符重载的传统写法
	/*BinaryTree& operator=(const BinaryTree& t)
	{
		if (this != &t)
		{
			_DestroyTree(_root);
			_root = _CopyTree(t._root);
		}

		return *this;
	}*/

	//赋值运算符重载的现代写法
	BinaryTree& operator=(BinaryTree t)
	{
		swap(_root, t._root);

		return *this;
	}

	//递归前序遍历
	void PreOrderTraverse()
	{
		_PreOrderTraverse(_root);

		cout<*> q;
		q.push(_root);
		while (!q.empty())
		{
			BinaryTreeNode* front = q.front();
			q.pop();
			cout<_left)
			{
				q.push(front->_left);
			}

			if (front->_right)
			{
				q.push(front->_right);
			}
		}
	}
	
	//非递归前序遍历
	void PreOrderTraverse_NonR()
	{
		if (NULL == _root)
		{
			return;
		}

		stack*> s;
		s.push(_root);

		while (!s.empty())//当栈为空时遍历完成
		{
			//先访问根节点
			BinaryTreeNode* top = s.top();
			s.pop();
			cout<_data<<" ";

			//右节点存在时先入栈，后出栈
			if (top->_right)
			{
				s.push(top->_right);
			}

			//左结点存在时后入栈，先出栈
			if (top->_left)
			{
				s.push(top->_left);
			}
		}

		cout<*> s;
		BinaryTreeNode* cur = _root;

		while (cur || !s.empty())
		{
			//左结点全部入栈
			while (cur)
			{
				s.push(cur);
				cur = cur->_left;
			}

			if (!s.empty())
			{
				BinaryTreeNode* top = s.top();
				cout<_data<<" ";
				s.pop();

				cur = top->_right;//将栈顶结点的右节点看作子树的根节点
			}
		}

		cout<*> s;
		BinaryTreeNode* cur = _root;
		BinaryTreeNode* pre = NULL;

		while (cur || !s.empty())//当前结点为空和栈为空同时满足时遍历完成
		{
			//左结点全部入栈
			while (cur)
			{
				s.push(cur);
				cur = cur->_left;
			}

			BinaryTreeNode* top = s.top();

			if (NULL == top->_right || pre == top->_right)//若当前结点的右结点为空或者右节点已经访问过，可以访问该结点
			{
				cout<_data<<" ";
				pre = top;
				s.pop();
			}
			else//该结点的右节点不为空且未被访问
			{
				cur = top->_right;//将该结点的右节点看作子树的根节点
			}
		}

		cout<* _CreateTree(const T* a, size_t size, size_t& index, const T& invalid)
	{
		BinaryTreeNode* root = NULL;

		if (index < size && a[index] != invalid)
		{
			root = new BinaryTreeNode(a[index]);
			root->_left = _CreateTree(a, size, ++index, invalid);
			root->_right = _CreateTree(a, size, ++index, invalid);
		}

		return root;
	}
	
	void _DestroyTree(BinaryTreeNode* root)
	{
		if (NULL == root)
		{
			return;
		}

		if (NULL == root->_left && NULL == root->_right)
		{
			delete root;
			root = NULL;
			return;
		}

		_DestroyTree(root->_left);
		_DestroyTree(root->_right);
		delete root;
	}

	BinaryTreeNode* _CopyTree(BinaryTreeNode* root)
	{
		if (NULL == root)
		{
			return NULL;
		}

		BinaryTreeNode* newRoot = new BinaryTreeNode(root->_data);
		newRoot->_left = _CopyTree(root->_left);
		newRoot->_right = _CopyTree(root->_right);

		return newRoot;
	}

	void _PreOrderTraverse(BinaryTreeNode* root)
	{
		if (NULL == root)
		{
			return;
		}

		cout<_data<<" ";
		_PreOrderTraverse(root->_left);
		_PreOrderTraverse(root->_right);
	}

	void _InOrderTraverse(BinaryTreeNode* root)
	{
		if (NULL == root)
		{
			return;
		}

		_InOrderTraverse(root->_left);
		cout<_data<<" ";
		_InOrderTraverse(root->_right);
	}

	void _PostOrderTraverse(BinaryTreeNode* root)
	{
		if (NULL == root)
		{
			return;
		}

		_PostOrderTraverse(root->_left);
		_PostOrderTraverse(root->_right);
		cout<_data<<" ";
	}

	//_Size方法1：
	/*size_t _Size(BinaryTreeNode* root)
	{
		if (NULL == root)
		{
			return;
		}

		return _Size(root->left) + _Size(root->_right) + 1;
	}*/

	//_Size方法2：（存在线程安全问题）
	/*size_t _Size(BinaryTreeNode* root)
	{
		static size_t size = 0;
		if (NULL == root)
		{
			return 0;
		}
		else
		{
			++size;
		}

		_Size(root->_left);
		_Size(root->_right);

		return size;
	}*/

	//_Size方法3：
	void _Size(BinaryTreeNode* root, size_t& size)
	{
		if (NULL == root)
		{
			return;
		}
		else
		{
			++size;
		}

		_Size(root->_left, size);
		_Size(root->_right, size);
	}

	size_t _Depth(BinaryTreeNode* root)
	{
		if (NULL == root)
		{
			return 0;
		}

		size_t leftDepth = _Depth(root->_left);
		size_t rightDepth = _Depth(root->_right);

		return leftDepth > rightDepth ? leftDepth+1 : rightDepth+1;
	}

	void _LeafSize(BinaryTreeNode* root, size_t& leafSize)
	{
		if (NULL == root)
		{
			return;
		}

		if (NULL == root->_left && NULL == root->_right)
		{
			++leafSize;
			return;
		}

		_LeafSize(root->_left, leafSize);
		_LeafSize(root->_right, leafSize);
	}

	size_t _GetKLevel(BinaryTreeNode* root, const size_t& k)
	{
		assert(k > 0);

		if (NULL == root)
		{
			return 0;
		}

		if (k == 1)
		{
			return 1;
		}

		return _GetKLevel(root->_left, k-1) + _GetKLevel(root->_right, k-1);
	}
protected:
	BinaryTreeNode* _root;
};

void BinaryTreeTest()
{
	int a[] = {1, 2, 3, '#', '#', 4, '#', '#', 5, 6};
	BinaryTree t(a, sizeof(a)/sizeof(a[0]), '#');

	cout<<"递归前序遍历：";
	t.PreOrderTraverse();
	cout<<"递归中序遍历：";
	t.InOrderTraverse();
	cout<<"递归后序遍历：";
	t.PostOrderTraverse();
	cout<<"非递归前序遍历：";
	t.PreOrderTraverse_NonR();
	cout<<"非递归中序遍历：";
	t.InOrderTraverse_NonR();
	cout<<"非递归后序遍历：";
	t.PostOrderTraverse_NonR();

	cout<<"Size:"< t2(t);
	cout<<"t2:";
	t2.PreOrderTraverse();

	BinaryTree t3;
	t3 = t2;
	cout<<"t3:";
	t3.PreOrderTraverse();
}

int main()
{
	BinaryTreeTest();

	return 0;
}

生成的二叉树如下图：

为天坛街道等地区用户提供了全套网页设计制作服务，及天坛街道网站建设行业解决方案。主营业务为成都网站建设、做网站、天坛街道网站设计，以传统方式定制建设网站，并提供域名空间备案等一条龙服务，秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求，就会得到认可，从而选择与我们长期合作。这样，我们也可以走得更远！

测试结果：

本文标题：C++实现二叉树
URL分享：http://myzitong.com/article/ihojpo.html