[자료구조] 트리(Tree)
트리는 계층적 관계를 표현하는 자료구조
[트리]
<특징>
단순히 무엇을 저장하고 꺼내는 것이 아닌 무언가를 표현하는 자료구조
<용어 정리>
노드 - 트리의 구성요소
간선 - 노드를 연결하는 연결선
루트 노드 - 트리 구조에서 최상위 노드
단말 노드 - 아래에 더 이상 노드가 없는 말단 노드
부모 노드가 같은 노드끼리는 형제 노드
<이진트리>
루트 노드를 중심으로 둘로 나누어지는 서브 트리
레벨 : 각 층 별로 숫자를 매긴 것 (루트 노드가 레벨 0)
높이 : 트리의 최고 레벨=높이
포화 이진트리 : 레벨이 꽉 찬 이진트리
완전 이진트리 : 노드가 위에서 아래로 & 왼쪽에서 오른쪽 순서대로 채워짐
특징 → 노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면 공집합 노드가 존재하는 것으로 간주
[배열 기반의 이진트리]
★부모노드를 참고할때 - idx/2 하면 됨
[연결 리스트 기반의 이진트리]
▶ 트리를 의미하는 구조체
typedef struct _bTreeNode
{
BTData data;
struct _bTreeNode * left;
struct _bTreeNode * right;
} BTreeNode;특징 - 하나의 노드도 그 자체로 이진트리가 될 수 있다
▶ ADT
필요한 기능 : 이진트리 생성, 데이터 반환, 데이터 저장, 좌/우 서브 트리의 주소 반환, 좌/우 서브트리 연결
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);
▶ 구현
- ADT의 구현
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;
}
<특징>
MakeLeft/RightSubTree -> 한 번의 free 호출이 전부이기 때문에 해당 트리 밑에 자식 노드들의 메모리 누수가 발생한다
- 좌/우 자식의 데이터를 출력하는 법
#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;
} printf("%d \n", GetData(GetLeftSubTree(bt1)));
printf("%d \n", GetData(GetLeftSubTree(GetLeftSubTree(bt1))));
-> 이런 식으로 getdata에 left 자식 노드의 주소를 준다
▶이진트리의 순회 = (트리 방문)
재귀적인 사고 능력 필요
필요한 이유 : 트리를 삭제할 때 트리를 구성하는 모든 노드를 대상으로 free 함수를 호출해야 하기 때문이다
순회의 세가지 방법
- 전위 순회 : 루트 노드 먼저 방문
- 중위 순회 : 루트 노드를 중간에 방문
- 후위 순회 : 루트 노드를 마지막에 방문
▶ 이진트리 구현
[전위 순회]
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);
}
<특징>
- action이란 특정 기능(노드의 데이터 출력, 노드 삭제 등등)을 하는 함수를 인자로 받는다!
- 재귀적 사고 능력 필요
▶수식 트리 = 이진 트리를 이용해서 수식을 표현해 놓은 것
전/중/후위 표기법이랑 동일한 포지션이라고 생각해
▶수식 트리 구성 방법
0. 중위 표기법의 수식 → 후위 표기법의 수식 → 수식 트리
1. 피연산자를 만나면 무조건 스택으로 옮긴다
2. 연산자를 만나면 스택에서 두개의 피연산자를 꺼내어 자식 노드로 연결한다
3. 자식 노드를 연결해서 만들어진 트리는 다시 스택으로 옮긴다
▶구현 ( 후위 표기법의 수식 → 수식 트리)
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);
}
<특징>
SPush(&stack, pnode); 에서 스택에 트리노드를 넣고 있음
<수식 트리의 순회>
- 전위 순회하여 수식 트리 데이터 출력 = 전위 표기법
- 중위 순회하여 수식 트리 데이터 출력 = 중위 표기법
- 후위 순회하여 수식 트리 데이터 출력 = 후위 표기법
▶수식 트리의 계산
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;
}
return 0;
}
ex) 예를 들어 이런 수식트리를 계산한다면 함수의 인자로 +, - , / 가 전달된다
