자료구조 - [Tree]이진 트리

이진 트리

1. 이진 트리의 조건

- root node를 중심으로 두 개의 sub tree로 나뉘어진다.

- 나누어진 두 sub tree도 모두 이진 트리이어야 한다.

※ 트리 그리고 이진 트리는 그 구조가 재귀적이다. 따라서 트리와 관련된 연산은 재귀적 사고와 구현을 할 필요가 있다.

2. 이진 트리와 공집합 노드

- 하나의 노드에 두 개의 노드가 달리는 형태의 트리는 모두 이진 트리이다

- 공집합(Empty set)도 이진 트리에서는 노드로 간주한다.

 -> 그러므로 형제 노드가 비어 있다고 해도 공집합으로 간주하여 이진 트리      가 성립 된다.

3. 이진 트리의 레벨과 높이

- root 노드 부터 0레벨로 시작하고, 아래로 갈수록 레벨이 증가한다.

- 레벨의 최대값과 트리의 높이는 같다.

3. 완전 트리와 포화 트리

- 완전 이진 트리는 위에서 아래로 왼쪽에서 오른쪽으로 채워진 트리를 의미한다.

- 따라서 포화 이진 트리는 동시에 완전 이진 트리이다.

- 하지만 와전 이진 트리는 포화 이진 트리가 될 수 없다.

4. 이진 트리 구현의 두 가지 방법

4_1 배열을 이용한 표현

- 노드에 번호를 부여하고 그 번호를 배열의 인덱스 값으로 활용

- 편의상 배열의 첫 번째 요소는 사용하지 않음

- 트리가 완성 된 이후부터 탐색이 자주 일어날 경우 효율적

4_2 연결리스트를 이용한 표현

- 트리의 구조와 리스트의 연결 구조가 일치한다.

- 구현과 관련된 직관적인 이해가 더 좋은 편

5. 이진 트리 구현 - 노드 구조체 정의

// 이진 트리의 노드를 표현한 구조체 typedef struct _bTreeNode { BTData data; struct _bTreeNode * left; struct _bTreeNode * right; } BTreeNode;

6. 이진 트리 구현 - 트리 기능관련 함수 정의

/ 이진 트리 노드를 생성하고, 그 주소값을 반환한다. BTreeNode * MakeBTreeNode(void) { BTreeNode * nd = (BTreeNode*)malloc(sizeof(BTreeNode)); nd->left = NULL; nd->right = NULL; return nd; } // 노드에 저장된 데이터를 반환한다. BTData GetData(BTreeNode * bt) { return bt->data; } // 노드에 데이터를 저장한다. 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; }

7. 이진 트리 구현 - 트리 동작

int main(void) { BTreeNode * bt1 = MakeBTreeNode(); //bt1 노드를 만든다. BTreeNode * bt2 = MakeBTreeNode(); //bt2 노드를 만든다. BTreeNode * bt3 = MakeBTreeNode(); //bt3 노드를 만든다. BTreeNode * bt4 = MakeBTreeNode(); //bt4 노드를 만든다. SetData(bt1, 1); // bt1 노드에 데이터 "1"을 넣는다. SetData(bt2, 2); // bt2 노드에 데이터 "2"을 넣는다. SetData(bt3, 3); // bt3 노드에 데이터 "3"을 넣는다. SetData(bt4, 4); // bt4 노드에 데이터 "4"을 넣는다. MakeLeftSubTree(bt1, bt2); // bt1노드의 왼쪽 서브트리로 bt2를 연결 시킨다. MakeRightSubTree(bt1, bt3); // bt1노드의 오른쪽 서브트리로 bt3를 연결 시킨다. MakeLeftSubTree(bt2, bt4); // bt2노드의 왼쪽 서브트리로 bt4를 연결 시킨다. printf("%d \n", GetData(GetLeftSubTree(bt1))); printf("%d \n", GetData(GetLeftSubTree(GetLeftSubTree(bt1)))); return 0; }