/**
**由前序，和中序创建二叉树，
**由已知的二叉树，得到他的后序
**/
#include<stdio.h>
#define TElemType char
#define MaxSize 10
typedef enum{Link,Thread}PointerThr;
typedef struct BitThrNode{
TElemType Data;
struct BitThrNode *lchild,*rchild;
PointerThr LTag,RTag;
}BiThrNode;
typedef struct Stack{
BiThrNode *Data;
struct Stack *next;
}Stack;
void InputTree(char *P,char *M); /*输入二叉树*/
void Correspinding(char*,char*,unsigned*); /*求得对应位置*/
void inputlater(BiThrNode*);
main()
{
unsigned PtoM[MaxSize],*Point,*first,i,k,j=0,L=0;
BiThrNode *node,*top,*p,*temp;
BiThrNode* Addr[MaxSize];
/**
char Pre[MaxSize]= "ATBZXCYP";
char Midd[MaxSize] = "TZBACYXP";
**/
char Pre[MaxSize];
char Midd[MaxSize];
memset(PtoM, 0x00,MaxSize*sizeof(unsigned));
InputTree(Pre,Midd);
Correspinding(Pre,Midd,PtoM);
Point = (unsigned*)malloc(MaxSize*sizeof(unsigned));
memset(Point, 0x00,MaxSize*sizeof(unsigned));
node = (BiThrNode*)malloc(sizeof(BiThrNode));
memset(node, 0x00,sizeof(BiThrNode));
node->Data = Pre[0];
top=p= node;
first = Point;
*Point = PtoM[0];
Point++;
printf("%s\n",Pre);
printf("%s\n",Midd);
printf("\n得到对应序列：");
for(i=0;i<10;i++){
printf("%d,",PtoM[i]);
}
printf("\n\n");
/**由前序，和中序创建二叉树**/
printf("\n创建二叉树(过程)：\n");
for(i=1;*(Pre+i);i++)
{
printf("\n第%d次-----(%d %d p=%c)------\n",i,PtoM[i],*(Point-1),p->Data);
if(PtoM[i] == *(Point-1))
{
Point--;
p = Addr[i];
continue;
}
node = (BiThrNode*)malloc(sizeof(BiThrNode));
memset(node, 0x00,sizeof(BiThrNode));
node->Data = Pre[i];
temp = node;
if(PtoM[i]<PtoM[i-1])
{p->lchild = node;
printf("%c ",p->lchild->Data);
for(j=i+1;j<=MaxSize;j++)
{ if(PtoM[j]==*(Point-1))break;/*注意*/
if(PtoM[j]>PtoM[i-1])
{
node = (BiThrNode*)malloc(sizeof(BiThrNode));
memset(node, 0x00,sizeof(BiThrNode));
node->Data = Pre[j];
p->rchild = node;
printf("%c(j=%d %d,%d) ",p->rchild->Data,j,PtoM[j],*(Point-1));
Addr[j] = node;
*Point = PtoM[j];/*注意*/
Point++;
break;
}
}
}else{
p->rchild = node;
printf("%c ",p->rchild->Data);
}
p = temp;
}
printf("\n---------------------\n");
inputlater(top);
getch();
return 0;
}
/***由已知的二叉树，得到他的后序***/
void inputlater(BiThrNode *head)
{int i;
Stack *ST,*S,*pre,*p,*top,*temp;
/*首先建立了两个栈
**（后续排序是左右根，我反放为 根右左） p存放最终的结果
** s暂时存放左值
*/
ST = (Stack*)malloc(sizeof(Stack));
ST->Data = head;/*放的是BiThrNode类型的指针*/
ST->next = NULL;
p = ST;
S = (Stack*)malloc(sizeof(Stack));
S->Data = NULL;
S->next = NULL;
top = pre = S;
do{
if(p->Data->rchild && p->Data->lchild)
{
ST = (Stack*)malloc(sizeof(Stack));
ST->Data = p->Data->rchild;
ST->next = p;
S = (Stack*)malloc(sizeof(Stack));
S->Data = p->Data->lchild;
S->next = pre;
pre = S;
p = ST;
}
if(p->Data->rchild && !p->Data->lchild)
{
ST = (Stack*)malloc(sizeof(Stack));
ST->Data = p->Data->rchild;
ST->next = p;
p = ST;
}
if(!p->Data->rchild && p->Data->lchild)
{
ST = (Stack*)malloc(sizeof(Stack));
ST->Data = p->Data->lchild;
ST->next = p;
p = ST;
}
if((!p->Data->lchild) && (!p->Data->rchild))
{if(pre==top)break;
temp = pre->next;
pre->next = p;
p = pre;
pre =temp;
}
}while(1);
printf("\n由已知的二叉树，得到他的后序:\n\n");
do{
printf("%c ",p->Data->Data);
p=p->next;
}while(p);
}
void Correspinding(char *P,char *M,unsigned *C)
{ int i,j;
for(i=0;*(P+i);i++){
for(j=0;*(M+j);j++)
{
if(M[j]==P[i])C[i]=j;
}
}
}
void InputTree(char *P,char *M)
{
int i;
char c;
printf("请输入前序序列:");
for(i=0;(c=getchar())!='\n';i++)
{
if(c!=',')P[i] = c;
else i--;
}
P[i] = '\0';
printf("请输入中序序列:");
for(i=0;(c=getchar())!='\n';i++)
{
if(c!=',')M[i] = c;
else i--;
}
M[i] = '\0';
}