선서 와 중 서 (중 서 와 후 서) 에 따라 이 진 트 리 를 확정 합 니 다.

정말 자신의 지능 이 부족 한 것 을 미워 합 니 다. 이 진 트 리 하나 가 오랫동안 만들어 서 야 알 게 되 었 습 니 다!!어떻게 선서 와 중 서 를 통 해 이 진 트 리 를 확정 합 니까?나의 알고리즘 디자인 방향 은 인터넷 에서 배 운 것 을 참고 하지만 코드 는 스스로 실현 한 것 이 고 사실은 이 진 트 리 를 만 드 는 토대 에서 조건 을 추가 한 것 이다.우 리 는 처음에 선 순위 서열 에서 첫 번 째 데 이 터 를 바탕 으로 중 순위 서열 에서 이 노드 데이터 와 같은 요 소 를 찾 아 중 순위 서열 에서 이 요소 가 있 는 아래 표 시 를 되 돌려 주 었 다 ， 。중간 순서 서열 에서 앞 순서 서열 의 현재 첫 번 째 요소 와 같은 요소 가 있 는 위 치 를 '\ 0' 으로 설정 하고 앞 순서 서열 에 있 는 이 요소 가 있 는 위치 값 을 '\ 0' 으로 설정 합 니 다. 먼저 순서 서열 의 첫 번 째 유효 요소 도 다음 요소 로 바 꿔 야 합 니 다 (즉, 이때 아래 표 시 를 옮 겨 다 니 며 이동 해 야 합 니 다).이 진 트 리 를 만 들 기 전에 하 는 일이 다.이 진 트 리 를 만 드 는 지 재 귀 를 사용 하 는 지, 위 에서 돌아 오 는 아래 표 에 따라 중간 순서 순 서 를 두 부분 으로 나 누 어 왼쪽 이 비어 있다 고 판단 하면 노드 를 만 든 왼쪽 아 이 를 비어 있 고 오른쪽 이 같 습 니 다.비어 있 지 않 으 면 앞부분 은 왼쪽 나무 이 고 후반 부 는 오른쪽 나무 입 니 다.앞 순서 와 중간 순서 앞부분, 그리고 만 든 결점 의 왼쪽 아이 지침 을 전달 합 니 다.재 귀적 호출 함수.앞 순서 와 중간 순서 후반 부, 그리고 만 든 결점 의 오른쪽 아이 지침 을 전달 합 니 다.재 귀적 호출 함수.이상 에서 말 한 것 은 화성 인 들 이 생각 을 이해 하고 이해 하지 못 하 는 것 은 당신들 을 탓 하 는 것 이 아니 라 나 를 탓 하 는 것 입 니 다. 표현 에 있어 서 확실히 논리성 이 부족 합 니 다. 다음은 우리 가 코드 를 보면 됩 니 다 ~ ~ ~

#include
#include
#include
using namespace std;
typedef struct node{
    
    char ch ;
    struct node * l,*r ;
}node_t,*node_l;

void create_tree(node_l * root,char  prelist[],char  midlist[]);
int findIndex(char prelist,char* midlist);
void print(node_l root);
int main(){
    
    node_l root ;
    char prelist[100];
    char midlist[100];
    bzero(prelist,sizeof(prelist));
    bzero(midlist,sizeof(midlist));
    cin>>prelist;
    cin>>midlist;
    create_tree(&root,prelist,midlist);
    print(root);
}
void print(node_l root){

    if(root){
        print(root->l);
        print(root->r);
        cout<<root->ch<<"";
    }
}
//          ，root   ，prelist     ，midlist     
//                
void create_tree(node_l* root,char prelist[],char midlist[]){
    //      ，           ，       ，
    //         。
    static int index = 0;  
    int mid_index ;
    //          ，         ，                 
    mid_index = findIndex(prelist[index],midlist);
    *root = (node_l)malloc(sizeof(node_t));
    //           
    (*root)->ch = prelist[index];
                ‘\0’
    prelist[index++]='\0' ;
    //              '\0'
    midlist[mid_index]='\0';
    //            ，   ，          ，         
    if(midlist[mid_index-1]!='\0'){
        create_tree(&((*root)->l),prelist,midlist);
    }
    //                 
    else{
        (*root)->l = NULL ;
    }
    //         ，    
    if(midlist[mid_index+1]!='\0'){
        create_tree(&((*root)->r),prelist,&midlist[mid_index+1]);
    }
    else{
        (*root)->r = NULL ;
    }
}
//             ，            。
int findIndex(char  pre,char * mid){   
    int i ;
    for(i = 0; *(mid+i)!= '\0' ;i++){
        if(pre == *(mid+i)){
            return i ;
        }
    }
    return 0;
}

뒷 순서 와 중간 순서 로 이 진 트 리 를 만 들 때 똑 같은 이치 에 따라 자신 이 이 를 바탕 으로 규칙 을 찾 아 보면 스스로 회복 할 수 있다

#include
#include
#include
using namespace std;
typedef struct node{
    
    char ch ;
    struct node * l,*r ;
}node_t,*node_l;

void create_tree(node_l * root,char  lastlist[],char  midlist[]);
int findIndex(char last,char* midlist);
void print(node_l root);
int main(){
    
    node_l root ;
    char lastlist[100];
    char midlist[100];
    bzero(lastlist,sizeof(lastlist));
    bzero(midlist,sizeof(midlist));
    cin>>midlist;
    cin>>lastlist;
    create_tree(&root,lastlist,midlist);
    print(root);
}
void print(node_l root){

    if(root){
        cout<<root->ch<<"";
        print(root->l);
        print(root->r);
    }
}
void create_tree(node_l* root,char lastlist[],char midlist[]){
    static int index = strlen(lastlist)-1;
    int mid_index ;    
    
    mid_index = findIndex(lastlist[index],midlist);
    *root = (node_l)malloc(sizeof(node_t));
    (*root)->ch = lastlist[index];

    lastlist[index--]='\0' ;
    if(index==-1)return ;
    midlist[mid_index]='\0';
    if(midlist[mid_index+1]!='\0'){
        create_tree(&((*root)->r),lastlist,&midlist[mid_index+1]);
    }
    else{
        (*root)->r = NULL ;
    }
    if(midlist[mid_index-1]!='\0'){
        create_tree(&((*root)->l),lastlist,midlist);
    }
    else{
        (*root)->l = NULL ;
    }
}

int findIndex(char  last,char * mid){
    
    int i ;
    for(i = 0; *(mid+i)!= '\0' ;i++){
        if(last == *(mid+i)){
            return i ;
        }
    }
    return 0;
}