[자료구조] 트리(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) 예를 들어 이런 수식트리를 계산한다면 함수의 인자로 +, - , / 가 전달된다