자료구조 트리
트리(TREE)
트리는 부모-자식 관계의 노드들로 이루어진다.
- 응용분야
- 계층적인 조직 표현
- 컴퓨터 디스크의 디렉토리 구조
- 인공지능에서의 결정트리(decision tree)
- 용어
- 노드(node) : 트리의 구성요소
- 루트(root) : 부모가 없는 노드
- 서브트리(subtree) : 하나의 노드와 그 노드들의 자손들로 이루어진 트리
- 단말노드(terminal node): 자식이 없는 노드
- 비단말노드 : 적어도 하나의 자식을 가지는 노드
- 레벨(level) : 트리의 각층의 번호
- 높이(height) : 트리의 최대 레벨
- 차수(degree) : 노드가 가지고 있는 자식 노드의 개수
- 종류
- 이진 트리
- 일반 트리
이진트리
- 이진 트리(binary tree) : 모든 노드가 2개의 서브 트리를 가지고 있는 트리
- 서브트리는 공집합일수 있다.
- 이진트리의 노드에는 최대 2개 까지의 자식 노드가 존재
- 모든 노드의 차수가 2 이하가 된다 -> 구현하기 편리
- 이진 트리에는 서브 트리간의 순서가 존재
이진 트리 검증
- 이진 트리는 공집합이거나
- 루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한집합으로 정의된다. 이진 트리의 서브 트리들은 모두 이진 트리어야 한다.
이진 트리의 성질
- 노드의 개수가 n개라면 간선(link)의 개수는 n-1
- 높이가 h인 이진트리의 경우, 최소 h개의 노드를 가지며 최대 2^h-1개의 노드를 가진다.
- n개의 노드를 가지는 이진트리의 높이
- 최대 n
- 최소 log2(n+1)
이진 트리의 분류
- 포화 이진트리(Full binary tree)
- 용어 그대로 트리의 각 레벨에 노드가 꽉 차있는 이진트리를 의미한다.
- 완전 이진 트리도 포함된다.
- 완전 이진 트리(Complete binary tree)
- 레벨 1부터 k-1까지는 노드가 모두 채워져 있고 마지막 레벨 k에서는 왼쪽 부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리
- 기타 이진 트리
이진트리의 표현
- 배열을 이용
- 배열표현법 : 모든 이진 트리를 포화 이진 트리라고 가정하고 각 노드에 번호를 붙여서 그 번호를 배열의 인덱스로 삼아 노드의 데이터를 배열에 저장하는 방법. 경사 이진트리처럼 밸런스가 맞지않는 이진트리를 표현하는 경우 효율적이지 못하다.
- 부모와 자식 인덱스 관계
- 노드 i의 부모 노드 인덱스 -> i/2
- 노드 i의 왼쪽 자식 노드 인덱스 -> 2*i
- 노드 i의 오른쪽 자식 노드 인덱스 -> 2*i+1 (left+1)
- 포인터를 이용
- 링크 표현법 : 포인터를 이용하여 부모노드가 자식노드를 가리키게 하는 방법
- 1개의 데이터필드와 2개의 링크필드(left, right) 필요
이진 트리의 순회
- 순회(traversal) : 트리의 노드들을 체계적으로 방문하는 것
- 3가지의 기본적인 순회방법
루트를 기준으로 이해하면 편한다. 무조건 왼쪽이 먼저이다 RL(X) LR(O)- 전위순회(VLR)
- 자손노드보다 루트노드를 먼저 방문
- 루트가 가장먼저 방문 L->R
- 중위순회(LVR)
- 왼쪽 자손, 루트 ,오른쪽 자손 순으로 방문한다.
- 루트가 중간 L->V(중간)->R
- 후위순회(LRV)
- 루트노드보다 자손을 먼저 방문한다.
- L->R 루트가 제일 마지막 V
- 전위순회(VLR)
이진탐색트리
- 탐색작업을 효율적으로 하기 위한 자료구조
- key(왼쪽서브트리)<=key(루트노드)<=key(오른쪽서브트리)
- 일반적으로 같은 중복된 key값을 허용하지는 않는다.
- 이진탐색을 중위순회하면 오름차순으로 정렬된 값을 얻을 수 있다.
이진탐색연산
- 비교한 결과가 같으면 탐색이 성공적으로 끝남
- 비교한 결과가, 주어진 키 값이 루트 노드의 키값보다 작으면 탐색으 루트 노드의 왼쪽 자식을 기준으로 다시 시작.
- 비교한 결과가, 주어진 키 값이 루트 노드의 키값보다 크면 탐색은 이 루트 노드의 오른쪽 자식을 기준으로 다시 시작.
찾아야하는 값이 루트보다 작으면 왼쪽 크면 오른쪽으로 재탐색
구현
- TREE 구조체 생성
- TREE INSERT 함수
- 전위 순회 구현
- 중위 순회 구현 (내림차순 정렬)
- 후위 순회 구현
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX(a,b) ((a)<(b)?(b):(a))
// 이진트리의 기본 구성을 위해 왼쪽,오른쪽 노드와 값을 저장하는 구조체 선언
typedef struct TreeNode
{
int value;
struct TreeNode * left;
struct TreeNode * right;
}TreeNode;
// 노드의 주소를 반환해주는 함수
// 들어온 노드가 NULL이라면 해당 노드에 값을 삽입해주고
// 그게 아니라면 루트 노트를 기준으로 왼쪽은 더 작은 값 오른쪽은 더 큰값이므로 조건에 맞게 삽입
TreeNode *insertNode(TreeNode *Node, int value){
if(Node==NULL){
TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
node->value = value;
node->left = NULL;
node->right = NULL;
return node;
}//만약에 들어온 노드가 널이라면 그냥 삽입
if(value < Node->value){
Node->left = insertNode(Node->left, value);
}
else if(value > Node->value){
Node->right = insertNode(Node->right,value);
}
return Node;
}
void preOrder(TreeNode* Root){
if(Root){ //노드가 비어있지 않다면
// 전위 순위는 루트 -> 왼 -> 오 순서
printf("[%d] ",Root->value);
preOrder(Root->left);
preOrder(Root->right);
}
}
void inOrder(TreeNode *Root){
if(Root){
// 중위 순위는 왼 -> 루트 -> 오른쪽 순서이며 중위순위를 사용하면 정렬이 된다.
inOrder(Root->left);
printf("[%d] ", Root->value);
inOrder(Root->right);
}
}
void postOrder(TreeNode *Root){
if(Root){
postOrder(Root->left);
postOrder(Root->right);
printf("[%d] ", Root->value);
}
}
int get_count_node(TreeNode *node){
int cnt = 0;
if(node){
cnt = 1+get_count_node(node->left)+get_count_node(node->right);
}
return cnt;
}
int get_height_node(TreeNode *node){
int height = 0;
if(node){
height = 1 + MAX(get_height_node(node->left), get_height_node(node->right));
}
return height;
}
int main(){
srand(time(NULL));
TreeNode *R = NULL;
int testCase = rand()%15;
for(int i=0; i<testCase; i++)
R = insertNode(R,rand()%100);
preOrder(R);
printf("\n");
inOrder(R);
printf("\n");
postOrder(R);
printf("\n");
int cnt = get_count_node(R);
int h = get_height_node(R);
printf("Node cnt is [%d]\n", cnt);
printf("Node height is [%d]\n", h);
return 0;
}