4

1、猴子选大王 2、约瑟夫环 3、迷宫求解 4、回文游戏 5、地图四染色问题 6、八皇后问题 7、原四则表达式求值 8、k阶斐波那契序列 9、遍历二叉树 10、编写DFS算法的非递归

//后序遍历二叉树的非递归算法.

#include <malloc.h>
#include <stdlib.h>
#include <stdio.h>	

#define OVERFLOW 0
#define STACKSIZE 50
#define ADD	20		

typedef struct BiTNode
{
	int sign;
	char data;
	struct BiTNode *lchild;
	struct BiTNode *rchild;		
}*BiTree;		

typedef struct stack
{
	BiTree *base;
	BiTree *top;
	int stacksize;		//规定堆栈的大小
}stack;


void CreateBiTree(BiTree &T)	//先序扩展序列建立二叉树的递归算法 
{  
	char ch;
	scanf("%c",&ch);
	if (ch=='.') 
		T=NULL;		
	else 
	{ 
		if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))
			exit(OVERFLOW);
		T->data=ch;
		T->sign=0;
		CreateBiTree(T->lchild); 
		CreateBiTree(T->rchild); 
	}  
} 


stack* CreateStack()	//构造一个空栈
{
	stack *s=(stack*)malloc(sizeof(stack));
	if(!s)	exit(OVERFLOW);
	
	s->base=(BiTree*)malloc(STACKSIZE*sizeof(BiTree));
	if(!s->base) exit (OVERFLOW);
	
	s->top=s->base;
	s->stacksize=STACKSIZE;
	return s;
}


void push(stack *s, BiTree i)			//压栈
{
	if(s->top-s->base>=s->stacksize)	//栈满，追加存储空间
	{
		s->base = (BiTree*)realloc(s->base,(s->stacksize+ADD)*sizeof(BiTree));
		if(!s->base)	exit(OVERFLOW);			
		s->top=s->base+s->stacksize;
		s->stacksize=s->stacksize+ADD;
	}
	*(s->top)=i;
	(s->top)++;
}


BiTree pop(stack *s)	//出栈
{
	BiTree i;
	if(s->top==s->base)
		return 0;
	else
	{
		i=*(--s->top);
		return i;
	}
}


BiTree GoLeft(BiTree T, stack *S)
{					
	if (!T)				
		return 0;
	while (T->lchild)		//T->lchild非空
	{  
		push(S,T);			//把T压栈
		T=T->lchild;		//往左下方走一步
	}
	return T;
}


void main()	//后序遍历的非递归算法的主程序
{										
	BiTree t;
	printf("请输按先序序列输入一串字符,当子树为空时,用.来代替:\n");
	CreateBiTree(t);
	stack *S;
	printf("\n后序遍历二叉树的结果是:");
	
	S=CreateStack();
	t=GoLeft(t, S);				// 找到最左下的结点
	while(t)							//t非空时
	{ 
		if( (!(t->rchild))||(t->sign==1))//如果此节点没有右孩子，输出此节点；如果此节点曾经被访问过，输出此节点；					
			printf("%c",t->data);
		
		
		if ((t->sign==0)&&(t->rchild))	//若此节点未标记且有右孩子，就标记次节点，并且找到右子树的最左下节点	
			{
				t->sign=1;					
				push(S, t);
				
				t=t->rchild;
				t=GoLeft(t, S);
			}
		
		
		else if (!(S->top==S->base))		//若此节点没有右孩子或曾经被标记 且 栈不空退栈
					t = pop(S);					
		     else
					t = 0;	             //栈空结束while循环，结束遍历
	}
	printf("\n"); 
	
}