2018년 8월 7일 화요일

자구/이진 트리(Binary Tree) - 수정중

1. 개요

이진 트리는 비선형 자료구조의 일종인데, 하나의 부모 노드에 두 개의 자식 노드가 연결된 형태의 트리(tree)이다. 일단 트리가 뭔지 살펴보고, 이진 트리가 어떤 장점이 있는지를 살펴보자. 그리고 이진 트리를 만들면서 동시에 이진 트리와 스택(stack)을 이용한 간단한 계산기를 구현해보자.

2. 이진 트리를 왜 쓰는가

우선 트리는 그래프의 일종인데, 회로가 없고 서로 다른 두 노드를 잇는 길이 하나만 존재한다. 최상위 노드는 루트 노드라고 하며, 직접 연결된 상위 노드를 부모 노드, 하위 노드를 자식 노드라고 한다.
한 부모 노드에 두 개의 자식 노드만 연결된 트리를 이진 트리라고 부른다. 그런데 자식 노드에는 또 다시 다른 자식 노드들이 있을 수 있다. 자식 노드가 없는 노드도 있을텐데 그런 노드를 말단 노드 혹은 잎 노드(leaf node)라고 부른다.
자식 노드가 또 자식 노드를 가지는 특성 때문에 이진 트리는 재귀적으로 구현한다. 아래의 코드를 보면 재귀적이다.

3. 데이터의 저장과 삭제

이진 트리에 데이터를 저장하고 삭제하는 것은

4. 이진 트리의 순회

데이터를 저장하고 또 삭제했으니, 이진 트리에 있는 데이터를 탐색해보자. 트리의 데이터들을 한번 쭉 보려면 이 트리를 순회해야 하는데, 그 방법은 세 가지가 있다. 전위 순회(Preorder), 중위 순회(Inorder), 후위 순회(Postorder) 세 가지인데, 각각은 루트 노드를 언제 방문하느냐가 다르다. 전위는 처음, 중위는 중간, 후위는 마지막이다.

이걸 이용해서 간단한 계산기를 만들 수 있다. 구현 연습용으로 좋은 것 같다. 윤성우의 <열혈 자료구조>에 소개된 내용이다.

윤성우 책의 예시에는 이진트리 헤더/실행 파일과 스택 헤더/실행 파일, 그리고 이진트리를 이용한 수식계산 헤더/실행 파일 + 메인파일까지 해서 파일이 7개나 된다. 너무 많아서 귀찮지만 한번 복붙해본다.

C 소스코드


1. 이진트리 헤더파일
#ifndef __BINARY_TREE_H__
#define __BINARY_TREE_H__
typedef int Data;
typedef struct _Node{
    Data data;
    struct _Node* left;
    struct _Node* right;
} Node;
Node* createNode(void);
Data getData(Node* bt);
void setData(Node* bt, Data data);
Node* getLeftSub(Node* bt);
Node* getRightSub(Node* bt);
void makeLeftSub(Node* mainbt, Node* subbt);
void makeRightSub(Node* mainbt, Node* subbt);
typedef void Visit(int data);
void PreorderTraverse(Node* bt, Visit act);
void InorderTraverse(Node* bt, Visit act);
void PostorderTraverse(Node* bt, Visit act);
void deleteTree(Node* bt);
#endif
cs


2. 이진트리 실행파일
#include <stdio.h>
#include <stdlib.h>
#include "BinaryTree.h"
Node* createNode(void){
    Node* node = (Node*)malloc(sizeof(Node));
    node->left = NULL;
    node->right = NULL;
    return node;
}
Data getData(Node* bt){
    return bt->data;
}
void setData(Node* bt, Data data){
    bt->data = data;
}
Node* getLeftSub(Node* bt){
    return bt->left;
}
Node* getRightSub(Node* bt){
    return bt->right;
}
void makeLeftSub(Node* mainbt, Node* subbt){
    if(mainbt->left != NULL){
        free(mainbt->left);
    }
    mainbt->left = subbt;
}
void makeRightSub(Node* mainbt,Node* subbt){
    if(mainbt->right != NULL){
        free(mainbt->right);
    }
    mainbt->right = subbt;
}
void PreorderTraverse(Node* bt, Visit act){
    if(bt == NULL)
        return;
    act(bt->data);
    PreorderTraverse(bt->left, act);
    PreorderTraverse(bt->right, act);
}
void InorderTraverse(Node* bt, Visit act){
    if(bt == NULL)
        return;
    
    InorderTraverse(bt->left, act);
    act(bt->data);
    InorderTraverse(bt->right, act);
}
void PostorderTraverse(Node* bt, Visit act){
    if(bt == NULL)
        return;
    
    PostorderTraverse(bt->left, act);
    PostorderTraverse(bt->right, act);
    act(bt->data);
}
void deleteTree(Node* bt){
    if(bt == NULL)
        return;
    
    deleteTree(bt->left);
    deleteTree(bt->right);
    printf("%d를 담은 노드 삭제\n", bt->data);
    free(bt);
}
cs


위의 두 코드는 이진트리의 헤더 및 실행파일이다.


3. 스택 헤더파일
#ifndef __STACK_H__
#define __STACK_H__
#define TRUE 1
#define FALSE 0
#include "BinaryTree.h"
typedef Node* NodeData;
typedef struct _StackNode{
    NodeData data;
    struct _StackNode* next;
} StackNode;
typedef struct _Stack{
    StackNode* head;
} Stack;
void StackInit(Stack* pstack);
int StackIsEmpty(Stack* pstack);
void StackPush(Stack* pstack, NodeData data);
NodeData StackPop(Stack* pstack);
NodeData StackPeek(Stack* pstack);
#endif
cs


4. 스택 실행파일
#include <stdio.h>
#include <stdlib.h>
#include "Stack.h"
void StackInit(Stack* pstack){
    pstack->head = NULL;
}
int StackIsEmpty(Stack* pstack){
    if(pstack->head == NULL)
        return TRUE;
    else
        return FALSE;
}
void StackPush(Stack* pstack, NodeData data){
    StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));
    
    newNode->data = data;
    newNode->next = pstack->head;
    
    pstack->head = newNode;
}
NodeData StackPop(Stack* pstack){
    NodeData popdata;
    StackNode* popnode;
    if(StackIsEmpty(pstack)){
        printf("스택이 텅 빔");
        exit(-1);
    }
    
    popdata = pstack->head->data;
    popnode = pstack->head;
    
    pstack->head = pstack->head->next;
    free(popnode);
    return popdata;
}
NodeData StackPeek(Stack* pstack){
    StackNode* popnode;
    if(StackIsEmpty(pstack)){
        printf("스택이 텅 빔");
        exit(-1);
    }
    return pstack->head->data;
}
cs


5. 수식트리 헤더파일

#include <stdio.h>
#include <stdlib.h>
#include "ExpressionTree.h"
int main(void){
    char exp[] = "12+7*";
    Node* expTree = createExpTree(exp);
    
    printf("prefix : ");
    ShowPrefixExp(expTree);
    printf("\n");
    
    printf("infix : ");
    ShowInfixExp(expTree);
    printf("\n");
    
    printf("postfix : ");
    ShowPostfixExp(expTree);
    printf("\n");
    
    printf("result : %d\n", EvaluateExpTree(expTree));
    
    return 0;
}
cs

6. 수식트리 실행파일
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "BinaryTree.h"
#include "Stack.h"
Node* createExpTree(char exp[]){
    Stack stack;
    Node* pnode;
    
    int expLen = strlen(exp);
    int i;
    StackInit(&stack);
    
    for(i=0; i<expLen; i++){
        
        pnode = createNode();
        
        if(isdigit(exp[i])){
            setData(pnode, exp[i] - '0');
        }
        else{
            makeRightSub(pnode, StackPop(&stack));
            makeLeftSub(pnode, StackPop(&stack));
            setData(pnode, exp[i]);
        }
        
        StackPush(&stack, pnode);
        
        
    }
    return StackPop(&stack);
}
int EvaluateExpTree(Node* bt){
    int op1, op2;
    
    if(getLeftSub(bt) == NULL && getRightSub(bt) == NULL)
        return getData(bt);
    
    op1 = EvaluateExpTree(getLeftSub(bt));
    op2 = EvaluateExpTree(getRightSub(bt));
    if(op2 == 0){
        switch(getData(bt)){
        case '+':
            return op1 + op2;
        case '-':
            return op1 - op2;
        case '*':
            return op1 * op2;
        case '/':
            printf("ERROR - divide by 0\n");
            exit(-1);
        }
    }
    else{
        switch(getData(bt)){
            case '+':
                return op1 + op2;
            case '-':
                return op1 - op2;
            case '*':
                return op1 * op2;
            case '/':
                return op1 / op2;
        }
    }
    
    return 0;
}
void ShowNodeData(int data){
    if(0<=data && data<=9)
        printf("%d ", data);
    else
        printf("%c ", data);
}
void ShowPrefixExp(Node* bt){
    PreorderTraverse(bt, ShowNodeData);
}
void ShowInfixExp(Node* bt){
    InorderTraverse(bt, ShowNodeData);
}
void ShowPostfixExp(Node* bt){
    PostorderTraverse(bt, ShowNodeData);
}
cs


7. 수식트리 메인함수 있는 파일
//postfix calculator using Binary Tree
#include <stdio.h>
#include <stdlib.h>
#include "ExpressionTree.h"
int main(void){
    char exp[] = "12+7*";
    Node* expTree = createExpTree(exp);
    
    printf("prefix : ");
    ShowPrefixExp(expTree);
    printf("\n");
    
    printf("infix : ");
    ShowInfixExp(expTree);
    printf("\n");
    
    printf("postfix : ");
    ShowPostfixExp(expTree);
    printf("\n");
    
    printf("result : %d\n", EvaluateExpTree(expTree));
    
    return 0;
}
cs





참고
윤성우.(2012).열혈 자료구조.오렌지미디어

-
라벨:

댓글 없음:

댓글 쓰기

피드 구독하기: 댓글 (Atom)

DL/코세라 딥러닝 3.이진 분류기(Binary Classifier)를 만들기 위해서는?

이 글은 코세라 Andrew Ng 교수의 deep learning AI 강의를 듣고 기억하기 좋게 정리한 것입니다. 목표는 제 부모님도 이해하시도록 쉽게 쓰는 것입니다.

  • DL/ Vectorization(벡터화) - 쓰는 중
    Vectorization(벡터화)란 무엇인가? 벡터화란 어떤 수들, 혹은 행렬을 열벡터로 바꾸어주는 것을 말한다. 선형 변환의 일종이다. 가령 어떤 2x2 행렬 A를 벡터화해서 다음과 같이 행렬 vec(A)를 만들 수 있다.
  • 자구/알고리즘(algorithm)이란? - 쓰는중
    1. 개요 지난번에 아버지와 같이 카페에 갔는데 아버지께서 "알고리즘이 대체 정확히 뭐냐?"라고 물어보셨다. 간단히 대답하긴 했는데, 아무래도 좀 더 자세한 답변을 원하셨던 것 같아서 이 참에 정리해본다. 알고리즘의 정의는 어떻게...
  • DL/코세라 딥러닝 3.이진 분류기(Binary Classifier)를 만들기 위해서는?
    이 글은 코세라 Andrew Ng 교수의 deep learning AI 강의를 듣고 기억하기 좋게 정리한 것입니다. 목표는 제 부모님도 이해하시도록 쉽게 쓰는 것입니다.