1. 이진 트리 정의하기
이진 트리(binary tree)
- 노드가 왼쪽 자식과 오른쪽 자식을 갖는 트리
- 각 노드의 자식은 2명 이하만 유지해야 함
- 왼쪽 자식과 오른쪽 자식을 구분
- 왼쪽 서브 트리 (left subtree)
: 왼쪽 자식을 다시 루트로 하는 서브트리
- 오른쪽 서브 트리 (right subtree)
: 오른쪽 자식을 다시 루트로 하는 서브트리
2. 완전 이진 트리 정의하기
완전 이진 트리 (complete binary tree)
- 마지막 레벨을 제외한 레벨은 노드를 가득 채움
- 마지막 레벨은 왼쪽부터 오른쪽 방향을 노드를 채우되 반드시 끝까지 채울 필요는 없음
- 높이가 k인 완전 이진트리가 가질 수 있는 노드의 최댓값 2^k+1 -1
- n개의 노드를 저장할 수 있는 완전 이진 트리의 높이 log n
- 너비 우선 탐색을 하며 각 노드에 0,1,2,..값을 주면 배열에 저장하는 인덱스와 일대일로 대응
3. 이진 검색 트리 살펴보기
이진검색트리(binary Search tree)
- 어떤 노드 N을 기준으로 왼쪽 서브 트리 노드의 모든 키값은 노드 N의 키 값보다 작아야 함
- 오른쪽 서브 트리 노드의 키 값은 노드 N의 키값보다 커야 함
- 같은 키값을 갖는 노드는 없음
- 특징
1) 구조가 단순
2) 중위 순회(Inorder)하면 키값의 오름차순으로 노드를 얻을 수 있음
3) 이진 검색과 비슷한 방식으로 빠르게 검색 가능
4) 노드를 삽입하기 쉬움
4. 이진검색트리 만들기
4.1 노드를 표현하는 구조체 BinNode
- 자기 참조형 구조체 BinNode
//노드
typedef struct __bnode {
Member data; //데이터
struct __bnode *left; //왼쪽 자식 노드에 대한 포인터
struct __bnode *right; //오른쪽 자식 노드에 대한 포인터
}BinNode;
4.2 노드를 생성하는 AllocBinNode 함수
- BinNode형 객체를 만드는 함수
//노드를 동적으로 할당
static BinNode *AllocBinNode(void) {
return (BinNode*)calloc(1,sizeof(BinNode));
}
4.3 노드 멤버값을 설정하는 SetBinNode 함수
- BinNode형 객체의 3개 멤버에 값을 설정하는 함수
- n이 가리키는 BinNode형 객체에 대해 멤버값 설정
//노드 멤버값 설정
static void SetBinNode(BinNode *n, const Member *x, const BinNode *left, const BinNode *right)
{
n->data =*x; //데이터
n->left = (BinNode*) left; //왼쪽 포인터
n->right = (BinNode*)right; //오른족 포인터
}
4.4 비어 있는 상태의 이진검색트리
- 이진검색트리 프로그램에서는 초기화 함수 Initialize함수가 필요 없음
- 루트 노드를 가리키는 BinNode*형 객체를 하나 준비하고 널 값을 대입하면 됨
BinNode *root = NULL; //이진검색트리의 루트 노드 포인터
4.5 키값으로 검색하는 Search 함수
ex) 3을 검색 (검색 성공)
1) 루트(5)를 선택, 3은 5보다 작기 때문에 왼쪽으로 검색 진행
2) 2를 선택, 3은 2보다 크기 때문에 왼쪽으로 검색 진행
3) 4를 선택, 3은 4보다 작기 때문에 왼쪽으로 검색 진행 (검색 성공)
ex) 8을 검색 (검색 실패)
1) 5를 선택, 8은 5보다 크기 때문에 오른쪽으로 검색 진행
2) 7을 선택, 8은 7보다 크기 때문에 오른쪽으로 검색 진행
오른쪽에는 자식이 없어 검색 실패
<검색 알고리즘>
- 루트부터 선택하여 검색을 진행. 여기서 선택하는 노드를 p라고 함
- p가 널이면 검색에 실패
- 검색하는 값 key와 선택한 노드 p의 키값을 비교
- 값이 같으면 검색에 성공
- key가 작으면 선택한 노드에 왼쪽 자식 노드를 대입
- key가 크면 선택한 노드에 오른쪽 자식 노드를 대입
//검색
BinNode *Search (BinNode *p, const Member *x)
{
int cnod;
if (p == NULL)
return NULL; //검색 실패
else if((cnod = MemberNoCmp(x,&p->data)) == 0)
return p; //검색 성공
else if(cnod < 0)
Search(p->left, x); //왼쪽 서브 트리에서 검색
else
Search(p->right,x); //오른쪽 서브 트리에서 검색
}
4.5 노드를 삽입하는 Add 함수
- 노드를 삽입한 다음에 트리의 형태가 이진검색트리의 조건을 유지해야함
- 노드를 삽입할 때는 먼저 삽입하기에 알맞은 위치를 찾아 내야함
ex) 1을 삽입
- 삽입할 위치를 찾음
- 추가할 값인 1은 2보다 작고, 2의 왼쪽 자식 노드는 비어 있으므로 해당 위치를 삽입 위치로 선택
- 2의 왼쪽 자식 노드로 1을 삽입
<삽입 알고리즘>
- node에 루트 포인터를 대입 (루트를 선택)
- 삽입할 key와 node의 키 값을 비교. 값이 같다면 삽입에 실패 (종료)
- 값이 같지 않은 경우 key값< node값
-> 왼쪽 자식 노드가 없는 경우에 노드 삽입
-> 왼쪽 자식 노드가 있는 경우에는 선택한 노드에 왼쪽 자식 노드 포인터를 대입
- 값이 같지 않은 경우 key값 < node값
-> 오른쪽 자식 노드가 없는 경우에 노드 삽입
-> 오른쪽 자식 노드가 있는 경우에는 선택한 노드에 오른쪽 자식 노드 포인터를 대입
//노드 삽입
BinNode *Add (BinNode *p, const Member *x)
{
int cond;
if(p == NULL) {
p = AllocBinNode();
SetBinNode(p,x,NULL,NULL);
}
else if ((cond = MemberNoCmp(x, &p->data)) == 0)
printf("[오류] %d는 이미 등록되어 있습니다.\n",x->no);
else if(cond < 0)
p->left = Add(p->left,x);
else
p->right = Add(p->right,x);
return p;
}
p == NULL인 경우
- 루트 노드가 없는 상태
- 노드를 만들고 값을 설정
p != NULL인 경우
1) 선택한 노드의 키 값 = 삽입할 키 값
- 값 삽입 불가
2) 삽입할 키 값 < 선택한 노드의 키 값
- 선택한 노드에 왼쪽 자식 노드 대입
- Add 함수에 왼쪽 자식 노드를 전달하며 재귀호출
3) 삽입할 키 값 > 선택한 노드의 키 값
- 선택한 노드에 오른쪽 자식 노드 대입
- Add 함수에 오른쪽 자식 노드를 전달하며 재귀호출
4.6 노드를 삭제하는 Remove 함수
1) 자식 노드가 없는 노드를 삭제 하는 경우
- 삭제할 노드가 부모 노드의 왼쪽 자식이면 부모의 왼쪽 포인터를 NULL로 함
- 삭제할 노드가 부모 노드의 오른쪽 자식이면 부모의 오른쪽 포인터를 NULL로 함
ex) 3을 삭제
- 3을 찾아감. 삭제할 노드 3에서 멈춤
- 부모(4)의 왼쪽 포인터에 NULL을 대입
2) 자식 노드가 1개인 노드를 삭제하는 경우
- 삭제 대상 노드가 부모 노드의 왼쪽 자식인 경우
-> 부모의 왼쪽 포인터가 삭제 대상 노드의 자식을 가리키도록 함
- 삭제 대상 노드가 부모 노드의 오른쪽 자식인 경우
-> 부모의 오른쪽 포인터가 삭제 대상 노드의 자식을 가리키도록 함
ex) 7을 삭제 하는 경우
- 7을 찾아감. 삭제할 노드 7에서 멈춤
- 부모 노드인 6의 오른쪽 포인터가 7의 자식 노드인 8을 가리키도록 업데이트
( 자식 노드 8을 루트로 하는 서브 트리의 모든 키 값은 부모 노드인 6보다 커야한다는 조건 만족)
3) 자식 노드가 2개인 노드를 삭제 하는 경우
- 삭제할 노드의 왼쪽 서브 트리에서 키값이 가장 큰 노드를 검색
- 검색한 노드를 삭제한 위치로 옮김
(검색한 노드의 데이터를 삭제 대상 노드 위치로 복사)
- 옮긴 노드를 삭제 . 이때
-> 옮긴 노드에 자식이 없으면
1) 자식 노드가 없는 노드를 삭제하는 경우에 따라 노드 삭제
-> 옮긴 노드에 자식이 있으면
2) 자식 노드가 1개인 노드를 삭제하는 경우에 따라 노드 삭제
ex) 5를 삭제
- 5를 찾아감. 삭제할 노드 5에서 멈춤
- 노드 5의 왼쪽 서브 트리에서 가장 큰 키값을 갖는 노드를 검색
- 4에서 멈춤
- 5가 있는 곳으로 4를 옮기면 삭제 과정이 끝남
- 4의 데이터를 5의 위치로 복사
- 원래의 4를 트리에서 떼어내면 됨
//노드 삭제
int Remove (BinNode **root, const Member *x)
{
BinNode *next *temp;
BinNode **left;
BinNode **p = root;
while(1) {
int cond;
if(*p == NULL)
{
printf("[오류] %d는 등록되어 있지 않습니다.\n",x->no);
return -1; //이 키는 없음
}
else if((cond = MemberNoCmp(x,&(*p)->data)) == 0)
break; //검색 성공
else if (cond < 0)
p = &((*p)->left); //왼쪽 서브 트리에서 검색
else
p = &((*p)->right); //오른쪽 서브 트리에서 검색
}
if((*p)->left == NULL)
next = (*p)->right;
else {
left =&((*p)->left);
while((*left)->right != NULL)
left = &(*left)->right;
next = *left;
*left = (*left)->left;
next->left = (*p)->left;
next->right = (*p)->right;
}
temp = *p;
*p = next;
free(temp);
return 0;
}
4.7 모든 노드를 출력하는 PrintTree 함수
- 모든 노드를 키값의 오름차순으로 출력
- 중위 순회(inorder)방법으로 트리 검색
//모든 노드의 데이터를 출력
void PrintTree (const BinNode *p)
{
if(p != NULL)
{
PrintTree(p->left);
PrintMember(&p->data);
putchar('\n');
PrintTree(p->right);
}
}
4.8 모든 노드를 삭제하는 FreeTree 함수
- 모든 노드를 삭제
- 후위 순회(postorder)방법을 트리를 검색하여 삭제를 진행
//모든 노드를 삭제
void FreeTree(BinNode *p)
{
if(p != NULL ) {
FreeTree(p->left);
FreeTree(p->right);
free(p);
}
}
'C언어 > 자료구조' 카테고리의 다른 글
| 10-1 장 해시법 (2) (0) | 2023.08.06 |
|---|---|
| 10 -1 해시법 (1) (0) | 2023.08.04 |
| 9-1장 트리 (0) | 2023.08.03 |
| 8-4장 원형 이중 연결 리스트 (0) | 2023.08.03 |
| 8-3장 커서를 이용한 연결 리스트 (0) | 2023.08.03 |
