二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^（i - 1）个结点；深度为k的二叉树至多有2^k - 1个结点。由于树的定义是递归实现的，所以在进行二叉树的前序、中序和后序遍历可通过递归实现，但也可通过非递归的栈来实现，二叉树的层次遍历可通过队列实现。

下面我对二叉树及前序、中序、后序遍历二叉树等方法进行实现

例如二叉树:

测试用例：

intarrary[10] = {1,2,3,'$','$',4,'$','$',5,6};

arrary为上图所示二叉树，通过前序存储的，'$'表示非法值，即没有结点

二叉树的结构：

template<classT>structBinaryTreeNode{BinaryTreeNode<T>*_left;BinaryTreeNode<T>*_right;T_data;BinaryTreeNode();BinaryTreeNode(constT&x);};template<classT>classBinaryTree{typedefBinaryTreeNode<T>Node;public:BinaryTree();BinaryTree(constT*a,size_tsize,constT&invalid);BinaryTree(constBinaryTree<T>&t);BinaryTree<T>&operator=(BinaryTree<T>t);~BinaryTree();voidPrevOrder();//前序遍历-递归voidInOrder();//中序遍历-递归voidPostOrder();//后序遍历-递归voidPrevOrder_NonR();//前序遍历-非递归voidInOrder_NonR();//中序遍历-非递归voidPostOrder_NonR();//后序遍历-非递归voidLevelOrder();//层次遍历size_tSize();//结点个数size_tDepth();//树的深度size_tLeafSize();//叶子结点个数size_tGetkLevel();//第k层结点个数protected:Node*_CreateTree(constT*a,size_tsize,size_t&index,constT&invalid);//树的建立Node*_CopyTree(Node*t);//复制树void_Distory(Node*root);//清空结点，先释放子树，再释放根结点void_PrevOrder(Node*root);//前序遍历void_InOrder(Node*root);//中序遍历void_PostOrder(Node*root);//后序遍历size_t_Size(Node*root);//结点个数size_t_Depth(Node*root);//树的深度//size_t_LeafSize(Node*root);//叶子结点个数size_t_LeafSize(Node*root,size_t&size);//叶子结点个数//size_t_GetkLevel(intk,Node*root);//第k层结点个数size_t_GetkLevel(intk,Node*root,int&size,intlevel);//第k层结点个数private:Node*_root;//BinaryTreeNode<T>*_root;};

二叉树的构造、拷贝构造、赋值运算和析构的实现，由于二叉树存在左子树和右子树，故用递归实现其功能，具体实现如下：

template<classT>BinaryTreeNode<T>::BinaryTreeNode():_left(NULL),_right(NULL),_data(0){}template<classT>BinaryTreeNode<T>::BinaryTreeNode(constT&x):_left(NULL),_right(NULL),_data(x){}template<classT>BinaryTree<T>::BinaryTree():_root(NULL){}template<classT>BinaryTree<T>::~BinaryTree(){_Distory(_root);}template<classT>voidBinaryTree<T>::_Distory(Node*root)//清空结点，先释放子树，再释放根结点{if(root==NULL){return;}if(root->_left)//递归释放子结点{_Distory(root->_left);}if(root->_right){_Distory(root->_right);}deleteroot;root=NULL;}template<classT>BinaryTree<T>::BinaryTree(constT*a,size_tsize,constT&invalid){size_tindex=0;//标记数组下标_root=_CreateTree(a,size,index,invalid);}template<classT>BinaryTreeNode<T>*BinaryTree<T>::_CreateTree(constT*a,size_tsize,size_t&index,constT&invalid)//树的建立{Node*root=NULL;if(index<size&&a[index]!=invalid)//indx<size以防数组越界{root=newNode(a[index]);root->_left=_CreateTree(a,size,++index,invalid);//左子树递归root->_right=_CreateTree(a,size,++index,invalid);//右子树递归}returnroot;}template<classT>BinaryTree<T>::BinaryTree(constBinaryTree<T>&t){_root=_CopyTree(t._root);}template<classT>BinaryTreeNode<T>*BinaryTree<T>::_CopyTree(Node*t)//此处的返回类型不能用Node表示{Node*root=NULL;if(t!=NULL){root=newNode(t->_data);root->_left=_CopyTree(t->_left);root->_right=_CopyTree(t->_right);}returnroot;}template<classT>BinaryTree<T>&BinaryTree<T>::operator=(BinaryTree<T>t)//现代写法{if(this!=&t){BinaryTree<T>tmp=t;swap(_root,tmp._root);}return*this;}

前序遍历(先根遍历)：(1)先访问根节点；(2)前序访问左子树；(3)前序访问右子树.【1 2 3 4 5 6】

下面分别用递归和非递归两种方法实现。

二叉树的递归实现前序遍历

//递归实现template<classT>voidBinaryTree<T>::PrevOrder()//前序遍历(先根结点){_PrevOrder(_root);}template<classT>voidBinaryTree<T>::_PrevOrder(Node*root){if(root==NULL){return;}cout<<root->_data<<"";_PrevOrder(root->_left);_PrevOrder(root->_right);}

二叉树的非递归实现前序序列，利用栈实现。

由于栈是后进先出，对于二叉树的前序遍历先访问左子树后访问右子树，故右结点比左结点先进栈

//非递归实现（利用栈实现）template<classT>voidBinaryTree<T>::PrevOrder_NonR()//前序遍历-非递归{stack<Node*>s;if(_root){s.push(_root);}while(!s.empty()){Node*top=s.top();//访问栈顶元素cout<<top->_data<<"";s.pop();//右结点比左结点先进栈if(top->_right){s.push(top->_right);}if(top->_left){s.push(top->_left);}}cout<<endl;}

中序遍历：(1)中序访问左子树；(2)访问根节点；(3)中序访问右子树.【3 2 4 1 6 5】

下面分别用递归和非递归两种方法实现

二叉树的递归实现中序序列

template<classT>voidBinaryTree<T>::InOrder()//中序遍历（中根结点）{_InOrder(_root);}template<classT>voidBinaryTree<T>::_InOrder(Node*root){if(root==NULL){return;}_InOrder(root->_left);cout<<root->_data<<"";_InOrder(root->_right);}

二叉树的非递归实现中序序列

//非递归实现（利用栈实现）template<classT>voidBinaryTree<T>::InOrder_NonR()//中序遍历-非递归{if(_root==NULL){return;}stack<Node*>s;Node*cur=_root;while(cur||!s.empty()){//压一棵树的左结点，直到最左结点while(cur){s.push(cur);cur=cur->_left;}if(!s.empty()){Node*top=s.top();cout<<top->_data<<"";s.pop();cur=top->_right;//使cur指向最左结点top的右结点}}cout<<endl;}

后序遍历(后根遍历)：(1)后序访问左子树；(2)后序访问右子树；(3)访问根节点.【3 4 2 6 5 1】

下面分别用递归和非递归两种方法实现

二叉树的递归实现后序序列

//递归实现template<classT>voidBinaryTree<T>::PostOrder()//后序遍历（后根结点）{_PostOrder(_root);}template<classT>voidBinaryTree<T>::_PostOrder(Node*root)//后序遍历{if(root==NULL){return;}_PostOrder(root->_left);_PostOrder(root->_right);cout<<root->_data<<"";}//非递归实现（利用栈实现）

二叉树的非递归实现后序序列

template<classT>voidBinaryTree<T>::PostOrder_NonR()//后序遍历-非递归{if(_root==NULL){return;}stack<Node*>s;Node*cur=_root;Node*prev=NULL;while(cur||!s.empty()){//压一棵树的左结点，直到最左结点while(cur){s.push(cur);cur=cur->_left;}Node*top=s.top();if(top->_right==NULL||top->_right==prev){cout<<top->_data<<"";s.pop();prev=top;}else//当未访问过栈顶的右子树，则继续右子树的访问{cur=top->_right;}cout<<endl;}}

层序遍历：一层层节点依次遍历。【1 2 5 3 4 6】

下面用非递归方法实现，利用队列进行访问。

//递归实现template<classT>voidBinaryTree<T>::LevelOrder()//层次遍历,通过队列实现{queue<Node*>q;//建立队列存放Note*类型值if(_root!=NULL){q.push(_root);}while(!q.empty()){Node*front=q.front();cout<<front->_data<<"";//访问队头q.pop();//队头出队列if(front->_left!=NULL)//存在左或右结点入队列{q.push(front->_left);}if(front->_right!=NULL){q.push(front->_right);}}cout<<endl;}

求树的结点个数，递归实现：

template<classT>size_tBinaryTree<T>::Size()//结点个数{return_Size(_root);}template<classT>size_tBinaryTree<T>::_Size(Node*root){if(root==NULL){return0;}//root不为0，则Size+1return_Size(root->_left)+_Size(root->_right)+1;}

求树的深度，递归实现：

template<classT>size_tBinaryTree<T>::Depth()//树的深度{return_Depth(_root);}template<classT>size_tBinaryTree<T>::_Depth(Node*root){if(root==NULL){return0;}size_tLeftDepth=_Depth(root->_left);size_tRightDepth=_Depth(root->_right);if(LeftDepth>RightDepth)//root不为0，则深度+1{returnLeftDepth+1;}else{returnRightDepth+1;}}

求树的叶子结点个数，递归实现：

//方法一template<classT>size_tBinaryTree<T>::LeafSize()//叶子结点个数{return_LeafSize(_root);}template<classT>size_tBinaryTree<T>::_LeafSize(Node*root){if(root==0){return0;}if(root->_left==0&&root->_right==0){return1;}return_LeafSize(root->_left)+_LeafSize(root->_right);}//方法二:在LeafSize中定义_size表示叶子结点个数template<classT>size_tBinaryTree<T>::LeafSize()//叶子结点个数{size_t_size=0;return_LeafSize(_root,_size);}template<classT>size_tBinaryTree<T>::_LeafSize(Node*root,size_t&size){if(root==0){return0;}if(root->_left==0&&root->_right==0){++size;returnsize;}_LeafSize(root->_left,size);_LeafSize(root->_right,size);returnsize;}

二叉树中第k层结点的个数，递归实现：

//方法一template<classT>size_tBinaryTree<T>::GetkLevel(intk){assert(k>0);return_GetkLevel(k,_root);}template<classT>size_tBinaryTree<T>::_GetkLevel(intk,Node*root)//第k层结点个数{if(root==NULL){return0;}if(k==1)//利用递归使k递减，k==1结束{return1;}size_tsize1=_GetkLevel(k-1,root->_left);size_tsize2=_GetkLevel(k-1,root->_right);returnsize1+size2;}//方法二:在GetkLevel中定义size表示第k层结点个数template<classT>size_tBinaryTree<T>::GetkLevel(intk){assert(k>0);intsize=0;//size为二叉树第level层结点个数intlevel=1;//第level层return_GetkLevel(k,_root,size,level);}template<classT>size_tBinaryTree<T>::_GetkLevel(intk,Node*root,int&size,intlevel)//第k层结点个数{if(root==NULL){return0;}if(level==k){++size;returnsize;}_GetkLevel(k,root->_left,size,level+1);_GetkLevel(k,root->_right,size,level+1);returnsize;}