上篇博客中，我们详细说明了树和二叉树的数据结构及其特征，本次，我们用C++来实现一下二叉树

定义二叉树节点结构

二叉树需要定义指向左孩子和右孩子节点的指针，还有存储的数据；我们在这把它的构造函数也写出来

//定义一个二叉树节点
template<typename T>
struct BinaryTreeNode
{
	T _data;//数据
	BinaryTreeNode<T> *_left;//左孩子
	BinaryTreeNode<T> *_right;//右孩子

	BinaryTreeNode(const T& x)//节点的构造函数
		:_data(x),_left(NULL),_right(NULL)
	{}
};

定义二叉树结构

在此，我们定义二叉树的结构，先实现他的构造、析构函数，拷贝构造函数和赋值运算符重载。

通过调用protected中实现Create、Copy、Destory三个递归函数来实现。

//定义二叉树
template<typename T>
class BinaryTree
{
	typedef BinaryTreeNode<T> Node;//重命名为Node
public:
	BinaryTree()
		:_root(NULL)
	{}
	BinaryTree(T* arr,const size_t size,const T& invalid = T())
	{
		assert(arr);
		size_t index = 0;
		_root = CreateTree(arr,size,index,invalid);//用递归的形式创建树，通过调用保护成员函数CreateTree() 
	}

	//拷贝构造函数
	BinaryTree(const BinaryTree& b)
	{
		_root = Copy(b._root);
	}

	//赋值运算符重载
	BinaryTree&operator=(BinaryTree t)
	{
		if (this != &t)
		{
			std::swap(t._root,_root);
		}
		return *this;
	}

	//析构函数
	~BinaryTree()
	{
		if (_root != NULL)
		{
			Destory(_root);
			_root = NULL;
		}
	}

	//先序遍历，中序遍历，后序遍历
	void PrevOrder();
	
	void InOrder();
	
	void PostOrder();

	//三种遍历方式的非递归形式
	void PrevOrderNonR();

	//中序遍历的非递归，只用把压栈访问元素的位置改到出栈的时候访问即可
	void InOrderNonR();

	//后序非递归遍历
	void PostOrderNonR();

	//层序遍历
	void LevelOrder();

	//求二叉树的节点个数
	size_t Size(); 

	//求二叉树的深度
	size_t Depth();

	//求二叉树的叶子节点
	size_t GetLeafSize();

	//求第K层节点的个数
	size_t GetKLevelSize(size_t k);
protected:
	Node* _root;
	
	//根据字符数组构建二叉树 
	Node* CreateTree(T* arr,size_t& index,const T& invalid = T())
	{ 
		//数组未完 并且 不为非法值 
		if (index < size && arr[index]!=invalid)
		{
			//生成节点递归构建 
			Node* root = new Node(arr[index]);
			root->_left = CreateTree(arr,++index,invalid);
			root->_right = CreateTree(arr,invalid);
			
			//返回生成的节点 
			return root;
		}
		
		//返回空 
		return NULL;
	}
	
	//递归销毁二叉树 
	void Destory(Node* root)
	{
		assert(root);
		
		//不为空，递归销毁左子树 
		if (root->_left != NULL)
			Destory(root->_left);
		
		//销毁完成赋值为NULL 
		root->_left = NULL;
		
		//不为空，递归销毁右子树 
		if (root->_right != NULL)
			Destory(root->_right);
		
		//销毁完成赋值为NULL 
		root->_right = NULL;
			
		//销毁当前节点 
		delete[] root;
		root = NULL;
		return;
	}
	
	//递归拷贝二叉树 
	Node* Copy(Node* root)
	{	
		//根为空 
		if (root == NULL)
			return NULL;
			
		//调用Node的构造函数 生成一个节点 
		Node* newnode = new Node(root->_data);
		
		//递归拷贝 
		newnode->_left = Copy(root->_left);
		newnode->_right = Copy(root->_right);
		return newnode;
	}
};

二叉树递归的遍历方法

（1）先序

这里都要采用递归的方法，通过调用protected成员函数 _PrevOrder来遍历

void PrevOrder()
{
	//采用递归方法，调用protected内部的_PrevOrder函数，中序和后序也是一样
	_PrevOrder(_root);
	cout << endl;
}

protected：

void _PrevOrder(Node* root)
{
	//节点为空，返回
        if (root == NULL)
		return;

        //先访问该节点
      cout << root->_data << " ";
        
        //递归访问左子树
      _PrevOrder(root->_left);
        //左子树访问完成后访问右子树
      _PrevOrder(root->_right);
}

（2）中序

同理，调用protected的_InOrder()

        void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
protected:
      void _InOrder(Node* root)
	{
                //节点为空返回
		if (root == NULL)
			return;
            
                //先访问左子树
		_InOrder(root->_left);

                //访问完成后访问该根节点
		cout << root->_data << " ";

                //访问右子树
		_InOrder(root->_right);
	}

（3）后序

       void PostOrder()
 {
  _PostOrder(_root);
  cout << endl;
 }
protected:
        void _PostOrder(Node* root)
	{
		if (root == NULL)
			return;

                //先访问左子树
		_PostOrder(root->_left);

                //左子树访问完了，访问右子树
		_PostOrder(root->_right);

                //左子树右子树访问完了，访问该节点
		cout << root->_data << " ";
	}

二叉树非递归的遍历方法

（1）先序

所有的递归程序都可以用非递归来实现；

简单的递归程序可以改成循环实现；

所有的递归程序都可以栈来实现；

所以我们现在要实用STL的栈

public:        
        void PrevOrderNonR()
	{
		//定义一个栈和一个指针变量
		stack<Node*> s;
		Node* cur = _root;

		//在cur,或者栈为空时
		while (cur || !s.empty())
		{
			//递归遍历左字数
			while (cur)
			{
				//访问元素
				cout << cur->_data << " ";
				
				//进行压栈
				s.push(cur);
				
				//指向左孩子
				cur = cur->_left;
			}
			//一路向左，此时cur为空

			//取栈顶元素
			Node* top = s.top();
			//出栈
			s.pop();
			//访问右孩子
			cur = top->_right;
		}
		cout << endl;
	}

（2）中序

一样是用栈，只用改变访问元素的位置即可

public:
      //中序遍历的非递归，只用把压栈访问元素的位置改到出栈的时候访问即可
	void InOrderNonR()
	{
		//定义一个栈和指针变量cur
		Node* cur = _root;
		stack<Node*> s;

		//判断是否结束
		while (cur || !s.empty())
		{
			//循环压入左字数
			while (cur)
			{
				s.push(cur);

				//中序，先不要访问元素
				cur = cur->_left;
			}
			Node* top = s.top();
			s.pop();

			//此时再访问元素
			cout << top->_data << " ";
			cur = top->_right;
		}
	}

（3）后序

后序的话，出来需要判断右子树的访问情况，否则会出错

public:
        //后序非递归遍历
	void PostOrderNonR()
	{
		//与中序，先序相比，多定义了一个prev指针，保存上一个访问的元素
		Node* prev = NULL;

		//定义一个栈s和指向节点的临时变量cur
		Node* cur = _root;
		stack<Node*> s;

		//判断是否结束
		while (cur || !s.empty())
		{
			//递归压入左子树
			while (cur)
			{
				//依旧不访问元素
				s.push(cur);
				cur = cur->_left;
			}

			//取栈顶元素进行判断
			Node* top = s.top();

			//如果站定元素的右子树为空  或者  右子树已经被访问
			if (top->_right == NULL || top->_right == prev)
			{
				//打印根
				cout << top->_data << " ";
				
				//将刚刚访问过的元素让prev保存起来
				prev = top;

				//出栈
				s.pop();
			}
			//右子树不为空 并且 还没有被访问
			else
			{
				//访问右字数
				cur = top->_right;
			}
		}
	}

（4）层序

层序遍历，我们需要借助另一个数据结构---队列

每次将根节点入栈，出栈后将它的孩子入栈；

以此论推

public:        
        //层序遍历
	void LevelOrder()
	{
		if (_root == NULL)
			return;

		//利用队列来存储每一层的节点
		queue<Node*> q;
		//压入根节点
		q.push(_root);

		//队列为空，访问结束
		while (q.empty() == false)
		{
			//取队头元素，进行访问
			Node* tmp = q.front();
			cout << tmp->_data << " ";

			//弹出队列的首元素
			q.pop();

			//哪个孩子不为空，就压入该孩子
			if (tmp->_left != NULL)
				q.push(tmp->_left);
			if (tmp->_right != NULL)
				q.push(tmp->_right);
		}
		cout << endl;
	}

递归求深度、节点个数、叶子节点个数和第K层节点个数

public:        
        //求二叉树的节点个数
	size_t Size()
	{
		return _Size(_root);
	}

	//求二叉树的深度
	size_t Depth()
	{
		return _Depth(_root);
	}

	//求二叉树的叶子节点
	size_t GetLeafSize()
	{
		size_t count = 0;
		_GetLeafSize(_root,count);
		return count;
	}

	//求第K层节点的个数
	size_t GetKLevelSize(size_t k)
	{
		assert(k > 0);
		return _GetKLevelSize(_root,k);
	}

protected:
      size_t _Size(Node* root)
	{
		if (root == NULL)
			return 0;
                //递归求解子问题。返回左子树的节点个数+右子树节点个数+自己 
              return _Size(root->_left) + _Size(root->_right) + 1;
	}
	size_t _Depth(Node* root)
	{
		if (root == NULL)
			return 0;
                //求左子树的深度和右子树的深度，用返回值接收  
              size_t leftDepth = _Depth(root->_left);
		size_t rightDepth = _Depth(root->_right);

                //返回子树中最大的+当层的深度1
		return leftDepth > rightDepth ? leftDepth + 1: rightDepth + 1;
	}

        //通过传入引用的count，来计数
      void _GetLeafSize(Node* root,size_t &count)
	{
		if (root->_left == NULL && root->_right == NULL)
		{
			count++;
			return;
		}
		if (root->_left != NULL)
			_GetLeafSize(root->_left,count);
		if (root->_right!=NULL)
			_GetLeafSize(root->_right,count);
	}

        //求第K层的节点
      size_t _GetKLevelSize(Node* root,size_t k)
	{
		if (root == NULL)
			return 0;
		if (k == 1)
			return 1;

		return _GetKLevelSize(root->_left,k-1) + _GetKLevelSize(root->_right,k-1);
	}