首先先来看一下树的结构：


树是n（n>=0）个有限个数据的元素集合，形状像一颗倒过来的树。

而二叉树就是树的一种特殊结构：

完全二叉树的数组表示

链表存储表示

下面我就实现一下二叉链的这种结构：

首先是它的节点的结构：

template<typenameT>structBinaryTreeNode{public:BinaryTreeNode(constT&data)//构造函数:_left(NULL),_right(NULL),_data(data){}public:BinaryTreeNode<T>*_left;//左子树BinaryTreeNode<T>*_right;//右子树T_data;//数据项};

然后是它的基本成员函数：

template<typenameT>classBinaryTree{typedefBinaryTreeNode<T>Node;//重命名struct结构public:BinaryTree()//无参的构造函数:_root(NULL){}BinaryTree(constT*a,size_tsize,constT&invalid)//有参构造函数:_root(NULL){size_tindex=0;_root=_CreatBinaryTree(a,size,invalid,index);}BinaryTree(constBinaryTree<T>&t)//拷贝构造:_root(NULL){_root=_Copy(t._root);}BinaryTree<T>&operator=(BinaryTree<T>t)//赋值运算符的重载{if(this!=&t)//防止自赋值{swap(_root,t._root);}return*this;}~BinaryTree()//析构函数{if(_root){_Delete(_root);}}voidPrevOrder()//前序遍历{_PrevOrder(_root);cout<<"over"<<endl;}voidInOrder()//中序遍历{_InOrder(_root);cout<<"over"<<endl;}voidPostOrder()//后序遍历{_PostOrder(_root);cout<<"over"<<endl;}voidLevelOredr()//层次遍历{_LevelOrder(_root);cout<<"over"<<endl;}size_tSize()//节点数{return_Size(_root);}size_tDepth()//深度{return_Depth(_root);}size_tLeafSize()//叶子节点数{return_LeafSize(_root);}protected://创建二叉树Node*_CreatBinaryTree(constT*a,size_tsize,constT&invalid,size_t&index){Node*cur=NULL;if(index<size&&a[index]!=invalid)//不能越界{cur=newNode(a[index]);//开辟节点cur->_left=_CreatBinaryTree(a,size,invalid,++index);//递归创建左子树cur->_right=_CreatBinaryTree(a,size,invalid,++index);//递归创建右子树}returncur;}//复制二叉树Node*_Copy(Node*root){Node*cur=NULL;if(root==NULL){returnNULL;}cur=newNode(root->_data);//创建该节点cur->_left=_Copy(root->_left);cur->_right=_Copy(root->_right);returncur;}//删除void_Delete(Node*&root){if(root==NULL){return;}if(root->_left==NULL&&root->_right==NULL)//该节点没有左右孩子{deleteroot;//释放该节点root=NULL;return;}_Delete(root->_left);_Delete(root->_right);}//前序遍历：根节点--左子树--右子树void_PrevOrder(Node*root){if(root==NULL){return;}cout<<root->_data<<"->";_PrevOrder(root->_left);_PrevOrder(root->_right);}//中序遍历：左子树--根节点--右子树void_InOrder(Node*root){if(root==NULL){return;}_PrevOrder(root->_left);cout<<root->_data<<"->";_PrevOrder(root->_right);}//后序遍历：左子树--右子树--根节点void_PostOrder(Node*root){if(root==NULL){return;}_PrevOrder(root->_left);_PrevOrder(root->_right);cout<<root->_data<<"->";}//层次遍历void_LevelOrder(Node*root){queue<Node*>q;if(root==NULL){return;}q.push(root);while(!q.empty()){if(q.front()->_left!=NULL){q.push(q.front()->_left);}if(q.front()->_right!=NULL){q.push(q.front()->_right);}cout<<q.front()->_data<<"->";q.pop();}}//节点个数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);/*if(leftDepth>=rightDepth){returnleftDepth+1;}elsereturnrightDepth+1;*/returnleftDepth>rightDepth?leftDepth+1:rightDepth+1;}//叶子节点个数size_t_LeafSize(Node*root){size_tsize=0;if(root==NULL){returnsize;}if(root->_left==NULL&&root->_right==NULL){size++;returnsize;}return_LeafSize(root->_left)+_LeafSize(root->_right);}private:Node*_root;//根节点};

测试用例以及结果如下：

voidTest(){intarray1[10]={1,2,3,'#','#',4,'#','#',5,6};BinaryTree<int>b1(array1,10,'#');cout<<"前序遍历：";b1.PrevOrder();cout<<"中序遍历：";b1.InOrder();cout<<"后序遍历：";b1.PostOrder();cout<<"层次遍历：";b1.LevelOredr();cout<<endl;cout<<"节点数："<<b1.Size()<<endl;cout<<"深度："<<b1.Depth()<<endl;cout<<"叶子节点数："<<b1.LeafSize()<<endl;cout<<endl;BinaryTree<int>b2(b1);cout<<"前序遍历：";b2.PrevOrder();cout<<"中序遍历：";b2.InOrder();cout<<"后序遍历：";b2.PostOrder();cout<<"层次遍历：";b2.LevelOredr();cout<<endl;cout<<"节点数："<<b2.Size()<<endl;cout<<"深度："<<b2.Depth()<<endl;cout<<"叶子节点数："<<b2.LeafSize()<<endl;cout<<endl;BinaryTree<int>b3;b3=b1;cout<<"前序遍历：";b3.PrevOrder();cout<<"中序遍历：";b3.InOrder();cout<<"后序遍历：";b3.PostOrder();cout<<"层次遍历：";b3.LevelOredr();cout<<endl;cout<<"节点数："<<b3.Size()<<endl;cout<<"深度："<<b3.Depth()<<endl;cout<<"叶子节点数："<<b3.LeafSize()<<endl;}