13

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

//已知中序和后序遍历_求二叉树

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

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

char c[N],c1[N];

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

int op(char* ch,char* ch1,BiTree &T)
{
   int i;
   
   char c[N],c1[N],cs[N],cs1[N];
   
   if(ch[0]=='\0')//如果输入的字符串是空,则返回1 。。。。输入时使用字符串录入 %s
   {
    T=null;
    return 1;
   } 

   
   if(strlen(ch1)!=strlen(ch))return 0;//如果中序序列和后序序列长度不等(即错误),返回0 
   
   
   for(i=0;ch[0]!=ch1[i]&&ch1[i]!='\0';i++)
   {
     c1[i]=ch1[i];//c1右子树的中序序列 
     c[i]=ch[i+1];//c右子树的后序序列 去根节点，所以+1
   }
   
   
   if(ch1[i]=='\0')//如果在中序序列中没有找到根结点(即错误),返回0 
	   return 0;
   
   
   c1[i]=c[i]='\0';//给c1和ch1字符串加上结束符 
   
   
   strcpy(cs,ch+i+1);//cs是左子树的后序序列 
   
   
   strcpy(cs1,ch1+i+1);//cs1是左子树的中序序列 
   
   
   if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))
	   return 0;
  
   T->data=ch[0];

   if(!op(c,c1,T->rchild))return 0;//根据右子树的中序和后序，建右子树
   if(!op(cs,cs1,T->lchild))return 0;//根据左子树的中序和后序，建左子树
   
   return 1;
}

int fth(char* ch,char* ch1,BiTree&T)//建二叉树
{
  int i,j,k;
  if((j=strlen(ch1))!=(i=strlen(ch)))return 0;//如果中序和后序数组长度不等,返回0 

  for(k=i-1,j=0;k!=-1;k--,j++)//把后续序列ch[N]从后向前赋给c[N] 
  {                           //把中序序列ch1[N]从后向前赋给c1[N]
    c[j]=ch[k];
    c1[j]=ch1[k];
  }
  c[j]=c1[j]='\0';
  
  if(!op(c,c1,T))return 0;//如果有错误返回0,否则建起一棵二叉树T 
  return 1;
}

int main()
{ 
  BiTree T;
  char ch[N];//后序数组 
  char ch1[N];//中序数组 
  
  printf("输入后序序列:");
  scanf("%s",ch);
  printf("输入中序序列:");
  scanf("%s",ch1);
  
  if(fth(ch,ch1,T))//如果建起了二叉树 
  {
    printf("\n先序序列为:");
    Pre_Order(T);
  }
  else
    printf("输入错误!");
  printf("\n");
  	
  return 0;
}