트리
트리의 개념
- 트리 (Tree) : 계층적인 구조를 가진 자료구조
- 예 : 가계도, 조직도, 컴퓨터의 디렉토리 구조 등
트리의 특징
- 노드가 N개인 트리는 항상 N - 1개의 링크(link)를 가진다.
- 트리의 루트에서 어떤 노드로 가는 경로는 유일하다.
- 임의의 두 노드간의 경로도 유일하다(같은 노드를 두 번 이상 방문하지 않는다는 조건하에).
- 일반적으로 각 노드가 데이터를 저장하는 데이터 필드와 자식 노드를 가리키는 링크 필드를 가지게하는 방법으로 프로그램에 표현한다.
트리의 용어
- 노드 (node) :
- 루트 노드 (root node) :
- 서브 트리 (sub tree) :
- 트리에서 한 노드와 그 노드의 자손들로 이루어진 트리
- 부모 노드 (parent node) :
- 부모-자식 관계에서 상위 계층의 노드
- 루트 노드를 제외한 모든 노드들은 유일한 부모 노드를 가짐
- 자식 노드 (child node) :
- 형제 노드 (sibling node) :
- 조상 노드 (ancestor node) :
- 조상-자손 관계에서 상위 계층의 노드
- 부모 노드 ~ 루트 노드까지 가는 경로에 존재하는 모든 노드
- 후손 노드 (descendant node) :
- 조상-자손 관계에서 하위 계층의 노드
- 해당 노드를 루트로 하는 서브 트리에 있는 모든 노드
- 외부 노드 (leaf node) :
- 내부 노드 (internal node) :
- 링크 (link), 간선 (edge), 가지 (branch) :
- 레벨 (level) :
- 노드의 깊이
- 루트를 1로 시작하여 내려갈수록 숫자 올라감
- 높이 (height) :
- 노드의 높이 = 해당 노드의 자식의 height 중 가장 높은 값 + 1
- 트리의 높이 = 해당 트리의 루트의 height
- 차수 (degree) :
- 노드의 차수 = 노드의 자식 수
- 트리의 차수 = 해당 트리 내 모든 노드의 차수 중 가장 높은 값
트리의 종류
이진 트리 (Binary Tree)
- 정의 :
- 모든 노드가 2개의 서브 트리를 가지고 있는 트리
- 서브 트리는 공집합이 될 수 있음
- 최대 2개의 자식 노드가 존재 가능하며 모든 노드의 차수는 2 이하임
- 왼쪽 서브 트리와 오른쪽 서브 트리는 서로 구별됨
- 성질 :
- n개의 노드를 가진 이진 트리는 (n - 1)개의 간선을 가짐
- 높이가 h인 이진 트리인 경우 최소 h개의 노드를 가지며 최대 (2^h - 1)개의 노드를 가짐
- 레벨 i에서의 노드의 최대 개수는 2^(i - 1)이 됨
- 분류 :
- 포화 이진 트리 (full binary tree) :
- 트리의 각 레벨에 노드가 꽉 차있는 이진 트리
- 높이가 h인 경우 정확히 (2^k - 1)개의 노드를 가짐
- 완전 이진 트리 (complete binary tree)
- 높이가 K일 때 레벨 1부터 (k - 1)까지 노드가 모두 채워져 있고 마지막 레벨은 노드가 왼쪽부터 채워져 있는 이진 트리
- 순회 (Traversal)
- 전위 순회 (preorder traversal) : VLR
- 루트 노드 방문
- 왼쪽 서브 트리 방문
- 오른쪽 서브 트리 방문
Preoder(x) :
if x != NULL
then print key[x]
Preoder(left[x])
Preoder(right[x])
- 중위 순회 (inorder traversal) : LVR
- 왼쪽 서브 트리 방문
- 트리 방문
- 오른쪽 서브 트리 방문
Inorder(x) :
if x != NULL
then inorder(left[x])
print key[x]
inorder(right[x])
- 후위 순회 (postorder traversal) : LRV
- 왼쪽 서브 트리 방문
- 오른쪽 서브 트리 방문
- 루트 노드 방문
Postorder(x) :
if x != NULL
then Postorder(left[x])
Postorder(right[x])
print key[x]
- 래벨 순회 (level traversal)
- 레벨 순으로 방문
- 왼쪽에서 오른쪽 순서로 방문
Levelorder(x) :
visit the root;
Q <- root;
while Q is not empty do
v <- dequeue(Q)
process v;
equeue children of v into Q;
- 응용 예 :
- Expression Tree
- Huffman Code
트리의 구현
public class BinaryTree<E> {
protected static class Node<E> {
protected E data;
protected Node<E> left;
protected Node<E> right;
public Node(E data) {
this.data = data;
this.left = null;
this.right = null;
}
public String toString() {
return data.toString();
}
}
protected Node<E> root;
public BinaryTree() {
this.root = null;
}
protected BinaryTree(Node<E> root) {
this.root = root;
}
public BinaryTree(E data, BinaryTree<E> leftTree, BinaryTree<E> rightTree) {
root = new Node<E>(data);
if (leftTree != null) {
root.left = leftTree.root;
}
else {
root.left = null;
}
if (rightTree != null) {
root.right = rightTree.root;
}
else {
root.right = null;
}
}
public BinaryTree<E> getLeftSubtree(){
if (root != null && root.left != null) {
return new BinaryTree<E>(root.left);
}
else {
return null;
}
}
public BinaryTree<E> getRightSubtree(){
if (root != null && root.right != null) {
return new BinaryTree<E>(root.right);
}
else {
return null;
}
}
}