이진 트리(Binary Tree) 개념 (2) - ADT

헤더 파일에 선언 할 ADT

< BTreeheader.h >

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를 연결한다.

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

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

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

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

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

ADT 함수의 구체화

< BTreefunc.c >

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;
}
// 위의 메모리 누수는 순회를 통해 삭제를 할 수 있게된다.

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

if(main->left != NULL)

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

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

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

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

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

< BTreeMain.c >

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

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