3

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

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

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

typedef struct BiTNode
{
	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;
		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压栈
		
		printf("%c",T->data);//访问节点
		
		T=T->lchild;		//往左下方走一步
	}
	
	printf("%c",T->data);//记录节点
	
	return T;
}


void main()	//先序遍历的非递归算法的主程序
{										
	BiTree t;
	printf("请输按先序序列输入一串字符,当子树为空时,用.来代替：\n");
	
	CreateBiTree(t);
	
	printf("先序遍历二叉树的结果是:");
	
	stack *S;
	S=CreateStack();
	t=GoLeft(t, S);				// 找到最左下的结点
	while(t)							//t非空时
	{ 
		if (t->rchild)					//如果右子树非空，则走到右子树的最左端
		{
			t=t->rchild;
			t=GoLeft(t, S);
		}
		else if (!(S->top==S->base))		// 栈不空时退栈
			{
				t = pop(S);					//右子树为空时，弹出双亲节点
			}
			else
			t = 0;						// 栈空表明遍历结束
	} 
	printf("\n");
		
}