[C언어] 자료구조 - Tree 트리 구현 -2

 

저번엔 트리의 성질, 개념에 대해 알아보았고 이번에는

구현을 어떻게 할지? 그리고  어떠한 기본연산을 할지? 알아보겠다.

 

뭐 기본적으로 삽입, 삭제, 탐색이 있을건데 이게 자료구조가

선형적인 구조가 아니라서 삽입과 삭제에는 일반적으로 하는 연산이 아닌 뭔가 다른게 있다. 

 

 

---

 

 

우선 이진트리를 구현하는데에는 2가지가 있는데

1. 배열, Array

2. Linked List, 연결리스트

 

 

 

 

1. 배열, Array

 

배열로 이진트리를 구성할 때는 높이에 따라 배열의 크기가 정해지는데

즉 h의 높이를 가지고 있으면 2^h-1 크기의 배열은 있어야 노드를 다 넣을 수 있겠지?

그렇지만 트리의 넘버링(numbering)을 1부터 시작하니까

배열의 인덱스랑 트리 넘버를 맞춰주려면 0번째 인덱스는 사용하지 않는게 더 눈에 잘들어오고 좋겠다.

그니까 높이 h를 가지면 2^h의 배열의 크기를 가지게 만들어주자.

 

 

 

 단점은 2^h개의 메모리를 차지하지만,, 완전트리나 포화트리가 아니어서 일부분만 사용하는 경우 

메모리 낭비가 심하다는게 단점이다. 뭐 접근속도는 무지하게 빠르겠지만...

트리가 이상하게 생겼을 경우 메모리낭비가 심각하게 많을 수도 있다.

또한 Array로 구현할 경우 가변크기를 가지지 않으므로.. 처음부터 충분히 크게 만들어야 한다.

 

 

 

장점으로는 배열로 표현했을 때 어떤 노드를 알면 부모노드를 바로 알 수 있다.

 

아래의 원리로 구현했기 때문에 가능한 일이다.

 

1. 노드 i의 부모 노드 인덱스 i/2

2. 노드 i의 왼쪽 자식 인덱스 2*i

3. 노드 i의 오른쪽 자식 인덱스 2*i +1

 

 

2. Linked List, 연결리스트

 

 

연결리스트로 구성해서 선형 자료구조 구현과 매우 비슷한데

노드는 자신의 데이터와 2개의 포인터 변수를 가진다.

2개의 포인터는 각각 자식을 가리키는 포인터가 되겠지?

 

**우선 일방향 연결리스트이다.

 

 

 

또한 노드의 개수가 많아지더라도

이상하게 생겼더라도 이런식으로 연결되기 때문에 메모리가 배열보단 효율적으로 쓸 수 있다.

 

 

배열에 대한 삽입, 삭제, 탐색은 어떻게든 쓰일 수 있지만

링크 표현으로는 연산으로 어떻게 쓰일지가 문제다??

해보자

 

 

 

우선 3가지 필드를 가지고 있는 구조체를 만들자

 

1.데이터

2.왼쪽 자식 포인터

3. 오른쪽 자식 포인터

 

 

이런 식으로 3가지 정도를 만들어두면 가능하다. 굿굿 

일단 데이터가 문자가 될지 숫자가 될지는 알아서 정하면 된다.

 

그리고 하나의 트리를 나타내기 위한 유일한 데이터는 루트의 주소다.

그래서 우선 루트를 가리키는  포인터 변수를 선언해야한다.

 

 

이런식으로다가 선언해주고 그렇다면 이제 기본 연산들을 알아보자.

 

void init_tree() { root = NULL;}   // root = NULL값이 되어서 root를 가리키는 주소값이 사라짐
int is_empty_tree() {return root==NULL;}  // root를 가리키는 주소값이 있다면 0 없다면 1이 반환.
TNode *get_root() {return root;} // 루트노드를 가리키는 주소값을 반환한다. TNode를 가리키는 포인터

 

TNode *create_tree(TElement val, TNode* l, TNode* r)
{
TNode* n = (TNode*) malloc(sizeof(TNode));  // 메모리 할당
n->data = val;  // val 이란 데이터를 집어넣는데, TElement에 따라 자료형이 바뀜
n->left = l;  //포인터
n->right = r;  // 포인터
return n;  만들어진 함수의 주소값 반환.
}

 

 

우선 기본연산들이 더 있지만 다음 글에서 순회(traversal)을 배우고 같이 알아보자.