이 진 트 리 의 코드 구현

이 진 트 리 는 비 선형 구조 이지 만 컴퓨터 에 저장 할 때 는 선형 에 따라 저장 해 야 한다.이 진 트 리 도 하나의 결점 으로 구성 되 어 있 습 니 다. 단지 하나의 결점 에 데 이 터 를 저장 해 야 할 뿐만 아니 라 왼쪽 아이의 지침 과 오른쪽 아이의 지침 도 저장 해 야 합 니 다.그래서 우 리 는 이 진 트 리 를 실현 하려 면 먼저 이 진 트 리 의 구 조 를 가 져 야 한다. 아까 분석 한 바 에 따 르 면 이 진 트 리 구조 중의 변 수 는 세 개 있어 야 한다.코드 는 다음 과 같 습 니 다:

struct BiTNode{

    int data;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
};

   이렇게 두 갈래 나무의 구조 가 생 긴 후에 우 리 는 동적 으로 결점 을 만 들 수 있다.예 를 들 어 우리 가 만 들 려 고 하 는 이 나 무 는 5 개의 요소 가 있 는데 A, B, C, D, E 이다.그러면 노드 를 만 드 는 코드 는 다음 과 같 습 니 다.

struct BiTNode *A = ( struct BiTNode * ) malloc ( sizeof ( struct BiTNode ) );
struct BiTNode *B = ( struct BiTNode * ) malloc ( sizeof ( struct BiTNode ) );
struct BiTNode *C = ( struct BiTNode * ) malloc ( sizeof ( struct BiTNode ) );
struct BiTNode *D = ( struct BiTNode * ) malloc ( sizeof ( struct BiTNode ) );
struct BiTNode *E = ( struct BiTNode * ) malloc ( sizeof ( struct BiTNode ) );

다음은 이 결점 들 을 초기 화하 고 나 무 를 만 드 는 것 이다.이 나 무 는 먼저 순서대로 옮 겨 다 니 며 결 과 는 다음 과 같다.

A->B->C->D->E

중간 순 서 를 옮 겨 다 니 는 결 과 는 다음 과 같 습 니 다.

B->A->D->C->E

나무의 이론 적 인 모양 이 생 긴 후에 우 리 는 이 결점 들 을 연결 하기 시작 해 야 한다.코드 는 다음 과 같 습 니 다:

A->data = 'A';
A->lchild = B;
A->rchild = C;
B->data = 'B';
B->lchild = B->rchild = NULL;
C->data = 'C';
C->lchild = D;
C->rchild = E;
D->data = 'D';
D->lchild = D->rchild = NULL;
E->data = 'E';
E->lchild = E->rchild = NULL;

이 진 트 리 를 만 든 후 이 진 트 리 를 옮 겨 다 니 기 시작 합 니 다.이 진 트 리 는 세 가지 가 있 는데 앞 순서, 중간 순서 와 뒤 순서 가 있다.이 진 트 리 의 옮 겨 다 니 는 것 은 사실상 재 귀 를 통 해 이 루어 진 것 이다.그럼 먼저 이 루 고 순서대로 옮 겨 다 니 세 요.코드 는 다음 과 같 습 니 다:

void PreOrderTraverse ( struct BiTNode *T ){

    if ( T == NULL )
        return;
        
    if ( T != NULL )
    printf ( "%c", T->data );     //      
    if ( T != NULL )
    PreOrderTraverse ( T->lchild );  //     
    if ( T != NULL )
    PreOrderTraverse ( T->rchild );   //     
    
}

이 어 중 서 를 옮 겨 다 니 며 중 서 를 옮 겨 다 니 는 것 은 왼쪽 트 리 를 먼저 방문 한 다음 에 뿌리 결산 점 을 방문 하고 마지막 으로 오른쪽 트 리 를 방문 하 는 것 에 불과 하 다.코드 는 다음 과 같 습 니 다:

void InOrderTraverse ( struct BiTNode *T ){

    if ( T == NULL )
        return;
        
    if ( T != NULL )
        InOrderTraverse ( T->lchild );
    if ( T != NULL )
        printf ( "%c", T->data );
    if ( T != NULL )
        InOrderTraverse ( T->rchild );

}

마지막 으로 뒷 순 서 를 옮 겨 다 니 는 것 이다.뒷 순 서 는 왼쪽 트 리 를 먼저 방문 한 다음 오른쪽 트 리 를 방문 하고 마지막 으로 뿌리 노드 를 방문 하 는 것 입 니 다.코드 는 다음 과 같 습 니 다:

void PostOrderTraverse ( struct BiTNode *T ){

    if ( T == NULL )
        return;
        
    if ( T != NULL )
        PostOrderTraverse ( T->lchild );
    if ( T != NULL )
        PostOrderTraverse ( T->rchild );
    if ( T != NULL )
        printf ( "%c", T->data );

}