[Data Structure] Chapter 08: 트리(Tree)

계층적 관계(Hierarchical Relationship)를 표현하는 자료구조인 트리(Tree)를 이해하고,
트리를 대표하는 이진트리를 이용해 수식 트리를 구현해보자.

 

 

트리

• 트리(Tree): 트리는 계층적 관계(Hierarchical Relationship)를 표현하는 자료구조이다.

트리의 구조

• 노드(node): 트리의 구성요소에 해당하는 A, B, C, D, E, F와 같은 요소
• 간선(edge): 노드와 노드를 연결하는 연결선
• 루트 노드(root node): 트리 구조에서 최상위에 존재하는 A와 같은 노드
• 단말 노드(terminal node): 아래로 또 다른 노드가 연결되어 있지 않은 E, F, C, D와 같은 노드
• 내부 노드(internal node): 단말 노드를 제외한 모든 노드로 A, B와 같은 노드
• 레벨(level): 각 층별로 숫자를 매겨서, 이를 트리의 '레벨'이라 칭한다.
• 높이(height): 트리의 최고 레벨을 가리켜 '높이'라 한다.

• 노드 A는 노드 B, C, D의 parent node이다.
• 노드 B, C, D는 노드 A의 child node이다.
• 노드 B, C, D는 부모 노드가 같으므로, 서로 sibling node이다.

 

서브 트리

• 서브 트리(sub tree): 큰 트리에 속하는 작은 트리를 뜻한다.

 

서브 트리

 

이진 트리

• 이진 트리는 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어진다.
• 이진 트리는 나뉘어진 두 서브 트리도 모두 이진 트리여야 한다.
• 노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면, 공집합(empty set) 노드가 존재하는 것으로 간주한다.

 

이진 트리

 

포화 이진 트리와 완전 이진 트리

• 포화 이진 트리(full binary tree): 모든 레벨이 꽉 찬 이진 트리를 의미한다.
• 완전 이진 트리(complete binary tree): 노드가 빈 틈 없이 채워진 이진 트리를 의미한다.

좌측부터 포화 이진 트리, 완전 이진 트리

 

 

배열 기반 이진 트리의 구현

배열 기반 이진 트리

• 노드 번호를 기준으로 데이터가 저장되는 배열의 위치를 결정한다.

 

 

연결 리스트 기반 이진 트리의 구현

• 연결 리스트 기반의 구성 형태가 트리와 일치하기 때문에 구현하기 용이하다.

연결 리스트 기반 이진 트리

 

이진 트리 자료구조의 ADT

BTreeNode * MakeBTreeNode(void);
- 이진 트리 노드를 생성하여 그 주소 값을 반환한다.

BTData GetData(BtreeNode * bt);
- 노드에 저장된 데이터를 반환한다.

void SetData(BTreeNode * bt, BTData data);
- 노드에 데이터를 저장한다. data로 전달된 값을 저장한다.

BTreeNode * GetLeftSubTree(BTreeNode * bt);
- 왼쪽 서브 트리의 주소 값을 반환한다.

BTreeNode * GetRightSubTree(BTreeNode * bt);
- 오른쪽 서브 트리의 주소 값을 반환한다.

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub);
- 왼쪽 서브 트리를 연결한다

void MakeRightSubTree(BTreeNode * main, BTreeNode * sub);
- 오른쪽 서브 트리를 연결한다

 

파일명: BinaryTree.h

#ifndef __BINARY_TREE_H__
#define __BINARY_TREE_H__

typedef int BTData;

typedef struct _bTreeNode
{
    BTData data;
    struct _bTreeNode * left;
    struct _bTreeNode * right;
} BTreeNode;

BTreeNode * MakeBTreeNode(void);
BTData GetData(BTreeNode * bt);
void SetData(BTreeNode * bt, BTData data);

BTreeNode * GetLeftSubTree(BTreeNode * bt);
BTreeNode * GetRightSubTree(BTreeNode * bt);

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub);
void MakeRightSubTree(BTreeNode * main, BTreeNode * sub);

#endif

 

파일명: BinaryTree.c

#include "BinaryTree.h"
#include <stdio.h>
#include <stdlib.h>

BTreeNode * MakeBTreeNode(void)
{
    BTreeNode * newNode = (BTreeNode*)malloc(sizeof(BTreeNode));
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}

BTData GetData(BTreeNode * bt)
{
    return bt->data;
}

void SetData(BTreeNode * bt, BTData data)
{
    bt->data = data;
}

BTreeNode * GetLeftSubTree(BTreeNode * bt)
{
    return bt->left;
}

BTreeNode * GetRightSubTree(BTreeNode * bt)
{
    return bt->right;
}

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub)
{
    if(main->left != NULL)
        free(main->left);

    main->left = sub;
}

void MakeRightSubTree(BTreeNode * main, BTreeNode * sub)
{
    if(main->right != NULL)
        free(main->right);

    main->right = sub;
}

 

파일명: BinaryTreeMain.c

#include <stdio.h>
#include "BinaryTree.h"

int main(void)
{
    BTreeNode * bt1 = MakeBTreeNode();
    BTreeNode * bt2 = MakeBTreeNode();
    BTreeNode * bt3 = MakeBTreeNode();
    BTreeNode * bt4 = MakeBTreeNode();

    SetData(bt1, 1);
    SetData(bt2, 2);
    SetData(bt3, 3);
    SetData(bt4, 4);

    MakeLeftSubTree(bt1, bt2);
    MakeRightSubTree(bt1, bt3);
    MakeLeftSubTree(bt2, bt4);

    printf("%d \n", GetData(GetLeftSubTree(bt1)));
    printf("%d \n", GetData(GetLeftSubTree(GetLeftSubTree(bt1))));

    return 0;
}

2 
4

 

 

 

이진 트리의 순회

순회의 세 가지 방법

• 전위 순회(Preorder Traversal)
• 중위 순회(Inorder Traversal)
• 후위 순회(Postorder Traversal)

좌측부터 중위 순회, 후위 순회, 전위 순회

 

순회의 재귀적 표현

이진 트리의 중위 순회

 

• 1단계: 왼쪽 서브 트리의 순회
• 2단계: 루트 노드의 방문
• 3단계: 오른쪽 서브 트리의 순회

 

 파일명: BinaryTree2.h

#ifndef __BINARY_TREE_H__
#define __BINARY_TREE_H__

typedef int BTData;

typedef struct _bTreeNode
{
    BTData data;
    struct _bTreeNode * left;
    struct _bTreeNode * right;
} BTreeNode;

BTreeNode * MakeBTreeNode(void);
BTData GetData(BTreeNode * bt);
void SetData(BTreeNode * bt, BTData data);

void DeleteTree(BTreeNode * bt);

BTreeNode * GetLeftSubTree(BTreeNode * bt);
BTreeNode * GetRightSubTree(BTreeNode * bt);

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub);
void MakeRightSubTree(BTreeNode * main, BTreeNode * sub);

typedef void (*VisitFuncPtr)(BTData data);

void PreorderTraverse(BTreeNode * bt, VisitFuncPtr action);
void InorderTraverse(BTreeNode * bt, VisitFuncPtr action);
void PostorderTraverse(BTreeNode * bt, VisitFuncPtr action);

#endif

 

 파일명: BinaryTree2.c

#include "BinaryTree2.h"
#include <stdio.h>
#include <stdlib.h>

BTreeNode * MakeBTreeNode(void)
{
    BTreeNode * newNode = (BTreeNode*)malloc(sizeof(BTreeNode));
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}

BTData GetData(BTreeNode * bt)
{
    return bt->data;
}

void SetData(BTreeNode * bt, BTData data)
{
    bt->data = data;
}

void DeleteTree(BTreeNode * bt)
{
    if(bt->data == NULL)
        return;
    
    DeleteTree(bt->left);
    DeleteTree(bt->right);

    free(bt);
}

BTreeNode * GetLeftSubTree(BTreeNode * bt)
{
    return bt->left;
}

BTreeNode * GetRightSubTree(BTreeNode * bt)
{
    return bt->right;
}

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub)
{
    if(main->left != NULL)
        free(main->left);

    main->left = sub;
}

void MakeRightSubTree(BTreeNode * main, BTreeNode * sub)
{
    if(main->right != NULL)
        free(main->right);

    main->right = sub;
}

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);
}

 

 파일명: BinaryTreeMain2.c

#include <stdio.h>
#include "BinaryTree2.h"

void ShowIntData(int data);

int main(void)
{
    BTreeNode * bt1 = MakeBTreeNode();
    BTreeNode * bt2 = MakeBTreeNode();
    BTreeNode * bt3 = MakeBTreeNode();
    BTreeNode * bt4 = MakeBTreeNode();
    BTreeNode * bt5 = MakeBTreeNode();
    BTreeNode * bt6 = MakeBTreeNode();

    SetData(bt1, 1);
    SetData(bt2, 2);
    SetData(bt3, 3);
    SetData(bt4, 4);
    SetData(bt5, 5);
    SetData(bt6, 6);

    MakeLeftSubTree(bt1, bt2);
    MakeRightSubTree(bt1, bt3);
    MakeLeftSubTree(bt2, bt4);
    MakeRightSubTree(bt2, bt5);
    MakeRightSubTree(bt3, bt6);

    PreorderTraverse(bt1, ShowIntData);
    printf("\n");
    InorderTraverse(bt1, ShowIntData);
    printf("\n");
    PostorderTraverse(bt1, ShowIntData);
    printf("\n");

    return 0;
}

void ShowIntData(int data)
{
    printf("%d ", data);
}

1 2 4 5 3 6 
4 2 5 1 3 6 
4 5 2 6 3 1

 

 

 

수식 트리의 구현

• 문자열 형태의 수식을 수식 트리로 표현하면 컴파일러의 수식해석이 좋아진다.

4*2+7-1의 수식 트리

• 연산의 결과가 연산자 노드 자리를 대체하는 방식으로 진행된다.
• 후위 표기법이 수식 트리 형태로 바꾸기 용이하다.
• 따라서, 중위 표기법의 수식 -> 후위 표기법의 수식 -> 수식 트리 순서로 수식 트리를 구현하는 것이 좋다. 
• 수식 트리를 구현하기 위해서는 이진 트리, 스택 자료구조가 필요하다.
• 같은 경로에 이전에 구현한 BinaryTree2.h,BinaryTree2.c, ListBaseStack.h,ListBaseStack.c를 포함하여 구현하겠다.

 

파일명: ExpressionTree.h

#ifndef __EXPRESSION_TREE_H__
#define __EXPRESSION_TREE_H__

#include "BinaryTree2.h"

BTreeNode * MakeExpTree(char exp[]);    //수식 트리 구성
int EvaluateExpTree(BTreeNode * bt);    //수식 트리 계산

void ShowPrefixTypeExp(BTreeNode * bt); //전위 표기법 기반 출력
void ShowInfixTypeExp(BTreeNode * bt);  //중위 표기법 기반 출력
void ShowPostfixTypeExp(BTreeNode * bt);    //후위 표기법 기반 출력

#endif

 

파일명: ExpressionTree.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "ListBaseStack.h"
#include "BinaryTree2.h"

BTreeNode * MakeExpTree(char exp[])
{
    Stack stack;
    BTreeNode * pnode;

    int expLen = strlen(exp);
    int i;

    StackInit(&stack);

    for(i=0; i<expLen; i++)
    {

        pnode = MakeBTreeNode();

        if (isdigit(exp[i]))
        {
            SetData(pnode, exp[i] - '0');
        }
        else
        {
            MakeRightSubTree(pnode, SPop(&stack));
            MakeLeftSubTree(pnode, SPop(&stack));
            SetData(pnode, exp[i]);
        }

        SPush(&stack, pnode);
    }

    return SPop(&stack);
}

int EvaluateExpTree(BTreeNode * bt)
{
    int op1, op2;

    if(GetLeftSubTree(bt)==NULL && GetRightSubTree(bt)==NULL)
        return GetData(bt);

    op1=EvaluateExpTree(GetLeftSubTree(bt));
    op2=EvaluateExpTree(GetRightSubTree(bt));

    switch(GetData(bt))
    {
    case '+':
        return op1+op2;
    case '-':
        return op1-op2;
    case '*':
        return op1*op2;
    case '/':
        return op1/op2;
    }
}

void ShowNodeData(int data)	//함수 포인터 매개변수로 전달될 함수
{
    if(0<data && data<=9)
        printf("%d ", data);
    else
        printf("%c ", data);    
}

void ShowPrefixTypeExp(BTreeNode * bt)
{
    PreorderTraverse(bt, ShowNodeData);
}

void ShowInfixTypeExp(BTreeNode * bt)
{
    InorderTraverse(bt, ShowNodeData);    
}

void ShowPostfixTypeExp(BTreeNode * bt)
{
    PostorderTraverse(bt, ShowNodeData);
}

 

파일명: ExpressionTreeMain.c

#include <stdio.h>
#include "ExpressionTree.h"

int main(void)
{
    char exp[] = "12+7*";
    BTreeNode * eTree = MakeExpTree(exp);

    printf("전위 표기법의 수식: ");
    ShowPrefixTypeExp(eTree); printf("\n");

    printf("중위 표기법의 수식: ");
    ShowInfixTypeExp(eTree); printf("\n");

    printf("후위 표기법의 수식: ");
    ShowPostfixTypeExp(eTree); printf("\n");

    printf("연산의 결과: %d \n", EvaluateExpTree(eTree));

    return 0;
}

전위 표기법의 수식: * + 1 2 7 
중위 표기법의 수식: 1 + 2 * 7 
후위 표기법의 수식: 1 2 + 7 * 
연산의 결과: 21

 

 

문제 08-2

void ShowInfixTypeExp(BTreeNode * bt)
{
    if(bt==NULL)
        return;
    if(bt->left!=NULL || bt->right!=NULL)
        printf("( ");

    ShowInfixTypeExp(bt->left);
    ShowNodeData(bt->data);
    ShowInfixTypeExp(bt->right);

    if(bt->left != NULL || bt->right != NULL)
        printf(") ");
}

 

 함수를 위와 같이 바꿔주면 된다.

---

참고자료

• 윤성우, <윤성우의 열혈 자료구조>, 오렌지미디어, 2022.04.11