C++实现二叉树

#include <assert.h>
#include <iostream>
using namespace std;
#include <stack>
#include <queue>

template<class T>
struct BinaryTreeNode
{
	BinaryTreeNode<T>* _left;
	BinaryTreeNode<T>* _right;
	T _data;

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

template<class T>
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>& t)
	{
		_root = _CopyTree(t._root);
	}

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

		return *this;
	}*/

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

		return *this;
	}

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

		cout<<endl;
	}

	//递归中序遍历
	void InOrderTraverse()
	{
		_InOrderTraverse(_root);

		cout<<endl;
	}

	//递归后序遍历
	void PostOrderTraverse()
	{
		_PostOrderTraverse(_root);

		cout<<endl;
	}

	//非递归层序遍历
	void LevelOrderTraverse()
	{
		if (NULL == _root)
		{
			return;
		}

		queue<BinaryTreeNode<T>*> q;
		q.push(_root);
		while (!q.empty())
		{
			BinaryTreeNode<T>* front = q.front();
			q.pop();
			cout<<front._data<<" ";

			if (front->_left)
			{
				q.push(front->_left);
			}

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

		stack<BinaryTreeNode<T>*> s;
		s.push(_root);

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

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

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

		cout<<endl;
	}

	//非递归中序遍历
	void InOrderTraverse_NonR()
	{
		if (NULL == _root)
		{
			return;
		}

		stack<BinaryTreeNode<T>*> s;
		BinaryTreeNode<T>* cur = _root;

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

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

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

		cout<<endl;
	}

	//非递归后序遍历
	void PostOrderTraverse_NonR()
	{
		if (NULL == _root)
		{
			return;
		}

		stack<BinaryTreeNode<T>*> s;
		BinaryTreeNode<T>* cur = _root;
		BinaryTreeNode<T>* pre = NULL;

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

			BinaryTreeNode<T>* top = s.top();

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

		cout<<endl;
	}

	//求结点数
	size_t Size()
	{
		size_t size = 0;
		_Size(_root, size);
		return size;
	}

	//求深度
	size_t Depth()
	{
		return _Depth(_root);
	}

	//求叶子结点数
	size_t LeafSize()
	{
		size_t leafSize = 0;
		_LeafSize(_root, leafSize);
		return leafSize;
	}

	//求第K层结点数
	size_t GetKLevel(const size_t& k)
	{
		 return _GetKLevel(_root, k);
	}
protected:
	BinaryTreeNode<T>* _CreateTree(const T* a, size_t size, size_t& index, const T& invalid)
	{
		BinaryTreeNode<T>* root = NULL;

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

		return root;
	}
	
	void _DestroyTree(BinaryTreeNode<T>* 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<T>* _CopyTree(BinaryTreeNode<T>* root)
	{
		if (NULL == root)
		{
			return NULL;
		}

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

		return newRoot;
	}

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

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

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

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

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

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

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

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

	//_Size方法2：（存在线程安全问题）
	/*size_t _Size(BinaryTreeNode<T>* 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<T>* root, size_t& size)
	{
		if (NULL == root)
		{
			return;
		}
		else
		{
			++size;
		}

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

	size_t _Depth(BinaryTreeNode<T>* 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<T>* 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<T>* 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<T>* _root;
};

void BinaryTreeTest()
{
	int a[] = {1, 2, 3, '#', '#', 4, '#', '#', 5, 6};
	BinaryTree<int> 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:"<<t.Size()<<endl;
	cout<<"Depth:"<<t.Depth()<<endl;
	cout<<"LeafSize:"<<t.LeafSize()<<endl;
	cout<<"Get3Level:"<<t.GetKLevel(3)<<endl;

	BinaryTree<int> t2(t);
	cout<<"t2:";
	t2.PreOrderTraverse();

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

int main()
{
	BinaryTreeTest();

	return 0;
}

生成的二叉树如下图：

测试结果：