小代码 二叉树非递归与结点计算

/*****************   WZ ASUST 2016
二叉树 的结点计算
配图 栈实现非递归 栈内元素变化图
******************/
  #include <iostream>  
#include <stdio.h>  
#include <stack>  
#include <queue>  
using namespace std;  
 
typedef struct BinNode{  
    char data;  
    bool flag;           //后序非递归中的标记  
    struct BinNode *lchild,*rchild;  
 
}BinNode,*BinTree;  
//按先序创建树    
// char ss[]="12##3##";
 char ss[]="124##x##3y##5##";
//char ss[]="124###3#5##";
/*************************
*          1
*      2     3
*   4           5
*************************/
int i=0;
void creatTree(BinTree &T)  
{    
 
    char c;  
   // cin>>c;
   c=ss[i++];
    if(c=='#')   T=NULL;  
    else{     // T=(BinTree)malloc(sizeof(BinNode));  
        T=new BinNode;  T->data=c;  
         creatTree(T->lchild);  
        creatTree(T->rchild);  
        }  
}  
void visit(BinTree T)  
{  
    if(T->data!='#')   cout<<T->data<<" ";  
}  
void preOrder(BinTree T)               //前序递归  
{  
    if(T)  
    {  
        visit(T);  
        preOrder(T->lchild);  
        preOrder(T->rchild);  
    }  
}  
void inOrder(BinTree T)             //中序递归  
{  
    if(T)  
    {  
        inOrder(T->lchild);  
        visit(T);  
        inOrder(T->rchild);  
    }  
}  
void postOrder(BinTree T)          //后序递归  
{  
    if(T)  
    {  
        postOrder(T->lchild);  
        postOrder(T->rchild);  
        visit(T);  
    }  
}  
void preOrderUnrec(BinTree T)           //非递归前序遍历  
{    
    BinTree p;     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;  
        }  
    }  
}  
void inOrderUnrec(BinTree T)             ////非递归中序遍历  
{    
    BinTree p;     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;  
        }  
    }  
}  
 
void postOrderUnrec1(BinTree T)    //非递归后序遍历  这个思路更好理解一些，下面有解释  
{    
    BinTree p,cur; p=T;  
    stack<BinTree> s;  s.push(p);  
	BinTree pre=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);  
         
        }  
    }  
}  
void postOrderUnrec2(BinTree T)    //非递归后序遍历  
{    
    BinTree cur,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  
         
        }  
    }  
}  
  void postOrderUnrec3(BinTree T)    
{    
    BinTree cur,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);
    }
}
 void postOrderUnrec4(BinTree T)    //非递归后序遍历 不宜用带计数器实现
{    
	BinTree cur,p; p=T;
	BinTree q[10];
        int f=0;int r=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];  
          }
}
void creatbylay(BinTree T)    
{    
     
 char c=ss[i++];
    if(c=='#')   T=NULL;  
    else      {   T=new BinNode;  T->data=c; }
     BinTree cur=T;
     queue<BinTree> q; q.push(cur);  
    while(!q.empty())  
    {  
     cur=q.front(); q.pop();
     if(c=='#')    cur->lchild=NULL;  
     else       {  cur->lchild=new BinNode;  T->data=c; q.push(cur->lchild);}
     if(c=='#')    cur->rchild=NULL;  
     else       {  cur->rchild=new BinNode;  T->data=c; q.push(cur->rchild);}
    }
}
void print_as_tree(BinTree T,int lay)
{
 if(T)
 {
 print_as_tree(T->rchild,lay+1);
	 for(int j=0;j<lay;j++)printf("*");cout<<T->data<<endl;
 print_as_tree(T->lchild,lay+1);
 }
 else return;
}
size_t count_on_klay(BinTree root,size_t k)
{
//假设参数合法；
 if(NULL==root) return 0;
 if(k==1)       return 1;
 return count_on_klay(root->lchild,k-1)+count_on_klay(root->rchild,k-1);
}
size_t count_to_klay(BinTree root,size_t k)
{
//假设参数合法；
   size_t count=0;
for(int i=1;i<=k;i++)
 	count+=count_on_klay(root,i);
  return count;
}
int main()  
{  
    BinTree T;  
     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;  
    return 0;  
}