5

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

//层次遍历的非递归算法

#include <iostream>
#include <malloc.h>			
#include <stdio.h>			
#include <stdlib.h>
#define N 50
#define OVERFLOW 0
#define NULL 0

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

typedef struct queue
{
	BiTree elem;
	int front;
	int tail;
}queue;

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); 
	}  
} 


queue* CreateQueue () 
 {							// 构造一个空队列Q
	queue *q;
	q=(queue *) malloc(sizeof (queue));
	if (!q) exit (OVERFLOW);	
    q->elem = (BiTree) malloc(N*sizeof (struct BiTNode));
    if (!q->elem) exit (OVERFLOW);		              
    q->front = q->tail = 0;
     return q;
 }


BiTree SubQueue(queue *q)//出队列函数 
{
	BiTree p;
	p=&(q->elem[q->front]);
	(q->front)++;
	return p;
}


void AddQueue(queue *q,BiTree T)//入队列函数 
{
	q->elem[q->tail]=*T;
	q->tail++;
}


void main()	//层次遍历二叉树的非递归算法的主程序
{
	queue *q;
    BiTree p;
    BiTree b;		
	printf("\n请输按先序序列输入一串字符,当子树为空时,用.来代替\n");
	CreateBiTree(b);
    printf("\n层次遍历二叉树的结果是\n");	
	q=CreateQueue();				
	
	AddQueue(q,b);//令头节点入队					
	
	while(q->front!=q->tail)//若队列不空		
		{
			p=SubQueue(q);//令队列的头元素出队列，并打印。并将此元素的左右孩子(若有的话)入队列
			printf("%c",p->data);
			if(p->lchild) AddQueue(q,p->lchild);
			if(p->rchild) AddQueue(q,p->rchild);
		}
	
	printf("\n");
	
}