BinaryTree.h

#pragmaoncetemplate<classT>structBinaryTreeNode{BinaryTreeNode<T>*_right;BinaryTreeNode<T>*_left;T_data;BinaryTreeNode(constT&d):_right(NULL),_left(NULL),_data(d){}};template<classT>classBinaryTree{typedefBinaryTreeNode<T>Node;public:BinaryTree():_root(NULL){}BinaryTree(constT*a,size_tsize,constT&invalid){size_tindex=0;_root=_CreatTree(a,size,index,invalid);}BinaryTree(constBinaryTree<T>&t){_root=_CopyTree(t._root);}~BinaryTree(){_Destory(_root);_root=NULL;}size_tSize()//求二叉树结点数目{return_Size(_root);}size_tDepth()//求二叉树深度{return_Depth(_root);}voidPrevOrder()//前序遍历{_PrevOrder(_root);cout<<endl;}protected:Node*_CreatTree(constT*a,size_tsize,size_t&index,constT&invalid){Node*root=NULL;if(index<size&&a[index]!=invalid){root=newNode(a[index]);root->_left=_CreatTree(a,size,++index,invalid);root->_right=_CreatTree(a,size,++index,invalid);}returnroot;}Node*_CopyTree(constNode*root){if(root==NULL){returnNULL;}Node*newRoot=newNode(root->_data);newRoot->_left=_CopyTree(root->_left);newRoot->_right=_CopyTree(root->_right);returnnewRoot;}void_Destory(Node*root){if(root==NULL){return;}_Destory(root->_left);_Destory(root->_right);deleteroot;}size_t_Size(Node*root){if(root==NULL){return0;}return_Size(root->_left)+_Size(root->_right)+1;}size_t_Depth(Node*root){if(root==NULL){return0;}size_tleftDepth=_Depth(root->_left);size_trightDepth=_Depth(root->_right);returnleftDepth>rightDepth?leftDepth+1:rightDepth+1;}void_PrevOrder(Node*root){if(root==NULL){return;}cout<<root->_data<<",";_PrevOrder(root->_left);_PrevOrder(root->_right);}private:Node*_root;