1. 트리의 구조
- 노드(Node) : 트리 구조의 자료 값을 담고 있는 단위
- 에지(Edge) : 노드 간의 연결선( = link, branch)
- 루트 노드(Root) : 부모가 없는 노드, 가장 위의 노드
- 잎새 노드(Leaf) : 자식이 없는 노드 (= 단말 노드)
- 내부 노드(Internal) : 잎새 노드를 제외한 모든 노드
- 부모 노드(Parent) : 연결된 두 노드 중 상위의 노드
- 자식 노드(Child) : 연결된 두 노드 중 하위의 노드
- 형제(Sibling) : 같은 부모를 가지는 노드
- 깊이(Depth) : 루트에서 어떤 노드까지의 간선의 수 ex) H 같은 경우 A(루트) -> B -> D -> H 로 총 에지(->)가 3개 있으므로 깊이는 3이다.
- 레벨(Level) : 트리의 특정 깊이를 가지는 노드 집합 ex) Level 2인 노드들은 {D, E, F, G)이다.
- 높이(Height) : 트리에서 가장 큰 레벨 값
- 크기(Size) : 자신을 포함한 자식 노드의 개수 ex) A의 크기는 (A, B, C... ,J)가 있으므 로 10이다.
- 차수(Degree) : 각 노드가 지닌 가지의 수 ex) F의 차수는 0, A의 차수는 2이다.
- 트리의 차수 : 트리의 최대 차수
2. 트리의 특징
- 하나의 노드에서 다른 노드로 이동하는 경로는 유일하다.
- 노드가 N개인 트리의 Edge의 수는 N-1개
- Cycle이 존재하지 않는 Acyclic구조이다.
- 모든 노드는 서로 연결되어 있음
- 하나의 Edge를 끊으면 2개의 Sub-Tree로 분리된다. ex) A->B를 연결하는 Edge를 끊게 되면 {A, C, F, G} 인 트리와 {B, D, E, H, I, J}인 트리 2개로 분리된다.
3. 이진 트리(Binary Tree)
- 특징
- 각 노드는 최대 2개의 자식을 가질 수 있음
- 자식 노드는 좌우를 구분함 -> 아래 두 트리는 자식 노드가 B, C로 같지만 순서가 달라서 서로 다른 트리임
- 포화 이진 트리의 높이가 h일 때, 노드의 수는 2^(h+1) - 1개
- 포화(or 완전) 이진 트리의 노드가 N개 일 때, 높이는 logN(소수점은 삭제)
- 이진 트리의 노드가 N개 일 때, 최대 가능 높이는 N
- 이진 트리 종류
- 포화 이진 트리(Perfect binary Tree) : 모든 레벨에서 노드들이 전부 채워져 있는 트리
- 완전 이진 트리(Complete binary Tree) : 마지막 레벨을 제외하고 모든 노드들이 전부 채워져 있는 트리
- 정 이진 트리(Full binary Tree) : 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리
- 편향 트리(Skewed Binary Tree) : 한쪽으로 기울어진 트리 (=사향 트리)
- 균형 이진 트리(Balanced binary Tree) : 모든 노드의 좌우 서브 트리 높이가 1이상 차이 나지 않는 트리 -> 탐색 속도가 빠름
- 이진 트리의 순회 (Traversal)
- 모든 노드를 빠뜨리거나 중복하지 않고 방문하는 연산
- 순회 종류는 4가지!
- 전위 순회, 중위 순회, 후위 순회 -> DFS
- 레벨 순회 -> BFS
- 전위 순회 (Preorder Traversal)
- 현재 노드 -> 왼쪽 노드 -> 오른쪽 노드
- 순회 경로 : A -> B -> D -> H -> I -> E -> J -> C -> F -> G
- 중위 순회 (Inorder Traversal)
- 왼쪽 노드 -> 현재 노드 -> 오른쪽 노드
- 순회 경로 : H -> D -> I -> B -> J -> E -> A -> F -> C -> G
- 후위 순회 (Postorder Traversal)
- 왼쪽 노드 -> 오른쪽 노드 -> 현재 노드
- 순회 경로 : H -> I -> D -> J -> E -> B -> F -> G -> C -> A
- 레벨 순회 (Levelorder Traversal)
- 위쪽 레벨 부터 왼쪽 노드 -> 오른쪽 노드
- 방문 순서 : A -> B -> C -> D -> E -> F -> G -> H -> I -> J
2. 트리 순회 구현
전위순회에 경우, 자기 노드를 출력하고 자식 노드가 있는지 확인 후 왼쪽 노드부터 이동하여 자식노드가 없을 때까지 현재노드 -> 왼쪽 노드 -> 오른쪽 노드 순으로 반복 출력한다. 출력할 자식 노드가 없는 경우에는 부모 노드로 이동하여 남은 노드가 있으면 출력한다.
이러한 과정을 계속 반복하기에 재귀문을 이용하여 각 순회를 구현해보았다.
// 노드의 데이터 저장하는 클래스
class Node{
char data;
Node left;
Node right;
}
// 노드를 이용해 트리를 만드는 클래스
class Tree {
public Node root;
public void setRoot(Node node) {
this.root = node;
}
public Node getRoot() {
return root;
}
public Node makeNode(char data, Node left, Node right) {
Node node = new Node();
node.data = data;
node.left = left;
node.right = right;
return node;
}
// 트리 순회
public void inOrder(Node node) {
if(node!=null){
inOrder(node.left);
System.out.print(node.data + " ");
inOrder(node.right);
}
}
public void preOrder(Node node) {
if(node!=null){
System.out.print(node.data + " ");
preOrder(node.left);
preOrder(node.right);
}
}
public void postOrder(Node node) {
if(node!=null){
postOrder(node.left);
postOrder(node.right);
System.out.print(node.data + " ");
}
}
}
public class BinaryTreeTraversal {
public static void main(String[] args) {
Tree tree = new Tree();
// 트리 노드 입력
Node H = tree.makeNode('H', null, null);
Node I = tree.makeNode('I', null, null);
Node D = tree.makeNode('D', H, I);
Node J = tree.makeNode('J', null, null);
Node E = tree.makeNode('E', J, null);
Node B = tree.makeNode('B', D, E);
Node F = tree.makeNode('F', null, null);
Node G = tree.makeNode('G', null, null);
Node C = tree.makeNode('C', F, G);
Node A = tree.makeNode('A', B, C);
//루트 노드 설정
tree.setRoot(A);
System.out.println("====== preOrder ======");
tree.preOrder(A);
System.out.println("");
System.out.println("====== inOrder ======");
tree.inOrder(A);
System.out.println("");
System.out.println("====== postOrder ======");
tree.postOrder(A);
System.out.println("");
}
}[실행 결과]
