[ch 08-3] 이진 트리의 순회

[순회 종류]

■ 그림(중위, 후위, 전위)

1. 중위 순회: 루트 노드의 왼쪽 자식 노드를 먼저 방문 후에 루트 노드를 중간에 방문하는 방식

2. 후위 순회: 루트 노드의 왼쪽 자식, 오른쪽 자식을 방문 후 루트 노드를 마지막에 방문하는 방식

3. 전위 순회: 루트 노드를 먼저 방문 후 왼쪽 자식, 오른쪽 자식을 방문하는 방식

[순회의 재귀]

■ 그림(중위 순회 재귀)

■ 이진 트리를 대상으로 중위 순회를 할 경우의 순회 순서

1단계: 왼쪽 서브 트리의 순회

2단계: 루트 노드의 방문

3단계: 오른쪽 서브 트리의 순회

※ 공집합(NULL) 값을 가진 노드를 방문하기 전까지 하위 단계로 순회를 반복

[소스 코딩]

※ 이전에 사용한 '이진 트리 구현(BinaryTree.h, BinaryTree.c)' 소스를 업데이트해서 사용

■ BinaryTree2.h

#ifndef BINARYTREE2_H_
#define BINARYTREE2_H_
 
typedef struct _bTreeNode        // 이진 트리를 표현 (=노드)
{
    int data;                    // 노드에 저장할 데이터 값
    struct _bTreeNode * left;    // 노드의 왼쪽 서브 트리를 연결할 포인터 변수
    struct _bTreeNode * right;   // 노드의 오른쪽 서브 트리를 연결할 포인터 변수
} BTreeNode;
 
BTreeNode * MakeBTreeNode(void);                // 이진 트리 노드 생성
int GetData(BTreeNode * bt);                    // 노드의 데이터 값 반환
void SetData(BTreeNode * bt, int data);         // 노드에 데이터를 저장
 
BTreeNode * GetLeftSubTree(BTreeNode * bt);     // 노드의 왼쪽 서브 트리의 주소 값을 반환
BTreeNode * GetRightSubTree(BTreeNode * bt);    // 노드의 오른쪽 서브 트리의 주소 값을 반환
 
void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub);     // 전달 받은 'sub' 노드를 'main' 노드의 왼쪽 서브 트리로 연결
void MakeRightSubTree(BTreeNode * main, BTreeNode * sub);    // 전달 받은 'sub' 노드를 'main' 노드의 오른쪽 서브 트리로 연결
 
//////////////////
/* ▼▼ 추가된 부분 ▼▼ */
 
void DeleteTree(BTreeNode * bt);        // 전달 받은 루트 노드와 하위 노드 모두 삭제(후위 순회)
 
typedef void VisitFuncPtr(int data);    // 노드 접근 시 호출(노드의 데이터 출력)
 
void PreorderTraverse(BTreeNode * bt, VisitFuncPtr action);     // 전위 순회
void InorderTraverse(BTreeNode * bt, VisitFuncPtr action);      // 중위 순회
void PostorderTraverse(BTreeNode * bt, VisitFuncPtr action);    // 후위 순회
 
#endif

- 노드를 방문 했을 때 목적은 상황에 따라 달라질 수 있으므로 포인터 함수 'VisitFuncPtr'을 만들어서 사용

  ※ 현재는 메시지 출력 함수를 전달 받아 사용할 예정

■ BinaryTree2.c

#include <stdio.h>
#include <stdlib.h>        // malloc, free 함수를 사용하기 위함
#include "BinaryTree2.h"
 
// 이진 트리 노드 생성 //
BTreeNode * MakeBTreeNode(void)
{
    BTreeNode * nd = (BTreeNode*)malloc(sizeof(BTreeNode));
    nd->left = NULL;
    nd->right = NULL;
    return nd;
}
 
// 노드의 데이터 값 반환 //
int GetData(BTreeNode * bt)
{
    return bt->data;
}
 
// 노드에 데이터를 저장 //
void SetData(BTreeNode * bt, int data)
{
    bt->data = data;
}
 
// 노드의 왼쪽 서브 트리의 주소 값을 반환 //
BTreeNode * GetLeftSubTree(BTreeNode * bt)
{
    return bt->left;
}
 
// 노드의 오른쪽 서브 트리의 주소 값을 반환 //
BTreeNode * GetRightSubTree(BTreeNode * bt)
{
    return bt->right;
}
 
// 전달 받은 'sub' 노드를 'main' 노드의 왼쪽 서브 트리로 연결 //
void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub)
{
    if(main->left != NULL)
        free(main->left);
 
    main->left = sub;
}
 
// 전달 받은 'sub' 노드를 'main' 노드의 오른쪽 서브 트리로 연결 //
void MakeRightSubTree(BTreeNode * main, BTreeNode * sub)
{
    if(main->right != NULL)
        free(main->right);
 
    main->right = sub;
}
 
//////////////////
/* ▼▼ 추가된 부분 ▼▼ */
 
//  전달 받은 루트 노드와 하위 노드 모두 삭제(후위 순회) //
void DeleteTree(BTreeNode * bt)
{
    if(bt == NULL)
        return;
 
    DeleteTree(bt->left);
    DeleteTree(bt->right);
 
    printf("%d ", bt->data);
    free(bt);
}
 
// 전위 순회 //
void PreorderTraverse(BTreeNode * bt, VisitFuncPtr action)
{
    if(bt == NULL)
        return;
 
    action(bt->data);
    PreorderTraverse(bt->left, action);
    PreorderTraverse(bt->right, action);
}
 
// 중위 순회 //
void InorderTraverse(BTreeNode * bt, VisitFuncPtr action)
{
    if(bt == NULL)
        return;
 
    InorderTraverse(bt->left, action);
    action(bt->data);
    InorderTraverse(bt->right, action);
}
 
// 후위 순회 //
void PostorderTraverse(BTreeNode * bt, VisitFuncPtr action)
{
    if(bt == NULL)
        return;
 
    PostorderTraverse(bt->left, action);
    PostorderTraverse(bt->right, action);
    action(bt->data);
}

■ 추가된 함수의 설명

//  전달 받은 루트 노드와 하위 노드 모두 삭제(후위 순회) //
void DeleteTree(BTreeNode * bt)
{
    if(bt == NULL)
        return;
 
    DeleteTree(bt->left);
    DeleteTree(bt->right);
 
    printf("%d ", bt->data);
    free(bt);
}

// 방문한 노드가 'NULL'일 경우

- 해당 노드를 반환

- 방문한 루트 노드의 왼쪽 서브 트리에 대한 삭제 재귀 순회 시작

- 왼쪽 순회가 끝나면 오른쪽 서브 트리에 대한 삭제 재귀 순회 시작

- 두 개의 순회가 전부 끝나면 루트 노드의 데이터를 출력 후 노드 삭제

// 전위 순회 //
void PreorderTraverse(BTreeNode * bt, VisitFuncPtr action)
{
    if(bt == NULL)
        return;
 
    action(bt->data);
    PreorderTraverse(bt->left, action);
    PreorderTraverse(bt->right, action);
}

// 방문한 노드가 'NULL'일 경우

- 해당 노드를 반환

- 포인터 함수인 'VisitFuncPtr'의 'action'을 인자로 받은 함수를 호출

- 루트 노드의 왼쪽 서브 트리에 'action'으로 받은 인자 값을 기준으로 재귀 순회 시작

- 루트 노드의 오른쪽 서브 트리에 'action'으로 받은 인자 값을 기준으로 재귀 순회 시작

// 중위 순회 //
void InorderTraverse(BTreeNode * bt, VisitFuncPtr action)
{
    if(bt == NULL)
        return;
 
    InorderTraverse(bt->left, action);
    action(bt->data);
    InorderTraverse(bt->right, action);
}

// 방문한 노드가 'NULL'일 경우

- 해당 노드를 반환

- 루트 노드의 왼쪽 서브 트리에 'action'으로 받은 인자 값을 기준으로 재귀 순회 시작

- 포인터 함수인 'VisitFuncPtr'의 'action'을 인자로 받은 함수를 호출

- 루트 노드의 오른쪽 서브 트리에 'action'으로 받은 인자 값을 기준으로 재귀 순회 시작

// 후위 순회 //
void PostorderTraverse(BTreeNode * bt, VisitFuncPtr action)
{
    if(bt == NULL)
        return;
 
    PostorderTraverse(bt->left, action);
    PostorderTraverse(bt->right, action);
    action(bt->data);
}

// 방문한 노드가 'NULL'일 경우

- 해당 노드를 반환

- 루트 노드의 왼쪽 서브 트리에 'action'으로 받은 인자 값을 기준으로 재귀 순회 시작

- 루트 노드의 오른쪽 서브 트리에 'action'으로 받은 인자 값을 기준으로 재귀 순회 시작

- 포인터 함수인 'VisitFuncPtr'의 'action'을 인자로 받은 함수를 호출

■ BinaryTree2Main.c

#include <stdio.h>
#include "BinaryTree2.h"
 
void ShowIntData(int data);
 
int main(void)
{
    BTreeNode * bt1 = MakeBTreeNode();    // 노드 'bt1' 생성
    BTreeNode * bt2 = MakeBTreeNode();    // 노드 'bt2' 생성
    BTreeNode * bt3 = MakeBTreeNode();    // 노드 'bt3' 생성
    BTreeNode * bt4 = MakeBTreeNode();    // 노드 'bt4' 생성
    BTreeNode * bt5 = MakeBTreeNode();    // 노드 'bt5' 생성
    BTreeNode * bt6 = MakeBTreeNode();    // 노드 'bt6' 생성
 
    SetData(bt1, 1);    // 노드 'bt1'에 데이터 '1' 저장
    SetData(bt2, 2);    // 노드 'bt2'에 데이터 '2' 저장
    SetData(bt3, 3);    // 노드 'bt3'에 데이터 '3' 저장
    SetData(bt4, 4);    // 노드 'bt4'에 데이터 '4' 저장
    SetData(bt5, 5);    // 노드 'bt5'에 데이터 '5' 저장
    SetData(bt6, 6);    // 노드 'bt6'에 데이터 '6' 저장
 
    MakeLeftSubTree(bt1, bt2);    // 노드 'bt2'를 노드 'bt1'의 왼쪽 서브 트리로 연결
    MakeRightSubTree(bt1, bt3);   // 노드 'bt3'를 노드 'bt1'의 오른쪽 서브 트리로 연결
    MakeLeftSubTree(bt2, bt4);    // 노드 'bt4'를 노드 'bt2'의 왼쪽 서브 트리로 연결
    MakeRightSubTree(bt2, bt5);   // 노드 'bt5'를 노드 'bt2'의 오른쪽 서브 트리로 연결
    MakeRightSubTree(bt3, bt6);   // 노드 'bt6'를 노드 'bt3'의 오른쪽 서브 트리로 연결
 
    printf("전위 순회 출력: ");
    PreorderTraverse(bt1, ShowIntData);     // 노드 'bt1'과 연결된 모든 노드의 데이터를 전위 순회로 출력
    printf("\n");
 
    printf("중위 순회 출력: ");
    InorderTraverse(bt1, ShowIntData);      // 노드 'bt1'과 연결된 모든 노드의 데이터를 중위 순회로 출력
    printf("\n");
 
    printf("후위 순회 출력: ");
    PostorderTraverse(bt1, ShowIntData);    // 노드 'bt1'과 연결된 모든 노드의 데이터를 후위 순회로 출력
    printf("\n\n");
 
    printf("[모든 노드 삭제]\n");
    printf("삭제된 노드: ");
    DeleteTree(bt1);                        // 노드 'bt1'과 연결된 모든 노드의 데이터를 출력 후 삭제
 
    return 0;
}
 
// 노드의 데이터 출력 //
void ShowIntData(int data)
{
    printf("%d ", data);
}

■ 실행결과

■ 그림(실행결과 트리 표현)