二叉树:二叉树是一棵特殊的树，二叉树每个节点最多有两个孩子结点，分别称为左孩子和右孩子。

#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>#include<assert.h>#include<stack>#include<queue>

usingnamespacestd;//节点结构template<classT>classBinaryTreeNode//节点{public:BinaryTreeNode(constT&data):_data(data),_left(NULL),_right(NULL){}T_data;//值BinaryTreeNode*_left;//左子树BinaryTreeNode*_right;//右子树};template<classT>classBinaryTree{typedefBinaryTreeNode<T>Node;public:BinaryTree()//无参构造函数:_root(NULL){}BinaryTree(constT*a,size_tsize,constT&invalid)//构造函数{assert(a);size_tindex=0;_root=_CreateTree(a,size,invalid,index);}BinaryTree(constBinaryTree<T>&t)//拷贝构造{_root=_Copy(t._root);}BinaryTree<T>&operator=(constBinaryTree<T>&t)//赋值函数{if(this!=&t){BinaryTreeNode<T>*tmp=_Copy(t._root);_Destroy(_root);_root=temp;}return*this;}~BinaryTree()//析构{_Destroy(_root);_root=NULL;}public:voidPrevOrder()//先根遍历{cout<<"先根遍历:";_PrevOrder(_root);cout<<endl;}voidInOrder()//中根遍历{cout<<"中根遍历:";_InOrder(_root);cout<<endl;}voidPostOrder()//后根遍历{cout<<"后根遍历:";_PostOrder(_root);cout<<endl;}voidLevelOrder()//层次遍历{cout<<"层次遍历:";_LevelOrder(_root);cout<<endl;}size_tSize()//求二叉树的节点的个数{return_Size(_root);}size_tDepth()//求二叉树的深度{return_Depth(_root);}size_tLeafSize()//叶子节点个数{return_LeafSize(_root);}protected:Node*_CreateTree(constT*a,size_tsize,constT&invalid,size_t&index)//index要传引用，需要更改index的值{Node*root=NULL;//判断数组是否越界和输入的值是否合法if(index<size&&a[index]!=invalid){root=newNode(a[index]);//创建根节点root->_left=_CreateTree(a,size,invalid,++index);//递归创建左子树root->_right=_CreateTree(a,size,invalid,++index);//递归创建右子树}returnroot;//返回根节点}//void_PrevOrder(Node*root)//{////如果节点为空则直接返回//if(root==NULL)//{//return;//}//cout<<root->_data<<"";//访问根节点//_PrevOrder(root->_left);//递归访问左子树//_PrevOrder(root->_right);//递归访问右子树//}void_PrevOrder(Node*root){stack<Node*>s;if(root==NULL){return;}s.push(root);while(!s.empty()){root=s.top();cout<<root->_data<<"";s.pop();if(root->_right){s.push(root->_right);}if(root->_left){s.push(root->_left);}}}//void_InOrder(Node*root)//{////如果节点为空则直接返回//if(root==NULL)//{//return;//}//_InOrder(root->_left);//递归访问左子树//cout<<root->_data<<"";//递归访问根节点//_InOrder(root->_right);//递归访问右子树//}void_InOrder(Node*root){if(root==NULL){return;}stack<Node*>s;Node*cur=root;while(cur||!s.empty()){while(cur){s.push(cur);cur=cur->_left;}cur=s.top();//将栈顶元素保存，以便后面判断它是否有有孩子cout<<s.top()->_data<<"";s.pop();if(cur->_right==NULL){cur=NULL;}else{cur=cur->_right;}}}//void_PostOrder(Node*root)//{//if(root==NULL)//{//return;//}//_PostOrder(root->_left);//递归访问左子树//_PostOrder(root->_right);//递归访问右子树//cout<<root->_data<<"";//递归访问根节点//}void_PostOrder(Node*root){if(root==NULL){return;}Node*cur=root;Node*prev=NULL;stack<Node*>s;while(cur||!s.empty()){while(cur){s.push(cur);cur=cur->_left;}cur=s.top();if(cur->_right==NULL||cur->_right==prev){cout<<cur->_data<<"";s.pop();prev=cur;cur=NULL;}else{cur=cur->_right;}}}void_Destory(Node*root)//析构---相当于后序删除{if(root==NULL){return;}//删除叶结点if(root->_left==NULL&&root->_right==NULL){deleteroot;root=NULL;return;}_Destory(root->_left);//递归删除左子树_Destory(root->_right);//递归删除右子树deleteroot;}size_t_Size(Node*root)//节点的个数{size_tcount=0;if(root==NULL){returncount;//树为空}count=_Size(root->_left)+_Size(root->_right);returncount+1;}size_t_Depth(Node*root)//树的深度{size_tleft=0;size_tright=0;size_tmax=0;if(root==0){return0;}else{left=_Depth(root->_left);right=_Depth(root->_right);max=left>right?left:right;returnmax+1;}}size_t_LeafSize(Node*root)//叶子节点的个数{if(root==NULL){return0;}if(root->_left==NULL&&root->_right==NULL){return1;}return_LeafSize(root->_left)+_LeafSize(root->_right);}Node*_Copy(Node*root){if(roo==NULL){return;}Node*newroot=newNode(root->_data);newroot->_left=Copy(root->_left);newroot->_right=Copy(root->_right);returnnewroot;}void_LevelOrder(Node*root)//层次遍历{queue<Node*>q;if(root==NULL){return;}q.push(root);//根节点入队while(!q.empty())//当队列不为空{if(q.front()->_left){q.push(q.front()->_left);}if(q.front()->_right){q.push(q.front()->_right);}cout<<q.front()->_data<<"";q.pop();}cout<<endl;}private:Node*_root;//根节点};voidTest(){inta[10]={1,2,3,'#','#',4,'#','#',5,6};BinaryTree<int>b(a,10,'#');b.PrevOrder();b.InOrder();b.PostOrder();b.LevelOrder();cout<<"size:"<<b.Size()<<endl;cout<<"depth:"<<b.Depth()<<endl;cout<<"leafSize:"<<b.LeafSize()<<endl;}intmain(){Test();getchar();return0;}