8. 트리

※ 해당 글은 C언어에 대한 이해를 필요로 합니다. C 언어에 대해 알고 싶으신 분들은 다음 글을 참고하세요

https://ward.tistory.com/category/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D%20%EC%96%B8%EC%96%B4/C

'프로그래밍 언어/C' 카테고리의 글 목록

 

(1) 트리의 개요

 

* 트리의 접근

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

이전에 배웠던 선형 자료구조들에서는 데이터의 저장, 검색 및 삭제에 초점을 맞췄지만 이후에 나오는 자료구조는 무엇을 표현하는가에 초점이 맞춰져 있다.

 

* 트리 관련 용어의 소개

기본적인 트리

• node: 트리의 구성요소에 해당하는 A, B, C, D, E, F와 같은 요소
• edge: 노드와 노드를 연결하는 연결선
• root node: 트리 구조에서 최상위에 위치하는 A와 같은 노드
• leaf node: 아래로 또 다른 노드가 연결되어 있지 않은 E, F, C, D와 같은 노드
• internal node: 단말 노드를 제외한 모든 노드로 A, B와 같은 노드
• parent: 노드 A는 노드 B, C, D의 parent 노드이다.
• child: 노드 B, C, D는 노드 A의 chlid 노드이다.
• sibling: 노드 B, C, D는 부모 노드가 같으므로, 서로가 서로에게 sibling 노드이다.
• level: 트리의 각 층별로 숫자를 매긴 것이다.
• height: 트리의 최고 레벨을 height라 한다.

* 이진 트리와 서브 트리

서브 트리: 큰 트리에 속하는 작은 트리를 서브 트리라 한다.

이진 트리: 각각의 노드가 최대 두 개의 자식 노드를 갖는 트리를 이진 트리라 한다.

* 포화 이진 트리와 완전 이진 트리

포화 이진 트리: 모든 레벨이 꽉 찬 이진 트리를 포화 이진 트리라 한다.

완전 이진 트리: 노드가 차곡차곡 빈 틈 없이 채워진 이진 트리를 완전 이진 트리라 한다.

 

(2) 이진 트리의 구현

 

* 이진 트리의 구현 방법

이진 트리는 배열을 기반으로도, 연결 리스트를 기반으로도 구현이 가능하다.

그러나 배열 기반으로는 주로 탐색이 빈번하게 일어나는 완전 이진 트리를 구현하고 대부분의 경우 연결 리스트 기반으로 구현한다.

 

* 이진 트리의 ADT 정의

Operation:

• BTreeNode* MakeBTreeNode()
  • 이진 트리 노드를 생성하여 그 주소 값을 반환한다.
• 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>

typedef int BTData;

typedef struct _bTreeNode
{
	BTData data;
	struct _bTreeNode* left;
	struct _bTreeNode* right;
} BTreeNode;

BTreeNode* MakeBTreeNode() {
	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;
}

 

(3) 이진 트리의 순회

 

* 순회의 세 가지 방법

전위 순회: C -> L -> R 

중위 순회: L -> C -> R 

후위 순회: L -> R -> C

 

* 순회의 재귀적 표현과 트리 전체의 삭제

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

void InorderTraverse(BTreeNode* bt) {
	if (bt == NULL)
		return;
	InorderTraverse(bt->left);
	printf("%d \n", bt->data);
	InorderTraverse(bt->right);
}

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

void DeleteTree(BTreeNode * bt)
{
	if(bt == NULL)
		return;
	DeleteTree(bt->left);
	DeleteTree(bt->right);
	printf("del tree data: %d \n", bt->data);
	free(bt);
}

 

(4) 수식  트리의 구현

 

* 수식 트리의 이해

수식 트리: 이진 트리를 이용해서 수식을 표현해 놓은 것이다.

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

중위 표기법의 수식을 후위 표기법으로 바꾸고 이를 수식 트리로 표현한다.

수식 트리

* 후위 표기법의 수식을 기반으로 수식 트리 구성하기

후위 표기법의 수식에서 앞쪽에 등장하는 피연산자와 연산자를 이용해서 트리의 하단을 만들고 이를 바탕으로 점진적으로 수식 트리의 윗부분을 구성해 나간다.

수식 트리를 구성하는 방법

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

* 수식 트리의 구현

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "ListBaseStack.h"
#include "BinaryTree.h"

BTreeNode* MakeExpTree(char exp[])
{
	Stack stack;
	BTreeNode* pnode;

	int expLen = strlen(exp);
    
	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);
}

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

 

참조문헌: 윤성우의 열혈 자료구조