트리는 고급 자료구조로 구분이 됩니다.
트리의 접근
트리는 계측정 관계를 표현하는 자료구조입니다. 자료구조는 근본적으로 무엇인가를 표현하는 도구입니다. 트리의 구조로 이뤄진 무엇인가를 표현하기에 적절히 정의되어 있나요. 트리를 이용해서 무엇인가를 저장하고 꺼내야 한다는 생각을 지우세요. 대신 무엇인가를 표현하는 도구라고 생각하세요. 노드는 트리의 구성요소에 해당하는 A, B, C, D, E, F,와 같은 요소입니다. 간선은 노드와 노드를 연결하는 연결선을 말합니다. 루트 노드는 트리 구조에서 최상위에 존재하는 A와 같은 노드입니다. 단말 노드는 아래로 또 다른 노드가 연결되어 있지 않은 E, F, C, D와 같은 노드입니다. 내부 노드는 단말 노드를 제외한 모든 노드로 A, B와 같은 노드입니다.
이진 트리와 서브 트리
서브 트리의 아래에는 더 작은 서브 트리가 존재합니다. 서브 트리가 무엇을 의미하는지, 그리고 트리와 서브 트리와의 관계가 어떻게 되는지 이해하였을 것입니다. 이진 트리라는 것이 자식 노드가 2 개씩 달린 트리인가요. 네 다음 두 조건을 만족해야 합니다. 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어집니다. 나뉘어진 두 서브 트리도 모두 이진 트리이어야 합니다. 이진 트리의 조건 자체가 재귀적이기 때문에 이렇게 정의합니다. 이진 트리가 ㅗ디려면, 루트 노드를 중심으로 둘로 나뉘는 두 개의 서브 트리도 이진 트리이어야 하고, 그 서브 트리의 모든 서브 트리도 이진 트리이어야 합니다. 노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면, 공집합 노드가 존재하는 것으로 간주합니다. 공집합 노드도 이진 트리의 판단에 있어서 노드로 인정합니다.
포화 이진 트리와 완전 이진 트리
트레이서는 각 층별로 숫자를 매겨서 이를 트리의 레벨이라고 하고, 트리의 최고 레벨을 가리켜 높이라 합니다. 레벨이 꽉 찬 이진 트리를 가리켜 포화 이진 트리라고 합니다. 포화 이진 트리처럼 모든 레벨이 꽉 찬 상태는 아니지만, 빈 틈 없이 노드가 채워진 이진 트리를 뜻합니다. 노드가 위에서 아래로, 그리고 왼쪽에서 오른쪽의 순서대로 채워졌습니다.
이진 트리의 구현
이진 트리의 구현 방법: 배열 기반 or 연결 리스트 기반
트리가 완성 된 이후부터는 그 트리를 대상으로 매우 빈번한 탐색이 이뤄집니다. 배열을 기반으로 이진 트리를 구현하려면 노드에 고유의 노드 번호를 부여해야 합니다. 완전 이진 트리의 구조를 갖는 힙이라는 자료구조는 배열을 기반으로 구현합니다.
헤더파일에 정의된 구조체의 이해
노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면, 공집합 노드가 존재하는 것으로 간주합니다. 공집합 노드도 이진트리를 판단하는데 있어서 노드로 인정합니다. BTreeNode는 노드의 표현결과일 뿐만 아니라 이진 트리의 표현결과도 된다는 것을 말하려는 것입니다.
헤더파일에 선언된 함수들의 기능
노드의 생성, 노드에 저장된 데이터를 반환, 노드에 데어틀 저장, 왼쪽 서브 트리, 그리고 오른쪽 서브 트리를 가리키기 위한 멤버는 NULL로 초기화됩니다. 왼쪽 서브 트리 주소 값 반환, 오른쪽 서브 트리 주소 값 반환. 이진 트리는 앞서 소개한 자료구조들과 다르네요. 예를 들어 연결 리스트의 경우, 정의된 함수를 기반으로 데이터를 저장하면 연결 리스트가 자동으로 생성 됩니다.
이진 트리 자료구조의 ADT
이진 트리 노드를 생성하여 그 주소 값을 반환합니다. 노드에 저장된 데이터를 반환합니다. 노드에 데이터를 저장합니다. data로 전달된 값을 저장합니다. 왼쪽 서브 트리의 주소 값을 반환합니다. 오른쪽 서브 트리의 주소 값을 반환합니다. 왼쪽 서브 티르를 연결합니다. 오른쪽 서브 트리르 연결합니다.
이진 트리의 구현
왼쪽 또는 오른쪽 서브 트리가 존재한다면, 해당 트리를 삭제하고 새로운 왼쪽 또는 오른쪽 서브 트리르 연결합니다. 한 번의 free 함수호출이 전부이기 때문에, 삭제할 서브 트리가 하나의 노드로 이뤄져 있다면 문제되지 않지만, 그렇지 않다면 메모리의 누수로 이어집니다. 둘 이상의 노드로 이뤄져 있는 서브 트리를 완전히 삭제하려면 서브 트리를 구성하는 모든 노드를 대상으로 free 함수를 호출해야 합니다. 즉, 모든 노드를 방문해야 하는 것 입니다. 모든 노드를 방문하는 것을 순회라고 합니다. 이진 트리의 순회는 연결 리스트의 순회와 달리 별도의 방법이 필요합니다.
#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; } |
#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; } |
이진 트리의 순회(Traversal)
순회의 세 가지 방법
전위 순위, 루트 노드를 먼저, 중위 순회, 루트 노드를 중간에, 후위 순회, 루트 노드를 마지막에.
순회의 재귀적 표현
재귀의 탈출 조건을 정의해야 합니다. 노드의 방문이 그저 데이터 출력입니다. 단말 노드도 이진 트리입니다.
#include <stdio.h> #include "BinaryTree.h" void InorderTraverse(BTreeNode * bt) { if (bt == NULL) return; InorderTraverse(bt->left); printf("%d \n", bt->data); InorderTraverse(bt->right); } 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)))); InorderTraverse(bt1);
return 0; } |
중위, 전위, 후위 순위 함수의 유일한 차이점은 루트 노드를 방문하는 문장이 삽입된 위치입니다.
노드의 방문 이유, 자유롭게 구성하기
노드의 방문목적은 데이터의 출력이 전부가 아닙니다. 방문의 목적은 상황에 따라 달라집니다. 함수의 주소 값을 매개변수 action 을 통해서 전달 받도록 변경하였습니다. 그리고 이 함수를 기반으로 노드의 방문을 다음과 같이 처리되도록 변경하였습니다. action(bt->data)
#ifndef __BINARY_TREE2_H__ #define __BINARY_TREE2_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); typedef void VisitFuncPtr(BTData data); void PreorderTravers(BTreeNode * bt, VisitFuncPtr action); void InorderTraverse(BTreeNode * bt, VisitFuncPtr action); void PostorderTraverse(BTreeNode * bt, VisitFuncPtr action); #endif
|
#include <stdio.h> #include <stdlib.h> #include "BinaryTree2.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; } 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); } |
#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); } |
수식 트리의 구현
이진 트리를 구성하는데 필요한 도구를 만들었습니다. 이 도구를 이용하여 이진 트리의 일종인 수식 트리를 만들어 보도록 하겠습니다.
수식 트리의 이해
수식 트리라고 합니다. 즉, 수식 트리는 이진 트리와 구분이 되는 별개의 것 입니다. 컴파일러는 코드를 실행이 가능한 상태로 만드는 소프트웨어입니다. 수식 트리는 중위 표기법을 사용하나요, 후위 표기법을 사용하나요. 루트 노드에 저장된 연산의 연산을 하되, 두 개의 자식 노드에 저장된 두 피연산자를 대상으로 연산을 합니다. 수식 트리를 만드는 것인가요. 수식 트리도 만들고 이를 대상으로 연산을 진행하는 함수도 만들어 보는 것이 맞나요.
수식 트리의 구현에 필요한 도구와 헤더파일의 정의
도구를 만들어 두고 활용하지 않는 것은 잘못된 것입니다. 수식 트리르 만드는 과정에서 스택을 필요로 하는데, 이것도 활용하면 됩니다.
#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 |
후위 표기법의 수식을 문자열의 형태로 입력 받으며, 이를 기반으로 수식 트리를 구성하고 그 수식 트리의 주소 값, 수식 트리의 루트 노드의 주소 값을 반환합니다.
후위 표기법의 수식을 기반으로 수식 트리 구성하기
수식 트리를 구성하기 위해서 후위 표기법의 두 가지 특징을 인지하고 있어야 합니다. 연산 순서대로 왼쪽에서 오른쪽으로 연산자가 나열됩니다. 해당 연산자의 두 피연산자는 연산자 앞에 나열됩니다. 수식 트리에서는 트리의 아래쪽에 위치한 연산자들의 연산이 먼저 진행됩니다. 때문에 후위 표기법이 수식에서 먼저 등장하는 피연산자와 연산자를 이용해서 트리의 하단을 만들고, 이를 바탕으로 점진적으로 트리의 윗부분을 구성해 나가야 합니다. 후위 표기법의 수식에서 앞쪽에 등장하는 피연산자와 연산자를 이용해서 트리의 하단을 만들고, 이를 바탕으로 점진적으로 수식 트리의 윗부분을 구성해 나갑니다.
수식 트리의 구성과정에서 피연산자는 무조건 스택으로 옮깁니다. 만들어진 수식 트리 전부를 스택으로 옮겨야 합니다. 이렇듯 트리 전체를 스택으로 옮기는 이유는 다른 연산자의 자식 노드가 되어야 하기 때문입니다. 의미적으로는 수식 트리 전부를 스택으로 옮기는 것이 되지만, 실제 코드상에서 + 연산자가 저장된 노드의 주소 값만 스택으로 옮기면 되지 않겠느낙. 자식 노드는 연결되어 있으니 말입니다. 수식트리를 구성하는 방법을 이해하였느낙. 정리하면 다음과 같습니다.
피연산자를 만나면 무조건 스택으로 옮깁니다. 연산자를 만나면 스택에서 두 개의 피연산자를 꺼내어 자식 노드로 연결합니다. 자식 노드를 연결해서 만들어진 트리는 다시 스택으로 옮깁니다. 설명한 흐름을 그대로 코드로 옮겨서 함수로 정의하면 됩니다.
#include <stdio.h> #include "ExpressionTree.h" int main(void) { char exp[] = "12+7*"; BTreeNode * eTree = MakeExpTree(exp); printf("1: "); ShowPrefixTypeExp(eTree); printf("\n"); printf("2: "); ShowInfixTypeExp(eTree); printf("\n"); printf("3: "); ShowPostfixTypeExp(eTree); printf("\n"); printf("result: %d \n", EvaluateExpTree(eTree)); return 0; } |
EvaluateExpTree 를 호출하고 있습니다.
수식 트리의 계산
수식 트리에 담겨있는 수식을 계산하는 함수를 정의하라고 하면, 단말 노드가 붙어 있는 서브 트리에서부터 계산을 해야 한다고 생각합니다. 두 개의 자식 노드에 담겨있는 두 피연산자를 확인하고, 부모 노드에 저장된 연산자를 확인하여 연산을 진행합니다. 수식 트리의 수식을 계산합니다. 재귀적으로 정의해 놓으면, 서브 트리의 서브 트리가 존재해도 문제가 없습니다. 이것이 바로 재귀의 위력 아닌가요. 그럴듯해 보이기는 하지만 자식 노드가 단만 노드인 경우에는 문제가 됩니다. 피연산자를 얻을 수 없게 됩니다. 전달된 것이, 서브 트리가 추가로 달려있지 않은 단말 노드의 주소 값이라면, 그 단만 노드에 저장된 피연산자를 반환합니다.