#include<assert.h>#include<iostream>usingnamespacestd;#include<stack>#include<queue>template<classT>structBinaryTreeNode{BinaryTreeNode<T>*_left;BinaryTreeNode<T>*_right;T_data;BinaryTreeNode(constT&x):_left(NULL),_right(NULL),_data(x){}};template<classT>classBinaryTree{public:BinaryTree():_root(NULL){}BinaryTree(constT*a,size_tsize,constT&invalid){size_tindex=0;_root=_CreateTree(a,size,index,invalid);}~BinaryTree(){_DestroyTree(_root);_root=NULL;}BinaryTree(constBinaryTree<T>&t){_root=_CopyTree(t._root);}//赋值运算符重载的传统写法/*BinaryTree<T>&operator=(constBinaryTree&t){if(this!=&t){_DestroyTree(_root);_root=_CopyTree(t._root);}return*this;}*///赋值运算符重载的现代写法BinaryTree<T>&operator=(BinaryTree<T>t){swap(_root,t._root);return*this;}//递归前序遍历voidPreOrderTraverse(){_PreOrderTraverse(_root);cout<<endl;}//递归中序遍历voidInOrderTraverse(){_InOrderTraverse(_root);cout<<endl;}//递归后序遍历voidPostOrderTraverse(){_PostOrderTraverse(_root);cout<<endl;}//非递归层序遍历voidLevelOrderTraverse(){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);}}}//非递归前序遍历voidPreOrderTraverse_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;}//非递归中序遍历voidInOrderTraverse_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;}//非递归后序遍历voidPostOrderTraverse_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_tSize(){size_tsize=0;_Size(_root,size);returnsize;}//求深度size_tDepth(){return_Depth(_root);}//求叶子结点数size_tLeafSize(){size_tleafSize=0;_LeafSize(_root,leafSize);returnleafSize;}//求第K层结点数size_tGetKLevel(constsize_t&k){return_GetKLevel(_root,k);}protected:BinaryTreeNode<T>*_CreateTree(constT*a,size_tsize,size_t&index,constT&invalid){BinaryTreeNode<T>*root=NULL;if(index<size&&a[index]!=invalid){root=newBinaryTreeNode<T>(a[index]);root->_left=_CreateTree(a,size,++index,invalid);root->_right=_CreateTree(a,size,++index,invalid);}returnroot;}void_DestroyTree(BinaryTreeNode<T>*root){if(NULL==root){return;}if(NULL==root->_left&&NULL==root->_right){deleteroot;root=NULL;return;}_DestroyTree(root->_left);_DestroyTree(root->_right);deleteroot;}BinaryTreeNode<T>*_CopyTree(BinaryTreeNode<T>*root){if(NULL==root){returnNULL;}BinaryTreeNode<T>*newRoot=newBinaryTreeNode<T>(root->_data);newRoot->_left=_CopyTree(root->_left);newRoot->_right=_CopyTree(root->_right);returnnewRoot;}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){staticsize_tsize=0;if(NULL==root){return0;}else{++size;}_Size(root->_left);_Size(root->_right);returnsize;}*///_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){return0;}size_tleftDepth=_Depth(root->_left);size_trightDepth=_Depth(root->_right);returnleftDepth>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,constsize_t&k){assert(k>0);if(NULL==root){return0;}if(k==1){return1;}return_GetKLevel(root->_left,k-1)+_GetKLevel(root->_right,k-1);}protected:BinaryTreeNode<T>*_root;};voidBinaryTreeTest(){inta[]={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();}intmain(){BinaryTreeTest();return0;}

生成的二叉树如下图：

测试结果：