5.cpp

都是以前随手编写的笑程序:总的来说只有五个<回文游戏,层次遍历二叉树,猴子选大王,先序、中序、后序遍历的递归算法等等> 如果对你又帮助你就下来看看吧

//5.后序遍历的非递归算法
#define STACK_INIT_SIZE 100//存储空间初始分量
#define STACKINCREMENT 10//存储空间分配增量
#include<stdio.h>
#include<stdlib.h>
#include<iostream.h>
   typedef struct BTNode
   { //定义树的存储结构
	 char data;
     BTNode *lchild,*rchild;}* BTree;
   typedef struct 
   {  //定义栈的存储结构
	  BTree *base, *top;
	  int *ibase, mark, stacksize;	
   }SqStack;
   int CreateBTree(BTree &BT)
   {  //按先序建立二叉树
	   char ch=' ';scanf("%c",&ch);
	    if(ch==' ')BT=NULL;
	     else
		 {
		  if(!(BT=(BTree)malloc(sizeof(BTree))))return 0;	
		  BT->data=ch;
		  CreateBTree(BT->lchild);
		  CreateBTree(BT->rchild);
	}return 1;
   }
   void InitStack(SqStack &Sq)
   {   //初始化栈
	   Sq.base=(BTree *)malloc(STACK_INIT_SIZE*sizeof(BTree));
	   Sq.ibase=(int *)malloc(STACK_INIT_SIZE*sizeof(int));
	   Sq.top=Sq.base;
	   Sq.mark=0;
	   Sq.stacksize=STACK_INIT_SIZE;
   } 
   int StackEmpty(SqStack S)
   {//判空栈
	   if(S.top==S.base)return 1;
	   return 0;
   }
   void Push(SqStack &S,BTree e,int i)
   {  //入栈  
	   //(其中用i来选择对树的左或右子树的操作)
	   if(S.top-S.base>=S.stacksize)
	   { S.base=(BTree *)realloc(S.base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(BTree));
		 S.top=S.base+S.stacksize;
		 S.stacksize+=STACKINCREMENT;
	   }
	   *(S.top)=e;   S.ibase[S.mark]=i;
	   S.mark++;     S.top++;
   }
   int Pop(SqStack &S,BTree *e,int &i)
   {   if(S.top==S.base)return 0;	
	   S.top--;         *e=*S.top;
	   S.mark--;        i=S.ibase[S.mark];	
	   return 1;
   }//出栈  (其中用i来选择对树的左或右子树的操作)
   void houTraverse(BTree T)
   {  //后序非递归遍历
	   SqStack s;      int i=0;
	   InitStack(s);   BTree p;
	   p=T;
	   Push(s,p,0);
	   while(!StackEmpty(s))
	   {Pop(s,&p,i);
	     switch(i)
		 {case 0:  Push(s,p,1);//i为0对左子树操作
	               if(p->lchild)   Push(s,p->lchild,0); break;
    	  case 1:  Push(s,p,2);//i为1对右子树操作
		           if(p->rchild)   Push(s,p->rchild,0); break;
		  case 2:  cout<<p->data;//i为2输出
		 }
	   }
   }

   void main()
   {   BTree T;
	   cout<<"输入结点的先序扩展序列:"<<endl;   CreateBTree(T);
	   cout<<"\n非递归后序遍历为：";            houTraverse(T);
	   cout<<endl;
   }
  /*输入结点的先序扩展序列:
   ab c  de  f
  非递归后序遍历为：cbefda */