×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 2,791,955명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
반응형

헤더 파일에 선언 할 ADT


< BTreeheader.h >


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
BTreeNode *MakeBTreeNode(void); // 노드의 생성
 
// 노드를 생성 할 시 , left와 right를 NULL로 초기화해 주고 data는 이후의 함수를 통해 설정해준다.
 
BTData GetData(BTreeNode *bt) // 노드에 저장된 데이터를 반환
 
void SetData(BTreeNode *bt, BTData data); // 노드에 데이터를 저장
 
BTreeNode *GetLeftSubTree(BTreeNode *bt); // 왼쪽 서브 트리의 주소 값 반환
 
BTreeNode *GetRightSubTree(BTreeNode *bt); // 오른쪽 서브 트리의 주소 값 반환
 
 
void MakeLeftSubTree(BTreeNode *main, BTreeNode *sub); // main의 서브 왼쪽 서브 트리로 sub를 연결한다.
 
void MakeRightSubTree(BTreeNode *main, BTreeNode *sub); // main의 오른쪽 서브 트리로 sub를 연결한다.
Crocus

1) 노드에 직접 접근하는 것보다 함수를 통한 접근이 좋은 코드이다.


2) 그리고 서브 트리라 함은 실제로는 노드의 주소 값을 반환하지만 트리를 크게 보면


   이 노드의 자식 노드들이 붙어있는 것들이 있기에 서브 트리의 주소 값을 반환 한다고 한다.


3) main이 루트 노드를 의미하는 그럿것이 아닌 인자로 넘어오는 것을 main이라고 칭할 뿐이다.


   하나의 노드도 일종의 이진 트리이다. 이 함수명을 노드로만 생각하지 않고 트리로 ADT를 해준다면 좋은 함수명이 될 것이다.



ADT 함수의 구체화


< BTreefunc.c >


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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;
}
// 위의 메모리 누수는 순회를 통해 삭제를 할 수 있게된다.
Crocus


이 코드에서 생각 해 볼 부분은 

if(main->left != NULL)

  free(main->right); 부분이다.


자식 노드가 많이 달려있으면 달려있을 수록, 메모리 누수가 커지는 코드이다.


그림으로 표현하면 다음과 같다.



따라서 이 부분에 대한 코드는 이진 트리를 어떻게 만드느냐에 따라 달리 설정해 주면 되는데, 그 방법중 하나가 이진 트리의 순회를 통한 제거법이다.

이 부분에 대해서는 순회 게시물에서 작성하겠다. 


< BTreeMain.c >


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int main(void)
{
 BTreeNode *bt1 = MakeBTreeNode(); // 노드 bt1 생성
 BTreeNode *bt2 = MakeBTreeNode(); // 노드 bt2 생성
 
 
 BTreeNode *bt3 = MakeBTreeNode(); // 노드 bt3 생성
 BTreeNode *bt4 = MakeBTreeNode(); // 노드 bt4 생성
 
 SetData(bt1, 1); // bt1노드 data 부분에 1 저장
 SetData(bt2, 2);
 SetData(bt3, 3);
 SetData(bt4, 4);
 
 MakeLeftSubTree(bt1,bt2); // 노드 bt1의 왼쪽 자식 노드로 노드 bt2 연결
 MakeRightSubTree(bt1, bt 3); // 노드 bt1의 오른쪽 자식 노드로 노드 bt3 연결
 MakeLeftSubTree(bt2, bt4);
 
 // bt1 왼쪽 자식 노드 데이터 출력 코드
 printf("%d \n", GetData(GetLeftSubTree(bt1)));
 
 // bt1 왼쪽 자식의 왼쪽 자식 노드 데이터 출력 코드
 printf("%d \n", GetData(GetLeftSubTree(GetLeftSubTree(bt1))));
 
 return 0;
}
Crocus


이 코드에 의해 2,4가 출력됨을 알 수 있다.

반응형