단서 이 진 트 리 (C 언어)

Description
이 문제 에 서 는 먼저 순서대로 옮 겨 다 니 는 문자열 을 보 여 줍 니 다. 빈 칸 은 빈 하위 노드 를 대표 하고 대문자 로 노드 내용 을 대표 합 니 다.이 문자열 을 통 해 이 진 트 리 를 만 들 고 제목 설명 에 따 른 알고리즘 을 사용 하 십시오. 중간 순 서 는 이 진 트 리 를 옮 겨 다 니 고 중간 순 서 는 이 진 트 리 를 옮 겨 다 니 며 출력 합 니 다.
이 진 트 리 를 옮 겨 다 니 는 과정 에서 일정한 규칙 에 따라 이 진 트 리 의 결점 을 하나의 선형 서열 로 배열 하여 이 진 트 리 에서 결점 의 선 순서 서열 이나 중 순서 서열 또는 후 순서 서열 을 얻 을 수 있다.그러나 이 진 링크 를 저장 구조 로 할 때 노드 의 좌우 아이 정보 만 찾 을 수 있 고 노드 가 임의의 시퀀스 에서 의 전구 와 후계 정 보 를 직접 얻 을 수 없 으 며 이런 정 보 는 옮 겨 다 니 는 동적 과정 에서 만 얻 을 수 있다.이런 정 보 를 저장 하기 위해 서 는 단서 링크 를 사용 해 야 한다.그 중에서 결점 을 가리 키 는 전구 와 후계 의 지침 을 단서 라 고 한다.단 서 를 추가 한 이 진 트 리 를 단서 이 진 트 리 라 고 합 니 다. 
Input
이 진 트 리 를 만 들 기 위해 문자열 S 를 포함 하 는 줄 만 입력 하 십시오.S 가 합 법 적 인 이 진 트 리 로 문자열 을 먼저 옮 겨 다 니 도록 보장 합 니 다. 노드 내용 은 대문자 만 있 고 S 의 길 이 는 100 을 초과 하지 않 습 니 다.
Output
모두 한 줄 에 한 줄 의 문 자 를 포함 하고 중간 순서에 따라 두 갈래 단서 트 리 를 옮 겨 다 니 며 얻 은 노드 내용 을 표시 하 며 알파벳 마다 빈 칸 을 출력 합 니 다.줄 끝 출력 줄 바 꾸 기 에 주의 하 세 요.
Sample Input

ABC  DE G  F   

Sample Output

C B E G D F A 

 
코드 및 설명:
 

#include
#include
typedef struct {
    char ch;
}ElemType; 
typedef enum {Link,Thread} PointerTag;
typedef struct BiTNode{
    ElemType elem;
    struct BiTNode *Lchild;
    struct BiTNode *Rchild;
    PointerTag LTag;
    PointerTag RTag;
}BiTNode,*BiTree;
 
BiTree pre;
void CreatTree(BiTree *T);
 
void InOrderThreading(BiTree *Thrt,BiTree T);
void InThreading(BiTree p);
void InOrderTraverse(BiTree T);
void Z_Traverse(BiTree T);
int main()
{
    BiTree T;
    CreatTree(&T);
    BiTree Thrt;
    InOrderThreading(&Thrt,T);//      
    InOrderTraverse(Thrt);//     
}
void CreatTree(BiTree *T)//          
{
    char a;
    scanf("%c",&a);
    if(a==' ')
    {
        *T=NULL;
    }
    else
    {
        *T=(BiTree)malloc(sizeof(BiTNode));
        (*T)->elem.ch=a;
        (*T)->LTag=Link;//    
        (*T)->RTag=Link;//    
        CreatTree( &( (*T)->Lchild ) );
        CreatTree( &( (*T)->Rchild ) );
    }
}
void InOrderThreading(BiTree *Thrt,BiTree T)
{
    (*Thrt) = (BiTree)malloc(sizeof(BiTNode));
     
    (*Thrt)->Rchild=*Thrt;//     
    (*Thrt)->RTag=Link;//    
    if(!T)//             
    {
        (*Thrt)->Lchild=*Thrt;
        (*Thrt)->LTag=Link;
    } 
    else
    {
        pre=*Thrt;
        (*Thrt)->Lchild=T;
        (*Thrt)->LTag=Link;
        InThreading(T);//    
        pre->Rchild=*Thrt;
        pre->RTag=Thread;
        (*Thrt)->Rchild=pre;
    }
}
void InThreading(BiTree p)//    
{
    if(p)
    {
        InThreading(p->Lchild);
        if(!p->Lchild)//     
        {
            p->LTag=Thread;
            p->Lchild=pre;
        }
        if(!pre->Rchild)//           
        {
            pre->RTag=Thread;
            pre->Rchild=p;
        }
        pre=p;
        InThreading(p->Rchild);
    }
}
void InOrderTraverse(BiTree T)//         
{
    BiTree p;
    p=T->Lchild;
    while(p!=T)
    {
        while(p->LTag==Link)//               
        {
            p=p->Lchild;
        }
        printf("%c ",p->elem.ch); 
        while(p->RTag==Thread&&p->Rchild!=T)//     &&         
        {
            p=p->Rchild;//       
            printf("%c ",p->elem.ch);
        }
        p=p->Rchild;//       
    }
}