트리(tree)

이 글은 윤성우 저 - "윤성우의 열혈 자료구조"를 공부하고 정리하여 작성하였습니다.

 

1. 트리(Tree)의 개요

1.1. 트리의 개념

• “트리는 계층적 관계를 표현하는 자료구조이다.”
• 트리의 구조와 용어
  • 노드: node
    • 트리 구성 요소에 해당하는 A, B, C, D, E, F와 같은 요소
  • 간선: edge
    • 노드와 노드를 연결하는 연결선
  • 루트 노드: root node
    • 트리 구조 최상위에 존재하는 A와 같은 노드
  • 단말 노드: terminal node or leaf node
    • 아래로 또 다른 노드가 연결되어 있지 않은 E, F, C, D와 같은 노드
  • 내부 노드: internal node
    • 단말 노드를 제외한 모든 노드로 A, B와 같은 노드

1.2. 이진 트리와 서브 트리

• 서브 트리(sub tree): 큰 트리에 속하는 작은 트리
• 이진 트리(binary tree)
  • 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어야 한다.
  • 나뉘어진 두 서브 트리도 모두 이진 트리어야 함
  • *노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면, 공집합 노드가 존재하는 것으로 간주한다.

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

• 레벨(level): 트리에서의 각 층
• 높이(height): 트리의 최고 레벨
• 포화 이진 트리(full binary tree): 모든 레벨이 꽉 찬 이진 트리
• 완전 이진 트리(complete binary tree): 모든 레벨이 꽉 찬 상태가 아니지만 빈 틈 없이 노드가 채워진 이진 트리

 

2. 이진 트리의 구현

2.1. 이진 트리 구현 방법: 배열/연결 리스트 기반

• 배열 기반의 경우, 해당 노드 번호를 매겨 배치를 함.

• 연결 리스트의 경우, 트리의 구조가 리스트의 연결 구조가 일치하여 구현과 이해가 더 좋음

2.2. 헤더파일에 정의된 구조체와 함수의 기능

• 이진 트리 자료구조 ADT

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);  
- 노드에 데이터를 저장, data로 전달된 값을 저장

BTreeNode * GetLeftSubTree(BTreeNode *bt);  
- 왼쪽 서브 트리 주소 값 반환
BTreeNode * GetRightSubTree(BTreeNode *bt);  
- 오른쪽 서브 트리 주소 값 반환

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

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

 

2.3. 이진 트리의 구현

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

• 왼쪽 혹은 오른쪽 서브트리가 존재한다면, 해당 트리를 삭제한 후 새로운 왼쪽 또는 오른쪽 서브트리를 연결
• 한 번의 free 함수 호출이 전부이기 때문에 삭제할 서브 트리가 여러 개의 노드로 이뤄질 경우 메모리 누수가 발생
• 그래서 순회의 방법이 필요함

 

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

3.1. 순회의 세 가지 방법

• 전위 순회(Preorder Traversal): 루트 → 왼쪽 → 오른쪽
• 중위 순회(Inorder Traversal): 왼쪽 → 루트 → 오른쪽
• 후위 순회(Postorder Traversal): 왼쪽 → 오른쪽 → 루트

void InorderTranverse(BTreeNode * bt)
{
	if(bt == NULL)  // bt가 NULL이면 탈출
		return;
	
	InorderTranverse(bt->left);
	printf("%d \n", bt->data);
	InorderTranverse(bt->right);


void PreorderTranverse(BTreeNode * bt)
{
	if(bt == NULL)  // bt가 NULL이면 탈출
	return;
	
	printf("%d \n", bt->data);
	PreorderTranverse(bt->left);
	PreorderTranverse(bt->left);
}

void PostorderTranverse(BTreeNode * bt)
{
	if(bt == NULL)  // bt가 NULL이면 탈출
	return;
	
	PostorderTranverse(bt->left);
	PostorderTranverse(bt->right);
	printf("%d \n", bt->data);
}

• printf를 저장하는 action 함수로만 변경하면 완성

 

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

4.1. 수식 트리의 이해와 헤더파일 정의

• 중위 표기법의 수식 → 후위 표기법의 수식 → 수식 트리

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

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

 

4.2. 후위 표기법 기반 수식 트리 구성

• 후위 표기법 수식
  1 2 + 7 *

• 연산 순서대로 왼쪽에서 오른쪽으로 연산자가 나열된다.
• 해당 연산자의 두 피연산자는 연산자 앞에 나열된다.
• 후위 표기법 수식의 앞쪽에 등장하는 피연산자와 연산자를 이용해 트리의 하단을 구성
• 이를 바탕으로 점진적으로 수식 트리의 윗부분을 구성

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

BTreeNode * MakeExpTree(char exp[])
{
	Stack stack;
	BTreeNode * pnode;
	int expLen = strlen(exp);
	int i;
	
	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 ShowNodeData(int data)
{
	if(0<=data && data <= 9)
		printf("%d ", data); 
	else
		printf("%c ", data);
}

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

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

}

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

 

4.3. 수식 트리의 계산

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

 

자료

• 윤성우의 열혈 자료구조 (윤성우 저, 2023.10)