二叉树先序遍历；（1）先序访问根节点 （2）先序访问左子树 （3）先序访问右子树

二叉树中序遍历；（1）中序访问根节点 （2）中序访问左子树 （3）中序访问右子树

二叉树后序遍历；（1）后序访问根节点 （2）后序访问左子树 （3）后序访问右子树

测试用例：int a[10]={'1','2','3','#','#','4','#','#','5','6'}

代码：

#include<iostream>usingnamespacestd;#include<queue>#include<stack>template<classT>structBinaryTreeNode{BinaryTreeNode<T>*_left;BinaryTreeNode<T>*_right;T_data;BinaryTreeNode(constT&d):_left(NULL),_right(NULL),_data(d){}};template<classT>classBinaryTree{public:BinaryTree():_root(NULL){}BinaryTree(constT*a,size_tsize,constT&invalid){size_tindex=0;_root=_Create(a,size,index,invalid);}//BinaryTree(constBinaryTree<T>&d)//{//BinaryTreeNode<T>root=NULL;//}BinaryTree<T>&operator=(constBinaryTree<T>&d){swap(root,d._root);}voidPrevOrder(){_PrevOrder(_root);}voidInOrder(){_InOrder(_root);}size_tSize(){_Size(_root);}size_tDepth(){return_Depth(_root);}size_tLeafSize(){return_LeafSize(_root);}voidLevelOrder(){_LeavelOrder();}voidPrevOrder_NonR(){_PrevOrder_NonR();}voidInOrder_NonR(){_InOrer_NonR();}voidPostOrder_NonR(){_PostOrder_NonR();}public:protected:BinaryTreeNode<T>*_Create(constT*a,size_tsize,size_t&index,constT&invalid){BinaryTreeNode<T>*root=NULL;while(index<size&&a[index]!=invalid){root=newBinaryTreeNode<T>(a[index]);root->_left=_Create(a,size,++index,invalid);root->_right=_Create(a,size,++index,invalid);}returnroot;}void_PrevOrder(BinaryTreeNode<T>*root){if(root==NULL){return;}cout<<root->_data<<"";_PrevOrder(root->_left);_PrevOrder(root->_right);}void_InOrder(BinaryTreeNode<T>*root){if(root==NULL){return;}_InOrder(root->_left);cout<<root->_data<<"";_InOrder(root->_right);}size_t_size(BinaryTreeNode<T>*root){if(root==NULL){return0;}return_Size(root->_left)+_Size(root->_right)+1;}size_t_Depth(BinaryTreeNode<T>*root){if(root==NULL){return0;}intleft=_Depth(root->_left)+1;intright=_Depth(root->_right)+1;return(left>right?left:right);}size_t_LeafSize(BinaryTreeNode<T>*root){if(root==NULL){return0;}if(root->_left==NULL&&(root->_right==NULL)){return1;}return_LeafSize(root->_left)+_LeafSize(root->_right);}void_LeavelOrder(){queue<BinaryTreeNode<T>*>q;if(_root){q.push(_root);}while(!q.empty()){BinaryTreeNode<T>*front=q.front();cout<<front._data<<"";if(_root->_left){q.push(_root->_left);}if(_root->_right){q.push(_root->_right);}q.pop();}cout<<endl;}void_PrevOrder_NonR(){stack<BinaryTreeNode<T>*>s;BinaryTreeNode<T>*cur=_root;while(cur||!s.empty()){while(cur){cout<<cur->_data<<"";s.push(cur);cur=cur->_left;}if(!s.empty()){BinaryTreeNode<T>*top=s.top();cur=top->_right;s.pop();}}}void_InOrer_NonR(){stack<BinaryTreeNode<T>*>s;BinaryTreeNode<T>*cur=_root;while(cur||!s.empty()){while(cur){s.push(cur);cur=cur->_left;}BinaryTreeNode<T>*Top=s.top();cout<<Top->_data<<"";cur=Top->_right;s.pop();}cout<<endl;}void_PostOrder_NonR(){BinaryTreeNode<T>*cur=_root;stack<BinaryTreeNode<T>*>s;BinaryTreeNode<T>*prev=NULL;while(cur||!s.empty()){while(cur){s.push(cur);cur=cur->_left;}BinaryTreeNode<T>*top=s.top();if(top->_right==NULL||top->_right==prev){cout<<top->_data<<"";s.pop();prev=top;}elsecur=top->_right;//cout<<endl;}}protected:BinaryTreeNode<T>*_root;};intmain(){inta1[10]={1,2,3,'#','#',4,'#','#',5,6};BinaryTree<int>b1(a1,10,'#');//b1.InOrder();//b1.InOrder_NonR();//b1.Depth();//b1.PrevOrder_NonR();b1.PostOrder_NonR();system("pause");return0;}