14

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

//已知二叉树的先序和中序序列-建立二叉树

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define null 0
#define N 100  //栈、队列的最大值

typedef struct BiTNode{   //树的节点结构定义
  char data;
  struct BiTNode *lchild,*rchild;
}*BiTree;

void post_order(BiTree T)//递归后序遍例
{
    if(T)
    {
		post_order(T->lchild);
        post_order(T->rchild);
		printf("%c",T->data);
    }
}

int op(char* ch,char* ch1,BiTree&T)//根据先序序列和中序序列建树 
{
   int i;
 
   char c[N],c1[N],cs[N],cs1[N];//c[N] 是左子树的先序序列
								//c1[N]是左子树的中序序列
								//cs[N]是右子树的先序序列
								//cs1[N]是右子树的中序序列
   
   
   if(ch[0]=='\0')//如果输入的字符串是空,则返回1
   {
	   T=null;
	   return 1;
   } 
   
   
   if(strlen(ch1)!=strlen(ch))return 0;//如果先序序列和中序序列长度不等,返回0 
  
   
   for(i=0;ch[0]!=ch1[i]&&ch1[i]!='\0';i++)//在中序序列中找到先序序列的第一个元素,下标是i 
   {
     c1[i]=ch1[i];
     c[i]=ch[i+1];
   }
   
   
   if(ch1[i]=='\0')return 0;//如果在中序序列中找不到先序序列的第一个元素,返回0 
   
   
   c1[i]=c[i]='\0';//给c1[N]和c[N]一个结束条件\0 
   
   strcpy(cs,ch+i+1);//把ch指针跳跃i+1的长度后指向的字母给cs ,作为建右子树的第一个参数 
   
   
   strcpy(cs1,ch1+i+1);////把ch1指针跳跃i+1的长度后指向的字母给cs1,作为建右子树的第二个参数
   
   
   if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))return 0;
  
   
   T->data=ch[0];
   
   
   if(!op(c,c1,T->lchild))return 0;//根据左子树的中序和先序，建左子树
   
   if(!op(cs,cs1,T->rchild))return 0;//根据右子树的中序和先序，建右子树

   return 1;
}


int main(int argc, char* argv[])
{
	BiTree T;
	char ch[N];//先序序列
	char ch1[N];//中序序列
	printf("输入先序序列:");
	scanf("%s",ch); 
	printf("输入中序序列:");
	scanf("%s",ch1);
	if(op(ch,ch1,T))//如果建树成功 ,先序输出该树 
	{
		printf("\n先序序列为:");
		post_order(T);
	}
	else 
	printf("输入错误!\n");
		
	return 0;
}