[자료구조] 이진 트리(Binary Tree) - 코딩밥상

이진 트리(Binary Tree)란?

앞서 트리에 대한 기본적인 이론을 공부했으니 가장 중요하게 쓰이는 특정 트리들을 정리해보겠습니다. 먼저 이진 트리입니다.

한 문장으로 정의하자면, 하나의 노드가 자식 노드를 최대 2개까지만 가질 수 있는 트리입니다.

즉 모든 노드의 자식 노드 수는 0,1,2 중 하나입니다.

출처 : 위키 백과

---

이진 트리의 종류

-포화 이진 트리(Full Binary Tree)

잎 노드를 제외한 모든 노드가 자식을 둘씩 가진 이진 트리.

따라서 포화 이진 트리는 잎 노드들이 모두 같은 깊이에 위치합니다

-완전 이진 트리(Complete Binary Tree)

잎 노드들이 트리의 왼쪽부터 차곡차곡 채워진 트리.

직관적으로 설명하면, 포화 이진 트리가 되기 전 단계에서 노드가 왼쪽 순서로 차곡차곡 채워진 트리입니다. 잎 노드들 사이에 빈 공간이 있으면 안되겠죠.

-높이 균형 트리(Height Balanced Tree)

뿌리 노드를 기준으로 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 2 이상 차이 나지 않는 이진 트리.

즉 뿌리노드와 연결된 왼쪽과 오른쪽의 서브 트리들의 높이 차이가 2이상 차이 나지 않아야 합니다.

-완전 높이 균형 트리(Completely Height Balanced Tree)

뿌리 노드를 기준으로 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 같은 이진 트리.

 

여기서 잠깐! 이진 트리에서 완전한 형태를 집착하는 이유는

이진 트리는 일반 트리처럼 나무 모양의 자료를 담기 위한 자료구조가 아니라 컴파일러나 검색과 같은 알고리즘의 뼈대가 되는 특별한 자료구조입니다.

특히 이진 트리를 이용한 검색에서는 트리의 노드를 가능한 한 완전한 모습으로 유지해야 높은 성능을 낼 수 있기때문입니다.

---

이진 트리의 순회

순회는 간단히 말해 트리 안에서 노드 사이를 이동하는 연산이라고 할 수 있습니다.

대표적인 방법인 전위,중위,후위 순회 3가지를 정리해보겠습니다.

-전위 순회

뿌리 노드, 왼쪽 하위 트리, 오른쪽 하위 트리 순으로 트리를 순회합니다.

전위 순회를 이용하여 이진 트리를 중첩된 괄호로 표현 할 수 있습니다. 뿌리 노드에서 시작해서 방문하는 노드의 깊이가 깊어질 때마다 괄호를 한 곂씩 두르면 됩니다.

-중위 순회

왼쪽 하위 트리, 뿌리 노드, 오른쪽 하위 트리 순으로 트리를 순회합니다.

중위 순회를 이용하여 수식 트리를 구현할 수 있습니다. 각 노드에 담긴 정보(피연산자 or 연산자)를 받고 각 하위 트리의 시작과 끝에 괄호를 두르면 됩니다.

-후위 순회

왼쪽 하위 트리, 오른쪽 하위 트리, 뿌리 노드 순으로 트리를 순회합니다.

후위 순회를 이용하면 후위 표기식을 나타낼 수 있습니다. 즉 중위 순회로 수식 트리를 구현하면 중위 표기식, 후위 순회로 수식 트리를 구현하면 후위 표기식으로 나타낼 수 있습니다.

---

이진 트리 구현

-노드 선언

typedef struct tagSBTNode{
    struct tagSBTNode* Left;
    struct tagSBTNode* Right;
    
    ElementType Data;
} SBTNode;

-노드 생성/소멸

SBTNode* SBT_CreateNode(ElementType NewData){	//노드 생성
    SBTNode* NewNode = (SBTNode*)malloc(sizeof(SBTNode));
    NewNode->Left = NULL;
    NewNode->Right = NULL;
    NewNode->Data = NewData;
    
    return NewNode;
}

void SBT_DestroyNode(SBTNode* Node){	//노드 소멸
    free(Node);
}

 

-전위 순회 출력

void SBT_PreorderPrintTree(SBTNode* Node){	//전위 순회
    if(Node == NULL) return;
    
    cout<<Node->Data<<' ';
    SBT_PreorderPrintTree(Node->Left);
    SBT_PreorderPrintTree(Node->Right);
}

-중위 순회 출력

void SBT_InorderPrintTree(SBTNode* Node){	//중위 순회
    if(Node == NULL) return;
    
    SBT_InorderPrintTree(Node->Left);
    cout<<Node->Data<<' ';
    SBT_InorderPrintTree(Node->Right);
}

-후위 순회 출력

void SBT_PostorderPrintTree(SBTNode* Node){	//후위 순회
    if(Node == NULL) return;
    
    SBT_PostorderPrintTree(Node->Left);
    SBT_PostorderPrintTree(Node->Right);
    cout<<Node->Data<<' ';
}

 

-트리 소멸

트리를 구축할 때는 노드들의 순서가 문제되지 않지만, 트리를 파괴할 때에는 반드시 잎 노드부터 자유 저장소에서 순차적으로 해제해야 합니다. 따라서 잎 노드부터 방문하여 뿌리 노드까지 거슬러 올라가는 후위 순회를 이용합니다.

void SBT_DestroyTree(SBTNode* Node){	//후위 순회를 이용하여 트리 소멸
    if(Node == NULL) return;
    
    SBT_DestroyNode(Node->Left);
    SBT_DestroyNode(Node->Right);
    SBT_DestroyNode(Node);
}