/*****************WZASUST2016二叉树的结点计算配图栈实现非递归栈内元素变化图******************/#include<iostream>#include<stdio.h>#include<stack>#include<queue>usingnamespacestd;typedefstructBinNode{chardata;boolflag;//后序非递归中的标记structBinNode*lchild,*rchild;}BinNode,*BinTree;//按先序创建树//charss[]="12##3##";charss[]="124##x##3y##5##";//charss[]="124###3#5##";/**************************1*23*45*************************/inti=0;voidcreatTree(BinTree&T){charc;//cin>>c;c=ss[i++];if(c=='#')T=NULL;else{//T=(BinTree)malloc(sizeof(BinNode));T=newBinNode;T->data=c;creatTree(T->lchild);creatTree(T->rchild);}}voidvisit(BinTreeT){if(T->data!='#')cout<<T->data<<"";}voidpreOrder(BinTreeT)//前序递归{if(T){visit(T);preOrder(T->lchild);preOrder(T->rchild);}}voidinOrder(BinTreeT)//中序递归{if(T){inOrder(T->lchild);visit(T);inOrder(T->rchild);}}voidpostOrder(BinTreeT)//后序递归{if(T){postOrder(T->lchild);postOrder(T->rchild);visit(T);}}voidpreOrderUnrec(BinTreeT)//非递归前序遍历{BinTreep;p=T;stack<BinTree>s;while(p||!s.empty()){while(p){visit(p);s.push(p);p=p->lchild;}if(!s.empty()){p=s.top();s.pop();p=p->rchild;}}}voidinOrderUnrec(BinTreeT)////非递归中序遍历{BinTreep;p=T;stack<BinTree>s;while(p||!s.empty()){while(p){s.push(p);p=p->lchild;}if(!s.empty()){p=s.top();visit(p);s.pop();p=p->rchild;}}}voidpostOrderUnrec1(BinTreeT)//非递归后序遍历这个思路更好理解一些，下面有解释{BinTreep,cur;p=T;stack<BinTree>s;s.push(p);BinTreepre=NULL;while(!s.empty()){cur=s.top();if((cur->lchild==NULL&&cur->rchild==NULL)||((pre!=NULL)&&(pre==cur->lchild||pre==cur->rchild))){visit(cur);s.pop();pre=cur;}else{if(cur->rchild)s.push(cur->rchild);if(cur->lchild)s.push(cur->lchild);}}}voidpostOrderUnrec2(BinTreeT)//非递归后序遍历{BinTreecur,p;p=T;p->flag=false;stack<BinTree>s;s.push(p);while(!s.empty()){cur=s.top();if(cur->flag==true){visit(cur);s.pop();}else{if(cur->rchild){cur->rchild->flag=false;s.push(cur->rchild);}if(cur->lchild){cur->lchild->flag=false;//左右节点为NULL时，开始要出栈s.push(cur->lchild);}cur->flag=true;//左右子节点入栈后，父节点标记为TRUE}}}voidpostOrderUnrec3(BinTreeT){BinTreecur,p;p=T;queue<BinTree>q;q.push(p);while(!q.empty()){cur=q.front();visit(cur);q.pop();if(cur->lchild!=NULL)q.push(cur->lchild);if(cur->rchild!=NULL)q.push(cur->rchild);}}voidpostOrderUnrec4(BinTreeT)//非递归后序遍历不宜用带计数器实现{BinTreecur,p;p=T;BinTreeq[10];intf=0;intr=1;while(f<r){visit(p);q[f]=p;if(p->lchild!=NULL)q[r++]=p->lchild;if(p->rchild!=NULL)q[r++]=p->rchild;if(r%2==1)f++;//cout<<r<<endl;p=q[f];}}voidcreatbylay(BinTreeT){charc=ss[i++];if(c=='#')T=NULL;else{T=newBinNode;T->data=c;}BinTreecur=T;queue<BinTree>q;q.push(cur);while(!q.empty()){cur=q.front();q.pop();if(c=='#')cur->lchild=NULL;else{cur->lchild=newBinNode;T->data=c;q.push(cur->lchild);}if(c=='#')cur->rchild=NULL;else{cur->rchild=newBinNode;T->data=c;q.push(cur->rchild);}}}voidprint_as_tree(BinTreeT,intlay){if(T){print_as_tree(T->rchild,lay+1);for(intj=0;j<lay;j++)printf("*");cout<<T->data<<endl;print_as_tree(T->lchild,lay+1);}elsereturn;}size_tcount_on_klay(BinTreeroot,size_tk){//假设参数合法；if(NULL==root)return0;if(k==1)return1;returncount_on_klay(root->lchild,k-1)+count_on_klay(root->rchild,k-1);}size_tcount_to_klay(BinTreeroot,size_tk){//假设参数合法；size_tcount=0;for(inti=1;i<=k;i++)count+=count_on_klay(root,i);returncount;}intmain(){BinTreeT;creatTree(T);preOrder(T);cout<<endl;postOrderUnrec1(T);cout<<endl;postOrderUnrec4(T);//creatbylay(T);//postOrderUnrec4(T);cout<<endl;print_as_tree(T,3);cout<<endl;cout<<count_to_klay(T,3);cout<<endl;cout<<count_on_klay(T,1);cout<<endl;return0;}