首先二叉树的节点定义如下：structBinaryNode{BinaryNode*_left;BinaryNode*_right;T_data;BinaryNode(Tdata):_data(data),_left(NULL),_right(NULL){};};二叉树的结构以及接口如下template<classT>classBinaryTree{typedefBinaryNode<T>Node;public:BinaryTree():_head(NULL){};BinaryTree(constT*a,size_tsize,constT&valiue)~BinaryTree()BinaryTree(BinaryTree&b)voidPrevOder()voidInOder()voidPostOder()private:public:voidLevalOder()size_tdepth()size_tsize()size_tlearsize()void_LevalOder(BinaryNode<T>*root);size_t_depth(BinaryNode<T>*root);void_size(BinaryNode<T>*root,int*p);void_leafsize(BinaryNode<T>*root,size_t*p);intLeafsize(BinaryNode<T>*root);voidPrevOder_Nor();voidInOder_Nor();voidPostOder_Nor();voidDistory(Node*_root)Node*_Copy(Node*cur);private:BinaryNode<T>*_root;};二叉树的建立（构造函数）BinaryTree(constT*a,size_tsize,constT&valiue){size_tindex=0;_root=_CreatTree(a,size,index,valiue);}BinaryNode<T>*_CreatTree(constT*a,size_tsize,size_t&index,constT&valiue){BinaryNode<T>*root=NULL;if(index<size&&a[index]!=valiue){root=newBinaryNode<T>(a[index]);root->_left=_CreatTree(a,size,++index,valiue);root->_right=_CreatTree(a,size,++index,valiue);}returnroot;}二叉树的销毁（析构函数）~BinaryTree(){Distory(_root);cout<<"~BinaryTree()"<<endl;}voidDistory(Node*_root){if(_root==NULL)return;Distory(_root->_left);Distory(_root->_right);if(_root)delete_root;_root==NULL;}二叉树的拷贝(拷贝构造)BinaryTree(BinaryTree&b){_root=_Copy(b._root);}BinaryNode<T>*BinaryTree<T>::_Copy(Node*cur){if(cur==NULL)returnNULL;Node*tmp=newNode(cur->_data);tmp->_left=_Copy(cur->_left);tmp->_right=_Copy(cur->_right);returntmp;}求叶子节点个数（两种方法）一：intBinaryTree<T>::Leafsize(BinaryNode<T>*root){intcount;if(root==NULL)count=0;elseif(root->_left==NULL&&root->_right==NULL){count=1;}elsecount=Leafsize(root->_left)+Leafsize(root->_right);returncount;}二：voidBinaryTree<T>::_leafsize(BinaryNode<T>*root,size_t*p){if(root!=NULL){_leafsize(root->_left,p);_leafsize(root->_right,p);if(root->_left==NULL&&root->_right==NULL){++*p;}}}二叉树前序遍历递归void_PrevOder(BinaryNode<T>*root){if(root==NULL)return;cout<<root->_data<<"";_PrevOder(root->_left);_PrevOder(root->_right);}二叉树前序遍历非递归voidBinaryTree<T>::PrevOder_Nor(){BinaryNode<T>*cur=_root;stack<BinaryNode<T>*>s;if(cur==NULL)return;s.push(cur);while(!s.empty()){BinaryNode<T>*tmp=s.top();cout<<tmp->_data<<"";s.pop();if(tmp->_right){s.push(tmp->_right);}if(tmp->_left){s.push(tmp->_left);}}cout<<endl;}二叉树层序遍历（队列实现）voidBinaryTree<T>::_LevalOder(BinaryNode<T>*root){deque<BinaryNode<T>*>q;q.push_back(root);while(q.size()){BinaryNode<T>*pNode=q.front();q.pop_front();cout<<pNode->_data<<"";if(pNode->_left){q.push_back(pNode->_left);}if(pNode->_right){q.push_back(pNode->_right);}}}二叉树中序遍历递归void_InOder(BinaryNode<T>*root){if(root==NULL)return;_InOder(root->_left);cout<<root->_data<<"";_InOder(root->_right);}二叉树中序遍历非递归voidBinaryTree<T>::InOder_Nor(){if(_root==NULL)return;Node*cur=_root;stack<Node*>s;while(cur||!s.empty()){while(cur){s.push(cur);cur=cur->_left;}Node*tmp=s.top();cout<<tmp->_data<<"";s.pop();cur=tmp->_right;}cout<<endl;}二叉树后序遍历递归void_PostOder(BinaryNode<T>*root){if(root==NULL)return;_PostOder(root->_left);_PostOder(root->_right);cout<<root->_data<<"";}二叉树后序遍历非递归voidBinaryTree<T>::PostOder_Nor(){if(_root==NULL)return;Node*cur=_root;stack<Node*>s;Node*prev=NULL;while(cur||!s.empty()){while(cur){s.push(cur);cur=cur->_left;}Node*tmp=s.top();if(tmp->_right==NULL||tmp->_right==prev){cout<<tmp->_data<<"";s.pop();prev=tmp;}else{cur=tmp->_right;}}cout<<endl;}二叉树的深度size_tBinaryTree<T>::_depth(BinaryNode<T>*root){inthleft;inthright;intmax;if(root){hleft=_depth(root->_left);hright=_depth(root->_right);max=hleft>hright?hleft:hright;returnmax+1;}else{return0;}}二叉树的大小size_tsize(){intcount=0;_size(_root,&count);returncount;}voidBinaryTree<T>::_size(BinaryNode<T>*root,int*p){if(root){++(*p);_size(root->_left,p);_size(root->_right,p);}return;}