Tree

Tree의 정의

• 나무의 형태를 가지고 있는 자료구조 (정확하게 말하면 나무를 뒤집어 놓은 형태)
• 단방향 그래프, 계층적 자료구조
• 하나의 뿌리로 부터 가지가 사방으로 뻗어 나가는 형태

Tree 구조와 특징

Tree의 용어

• 노드(Node) : 트리 구조를 이루는 모든 개별의 데이터
• 부모 노드(Parent Node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에 가까운 노드
• 자식 노드(Child Node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에 먼 노드
• 루트(Root) : 트리 구조의 시작점이 되는 노드
• 형제 노드(Sibling Node) : 같은 레벨에 위치하 노드
• 리프 노드(Leaf Node) : 트리 구조의 끝 지점, 자식 노드가 없는 노드
• 간선(Edge) : 노드가 서로 연결되어 있음을 나타내는 것

Tree의 특징

• 깊이(Depth): 루트로부터 하위 계층의 특정 노드까지의 깊이
  • 루트 A의 깊이는 0, B와 C의 깊이는 1, H, I, J의 깊이는 3
• 레벨(Level) : 같은 깊이를 가지고 있는 노드들의 묶음
  • 레벨 1 : A, 레벨 2 : B, C 레벨 3 : D, E, F, G 레벨 4 : H, I, J
• 높이(Height) : 리프 노드를 기준으로 루트까지의 높이
  • 리프 노드의 높이는 0
  • 부모 노드는 자식 노드의 가장 높은 높이를 기준으로 높이를 가진다
  • 노드 C를 기준으로 F는 리프 노드로서 0의 높이를 가지고 G는 자식노드를 가지고 있어 1이라는 높이를 가진다. 이때 C의 높이는 더 높이 값이 높은 G를 기준으로 2라는 높이를 가진다.
• 서브 트리(Sub Tree) : Root를 가진 트리 내부에 트리 구조를 갖춘 작은 트리

Tree의 메서드

Tree 순회 방법

1. 전위(Pre-Order) : 부모 노드를 먼저 방문하는 순회 방식( root-left-right )
2. 중위(In-Order) : 부모 노드를 중간에 방문하는 순회 방식( left-root-right )
3. 후위(Post-Order) : 부모 노드를 가장 마지막에 방문하는 순회 방식( left-root-right )

Tree의 메서드

메서드	설명
void addleft()	현재 노드의 좌측에 노드 연결 정보 추가
void addRight()	현재 노드의 우측에 노드 연결 정보 추가
void deleteLeft()	현재 노드의 좌측에 노드 연결 정보 삭제
void deleteRight()	현재 노드의 우측에 노드 연결 정보 삭제
Node addNode(Object data)	현재 스택에 포함된 모든 데이터 삭제
Node preOrder(Node node)	전위 순회 방법으로 출력
Node inOrder(Node node)	중위 순회 방법으로 출력
Node postOrder(Node node)	후위 순회 방법으로 출력
addChildNode(value)	입력받은 value를 Tree에 계층적으로 추가
removeChildNode(node)	입력받은 node를 Tree에서 삭제
getChildrenNode()	현재 트리에서 존재하는 children을 리턴
contains(value)	트리에 포함된 데이터를 찾는다.

BST(Binary Search Tree)

이진 탐색 트리 : 자식 노드가 최대 두개인 노드들로 구성된 트리

이진 트리의 특징

• 모든 왼쪽 자신의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가진다.
• 이진 트리는 자료의 삽입, 삭제 방법에 따라 정 이진 트리, 완전 이진 트리, 포화 이진 트리로 나뉜다.
• 중복 값을 허용하지 않는다.

이진 트리의 종류

정 이진 트리(Full binary tree)

• 각 노드가 0개 혹은 2개의 자식 노드를 가진다.

완전 이진 트리(Complete binary tree)

• 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 한다.

포화 이진 트리(Perfect binary tree)

• 정 이진 트리이면서 완전 이진 트리인 경우
• 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리

이진 트리의 메서드

메서드	설명
insert(value)	입력받은 value를 Binary Search에 맞게 Tree에 계층적으로 추가할 수 있어야 합니다.
contains(value)	트리에 포함된 데이터를 찾을 수 있어야 합니다.
preorder(root, depth, list)	전위 순회를 통해 트리의 모든 요소를 정렬하여 ArrayList 타입으로 반환합니다.
inorder(root, depth, list)	중위 순회를 통해 트리의 모든 요소를 정렬하여 ArrayList 타입으로 반환합니다.
postorder(root, depth, list)	후위 순회를 통해 트리의 모든 요소를 정렬하여 ArrayList 타입으로 반환합니다.