트리
개요
- 트리의 개념과 종류를 알아본다.
기본 개념
- 트리란 노드로 이루어진 자료구조를 말한다.
- 트리는 다음과 같은 조건을 갖는다.
1. 하나의 루트 노드를 갖는다.
2. 루트 노드와 자식 노드들은 0개 이상의 자식 노드를 갖는다.
3. 사이클이 존재하지 않는다. (사이클이란 자식노드들을 통해서 자신의 노드로 돌아올 수 있는 순환 구조를 말한다.)
이진 트리
- 각 노드가 최대 두 개의 자식을 갖는 트리
이진 트리의 종류
1. 이진 탐색 트리
- 왼쪽 자식 노드의 값이 부모 노드의 값보다 작거나 같고, 부모 노드의 값은 오른쪽 자식 노드의 값보다 작은 이진 트리
- 위의 경우에는 모든 왼쪽 자식 노드의 값이 부모 노드의 값보다 작거나 같고, 부모 노드의 값은 오른쪽 자식 노드의 값보다 작기 때문에 이진 탐색 트리이다.
- 위의 경우에는 왼쪽 자식의 노드값이 부모 노드의 값보다 크기때문에 이진 탐색 트리가 아니다. (빨간색 박스 내부)
2. 완전 이진 트리
- 트리 모든 level에서 자식 노드가 2개인 이진 트리를 말한다. 단, 마지막 level은 모든 자식 노드가 2개가 아니여도 되지만, 왼쪽부터 자식노드가 할당되어 있어야 한다.
- 위의 경우는 모든 level에서 자식 노드가 2개이고, 마지막 level의 경우 왼쪽부터 채워져 있기 때문에 완전 이진 트리이다.
- 위의 경우는 마지막 level을 제외한 모든 level에서 자식 노드가 2개이지만, 마지막 level에서 왼쪽부터 채워져 있지 않기 때문에 완전 이진 트리가 아니다.
3. 전 이진 트리
- 모든 노드의 자식 노드의 개수가 0 또는 2인 이진 트리
4. 포화 이진 트리
- 전 이진 트리이면서 완전 이진 트리인 경우, 단 마지막 level의 노드의 개수는 최대가 되어야 한다.
( 포화 이진 트리의 노드 개수는 K^(2-1)
이진 트리의 순회
1. 전위 순회
- 자식 노드보다 현재 노드를 먼저 방문하는 방법
- 이 방법은 루트 노드를 가장 먼저 방문한다.
- 전위 순회의 수도 코드와 방문 순서는 다음과 같다.
void preOrderTraversal(Node node){
if( node != null ){
visit(node);
preOrderTraversal(node.left);
preOrderTraversal(node.right);
}
}
2. 중위 순회
- 왼쪽 자식 노드, 현재 노드, 오른쪽 가지 순서 노드를 방문하는 방법
- 이 방식은 가장 하위 왼쪽의 자식 노드를 먼저 방문한다. 이진 탐색 트리를 이 방식으로 순회하면 오름차순으로 방문한다.
- 중위 순회의 수도 코드와 방문 순서는 다음과 같다.
void preOrderTraversal(Node node){
if( node != null ){
preOrderTraversal(node.left);
visit(node);
preOrderTraversal(node.right);
}
}
3. 후위 순회
- 모든 자식 노드들을 먼저 방문한 뒤 마지막에 현재 노드를 방문한다.
- 루트 노드를 가장 나중에 방문하는 방식
- 후위 순회의 수도 코드와 방문 순서는 다음과 같다.
void preOrderTraversal(Node node){
if( node != null ){
preOrderTraversal(node.left);
preOrderTraversal(node.right);
visit(node);
}
}
'자료구조' 카테고리의 다른 글
| [자료 구조] 트라이(접두사 트리) (0) | 2022.02.24 |
|---|
댓글