08-1. 트리의 개요

비선형 자료구조

트리(Tree)의 접근

트리는 계층적 관계를 표현하는 자료구조이다

트리가 표현할 수 있는 것들

가지를 늘려가며 뻗어나간다

[의사 결정 트리]

트리 관련 용어의 소개

노드 : node
트리의 구성요소에 해당하는 A, B, C, D, E와 같은 요소
간선 : edge
노드와 노드를 연결하는 연결선
루트 노드 : root node
트리 구조에서 최상위에 존재하는 A와 같은 노드
단말 노드 : terminal node
아래로 또 다른 노드가 연결되어 있지 않은 C, D, E, F와 같은 노드
내부 노드 : internal node
단말 노드를 제외한 노드로 A, B와 같은 노드

단말 노드는 잎사귀 노드(leaf node) 라고도 불리며,
내부 노드는 단말 노드가 아니라고 하여 비단말 노드(noninternal node) 라고도 불린다

노드 A는 노드 B, C, D의 부모 노드(parent node)이다
노드 B, C, D는 노드 A의 자식 노드(child node)이다
노드 B, C, D는 부모가 같으므로, 서로가 서로에게 형제 노드(sibling node)이다

조상노드(Ancestor node)
특정 노드의 위에 위치하는 모든 노드
후손 노드(Descendent node)
특정 노드의 아래에 위치하는 모든 노드

이진 트리와 서브 트리

서브트리
큰 트리에 속하는 작은 트리

이진 트리(binary tree)

- 루트 노드를 중심으로 두 개의 서브트리로 나뉘어진다
- 나뉘어진 두 서브 트리도 모두 이진트리이다

Ex)

공집합(empty node)노드는 이진트리의 판단에 있어서 노드로 인정한다

포화 이진 트리(Full Binary Tree)와 완전 이진 트리(Complete Binary Tree)

레벨 : 층별로 숫자를 매긴 것
높이 : 트리의 최고 레벨

포화 이진 트리 : 모든 레벨이 꽉 차있어서 노드를 더 추가하려면 레벨을 높여야 한다

완전 이진 트리 : 포화 이진 트리처럼 모든 레벨이 꽉 차있는 것은 아니지만, 빈 틈 없이 노드가 채워진 이진 트리

위에서 아래로, 왼쪽에서 오른쪽의 순서대로 채워진다

그냥 이진 트리

08-2. 이진 트리의 구현

이진 트리의 구현 방법 : 배열 or 연결리스트

트리를 표현하기에는 연결 리스트가 더 유연하다

하지만 트리가 완성된 이후 매우 빈번한 탐색이 이루어지는 트리일 경우 배열로 구현한다. 탐색이 매우 용이하고 빠르기 때문이다

헤더파일에 정의된 구조체의 이해

 #ifndef __BINARY_TREE_H__
 #define __BINARY_TREE_H__
 
 typedef int BData;
 
 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

헤더파일에 선언된 함수들의 기능

BTreeNode * MakeBTreeNode(void); : 노드의 생성
BTData GetData(BTreeNode * bt); : 노드에 저장된 데이터를 반환
void SetData(BTreeNode * bt, BTData data); : 노드에 데이터를 저장
BTreeNode * GetLeftSubTree(BTreeNode * bt); : 왼쪽 서브 트리 주소 값 반환
BTreeNode * GetRightSubTree(BTreeNode * bt); : 오른쪽 서브 트리 주소 값 반환

이진 트리 자료구조의 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);

오른쪽 서브 트리를 연결한다

이진 트리의 구현

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

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

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

08-3. 이진 트리의 순회(Traversal)

순회의 세 가지 방법

전위 순회(Preorder Traversal) : 루트 노드를 먼저
중위 순회(Inorder Traversal) : 루트 노드를 중간에
후위 순회(Postorder Traversal) : 루트 노드를 마지막에

순회의 재귀적 표현

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

void InorderTraverse(BTreeNode * bt) // 이진 트리 전체를 중위 순회하는 함수
{
    InorderTraverse(bt->left); // 1단계 왼쪽 서브 트리의 순회
    printf(“%d \n”, bt->data); // 2단계 루트 노드의 방문
    InorderTraverse(bt->right); // 3단계 오른쪽 서브 트리의 순회
}

재귀의 탈출 조건이 정의되어 있지 않다
노드의 방문이 그저 데이터의 출력이다

재귀의 탈출 조건

1단계 : 왼쪽 서브 트리의 순회 (노드N)
2단계 : 루트 노드의 방문 (노드L)
3단계 : 오른쪽 서브 트리의 순회 (공집합노드)

void InorderTraverse(BTreeNode * bt) // 이진 트리 전체를 중위 순회하는 함수
{
    if(bt == NULL) // bt가 NULL이면 재귀 탈출!
        return;

    InorderTraverse(bt->left); // 1단계 왼쪽 서브 트리의 순회
    printf(“%d \n”, bt->data); // 2단계 루트 노드의 방문
    InorderTraverse(bt->right); // 3단계 오른쪽 서브 트리의 순회
}

전위 순회

void PreorderTraverse(BTreeNode * bt)
{
    if(bt == NULL)
        return;
    
    printf(“%d \n”, bt->data); // 전위 순회이므로 루트 노드 먼저 방문
    PreorderTraverse(bt->left);
    PreorderTraverse(bt->right);
}

후위 순회

void PostorderTraverse(BTreeNode * bt) 
{
    if(bt == NULL)
        return;
   
    PostorderTraverse(bt->left);
    PostorderTraverse(bt->right);
    printf(“%d \n”, bt->data); // 후위 순회이므로 루트 노드 나중에 방문!
}

08-4. 수식 트리(Expression Tree)의 구현

루트 노드에 저장된 연산자의 연산을 하되, 두 개의 자식 노드에 저장된 두 피연산자를 대상으로 연산을 한다

중위 표기법의 수식 -> 후위 표기법의 수식 -> 수식 트리

수식 트리의 구현에 필요한 도구와 헤더파일의 정의

#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

후위 표기법

왼쪽에서 오른쪽으로 연산자가 나열된다
두 피연산자는 연산자 앞에 나열된다

수식트리를 구성하는 방법

피연산자를 만나면 무조건 스택으로 옮긴다
연산자를 만나면 스택에서 두 개의 피연산자를 꺼내어 자식 노드로 연결한다
자식 노드를 연결해서 만들어진 트리는 다시 스택으로 옮긴다

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

수식 트리의 순회

전위 순회하여 데이터를 출력한 결과 : 전위 표기법의 수식
중위 순회하여 데이터를 출력한 결과 : 중위 표기법의 수식
후위 순회하여 데이터를 출력한 결과 : 후위 표기법의 수식

void ShowPrefixTypeExp(BTreeNode * bt) // 전위 표기법의 수식으로
{
    PreorderTraverse(bt, ShowNodeData);
}

void ShowInfixTypeExp(BTreeNode * bt) // 중위 표기법의 수식으로
{
    InorderTraverse(bt, ShowNodeData);
}

void ShowPostfixTypeExp(BTreeNode * bt) // 후위 표기법의 수식으로
{
    PostorderTraverse(bt, ShowNodeData);
}

수식 트리의 계산

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

    if(GetLeftSubTree(bt) == NULL && GetRightSubTree(bt) == NULL) // 단말 노드라면
        return GetData(bt);

    op1 = GetData(GetLeftSubTree(bt)); // 첫 번째 피연산자
    op2 = GetData(GetRightSubTree(bt)); // 두 번째 피연산자

    switch(GetData(bt)) // 연산자를 확인하여 연산을 진행
    {
        case ‘+’ :
            return op1+op2;
        case ‘-‘ :
            return op1-op2;
        case ‘*’ :
            return op1*op2;
        case ‘/‘ :
            return op1/op2;
    }
    
    return 0;
}

Author And Source

이 문제에 관하여(Ch08. 트리(Tree)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@www_castlehi/Ch08.-트리Tree

우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)

Ch08. 트리(Tree)