반복 시퀀스에서 두 갈래 트리 복원

1804 단어
두 갈래 나무의 정의에 따르면 먼저 루트 노드를 방문한 다음에 왼쪽 트리를 먼저 훑어보고 마지막으로 오른쪽 트리를 훑어본다.따라서 서열 중의 첫 번째 노드는 반드시 두 갈래 나무의 뿌리 노드이다.그 밖에 두 갈래 나무의 중차 역행은 먼저 중차 역행 루트 노드의 왼쪽 서브 트리를 방문한 다음에 루트 노드를 방문하고 마지막으로 중차 역행 루트 노드의 오른쪽 서브 트리를 방문한다. 따라서 중차 역행 서열에서 루트 노드의 왼쪽 서브 서열은 두 서브 서열로 나눌 수 있다. 루트 노드의 왼쪽은 왼쪽 서브 트리가 대응하는 중차 서열이고 루트 노드의 오른쪽은 오른쪽 서브 트리가 대응하는 중차 서열이다.이 두 개의 하위 서열에 따라 선행 역행 서열에서 대응하는 왼쪽 트리와 오른쪽 트리를 찾을 수 있다. 이때의 왼쪽 트리 서열의 첫 번째 노드는 왼쪽 트리의 뿌리 노드이고 오른쪽 트리 서열의 첫 번째 노드는 오른쪽 트리의 뿌리 노드이다. 그러면 왼쪽 오른쪽 트리의 뿌리 노드를 확정할 수 있다. 다음은 왼쪽 트리의 왼쪽 트리를 구분하고 이렇게 분류하여 선행 역행 노드를 모두 취할 때유일하게 이 두 갈래 나무를 회복했다.마찬가지로 뒷차례와 중간차례도 유일하게 두 갈래 나무를 정할 수 있다.
먼저 차례차례 반복하고, 중차례차례 반복하여 두 갈래 나무를 확정한다.
void Pre_In_Order(char pred[],char ind[],int i,int j,int k, int h,BiTNode **p){
    //i,j ， ；k,h ， 
    int m;
    *p=(BiTNode*)malloc(sizeof(BiTNode));
    (*p)->data=pred[i];
    m=k;
    while(pred[i]!=ind[m]){
        m++;
    } 
    if(m==k){
        // 
        (*p)->lchild=NULL; 
    }
    else{
        Pre_In_Order(pred,ind,i+1,i+m-k,k,m-1,&(*p)->lchild);
    }
    if(m==h){
        // 
        (*p)->rchild=NULL;
    }
    else{
        Pre_In_Order(pred,ind,i+m-k+1,j,m+1,h,&(*p)->rchild); 
    } 
}

중간 순서, 뒤 순서로 두 갈래 트리 확정
void Post_In_Order(char post[],char ind[],int i,int j,int k, int h,BiTNode **p){
    //i,j ， ；k,h ， 
    int m;
    *p=(BiTNode*)malloc(sizeof(BiTNode));
    (*p)->data=post[j];
    m=k;
    while(post[j]!=ind[m]){
        m++;
    } 
    if(m==k){
        // 
        (*p)->lchild=NULL; 
    }
    else{
        Post_In_Order(post,ind,i,i+m-k-1,k,m-1,&(*p)->lchild);
    }
    if(m==h){
        // 
        (*p)->rchild=NULL;
    }
    else{
        Post_In_Order(post,ind,i+m-k,j-1,m+1,h,&(*p)->rchild); 
    } 
}
두 갈래 나무 관련 필기시험 문제 (3)
이미 알고 있는 두 갈래 나무의 앞 순서와 중간 순서, 두 갈래 나무 재건_메모

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage