백기선님과 유튜브에서 온라인으로 진행하는 온라인 스터디 공부 내용입니다. 이번 글은 (5주 차. 클래스)에 관한 스터디의 Optional 과제인 이진트리를 정리한 내용입니다.
과제 (Optional)
-
int 값을 가지고 있으면서 이진트리를 나타내는 Node 클래스를 정의하세요.
-
in value, Node left, Node right를 가지고 있어야 합니다.
-
BinaryTree라는 클래스를 정의하고 주어진 노드를 기준으로 출력하는 bfs(Node node), dfs(Node node) 메서드를 구현하세요.
-
DFS는 왼쪽 -> 루트 -> 오른쪽으로 순회한다.
Contents
-
이진트리란 무엇인가?
-
과제 구현
이진트리의 정의
부모 노드 밑에 자식 노드를 최대 2개로 제한하는 트리 구조의 간단한 형태이다. 두 자식 노드를 보통 왼쪽 자식과 오른쪽 자식으로 구분 지으며, 하나의 값과 왼쪽, 오른쪽 자식 노드를 각각 가리킬 두 개의 포인터(참조값)를 가진 구조로 구현할 수 있다.
이진트리의 종류
-
전 이진트리 (Full Binary Tree)
: Leaf 노드 (맨 마지막 노드)를 제외한 모든 노드가 자식 노드를 0개 혹은 2개만 가지고 있는 트리 구조 완전 이진트리
-
완전 이진트리 (Complete Binary Tree)
: 트리의 마지막 레벨을 제외하고 모든 트리가 채워져 있는 상태, 단 마지막 레벨은 채워지지 않아도 되지만 왼쪽에서 오른쪽 순서대로 채워져야 한다. 다시 말해서 마지막 노드는 왼쪽만 채워져 있거나 전부 채워진 상태여야 한다.
-
포화 이진 트리 (Perfect Binary Tree)
: 전 이진트리이며서 완전 이진트리인 경우
이진트리 순회 방법
부모 자식 관계를 가지고 있는 트리 노드는 아래 그림과 같이 Root, Left, Right로 나누어진다. Root, Left, Right를 어떤 순서로 탐색하느냐에 따라서 순회 방법이 나누어지게 된다. 순회 방법은 4가지로 나눌 수 있다.
예제 이진트리를 보면서 각 순회가 어떻게 이루어지는지 살펴보도록 하자.
1) 전회 순회 (Preorder Traversal)
: 노드 기준으로 Root -> Left -> Right 순서로 탐색하는 방법 (Root를 먼저 방문하는 게 특징)
0 > 1 > 3 > 7 > 8 > 4 >9 > 10 > 2 > 5 > 11
2) 중위 순회 (Inorder Traversal)
: 노드 기준으로 Left -> Root -> Right 순서로 탐색하는 방법
7 > 3 > 8 > 1 > 9 > 4 > 10 > 0 > 11 > 5 > 2 > 6
3) 후위 순회 (Postorder Traversal)
: 노드 기준으로 Left -> Right -> Root 순서로 탐색하는 방법
7 > 8 > 3 > 9 > 10 > 4 > 1 > 11 > 5 > 6 > 2 > 0
4) 층별 순회 (Level Traversal)
: 맨 위에 노드부터 층별로 차례대로 방문하면서 탐색하는 방법
0 > 1 > 2 > 3 > 4 > 5 > 6 > 7 > 8 > 9 > 10 > 11
과제 풀이
1) int 값을 가지고 있으면서 이진트리를 나타내는 Node 클래스를 만드세요.
: Node 클래스는 노드를 구성하는 데 필요한 value, left, right을 가지고 있다.
2) Node 클래스에는 int value, Node left, Node right 멤버를 가지고 있어야 한다.
// Node 클래스
public class Node {
private int value;
private Node left;
private Node right;
public void setValue(int value) {
this.value = value;
}
public void setLeft(Node left) {
this.left = left;
}
public void setRight(Node right) {
this.right = right;
}
// 노드 내부에 존재하는 값을 가져오기 위한 메소드
public int getValue() {
return value;
}
}
3) BinaryTree 클래스를 정의하고 주어진 노드를 출력하는 dfs(Node node), bfs(Node node) 메서드를 구현하세요.
(단, dfs 탐색은 왼쪽 -> 루트 -> 오른쪽 순서대로 순회한다.)
BinaryTree 클래스를 정의한다.
public class BinaryTree {
private Node root;
// 루트 노드를 지정
public void setRoot(Node root) {
this.root = root;
}
public Node getRoot() {
return root;
}
// 노드 생성
public Node makeNode(Node left, int value, Node right) {
Node node = new Node();
node.setValue(value);
node.setLeft(left);
node.setRight(right);
return node;
}
}
dfs (Node node) 메서드를 구현한다. dfs 탐색 조건인 왼쪽 -> 루트 -> 오른쪽인 것을 보면 inorder 순회와 같다는 사실을 알 수 있다. 결국 해당 문제는 inorder 순회를 구현하라는 의미와 동일한다. inorder 순회 구현 방법은 스택, 재귀 등 여러 가지가 있지만 이 중에서 재귀를 통해 구현을 해보도록 하겠다.
dfs(Node node) 메서드를 구현한다.
public class BinaryTree {
......
// dfs 최종 결과
ArrayList<Integer> values = new ArrayList<>();
// in-order: left -> root -> right) -> 재귀
public void dfs(Node node) {
if (node != null) {
dfs(node.left);
values.add(node.value);
dfs(node.right);
}
}
// dfs 최종 결과 제공 메서드
public List<Integer> getDfsValues() {
return values;
}
}
그다음은 bfs(Node node) 메서드를 구현해 보자. 넓이 우선 탐색은 여러 순회 방법 중에 level traversal라 할 수 있다. bfs는 구현방법이 여러가지가 있겠지만 Queue 저장 공간을 이용하여 구현하였다.
public class BinaryTree {
// level-order -> QUEUE 방식
public List<Integer> bfs(Node node) {
// 노드 시작이 null 로 입력되는 경우는 빈 배열로 처리
if (node == null) return new ArrayList<>();
Queue<Node> stack = new LinkedList<>();
List<Integer> result = new ArrayList<>(); // 최종 결과
Node startNode = node;
stack.add(startNode);
while (!stack.isEmpty()) {
Node currentNode = stack.poll();
result.add(currentNode.value);
if (currentNode.left != null) {
stack.add(currentNode.left);
}
if (currentNode.right != null) {
stack.add(currentNode.right);
}
}
return result;
}
}
테스트 코드 작성한다.
class BinaryTreeTest {
private static BinaryTree bt;
private static Node n1;
private static Node n2;
private static Node n3;
private static Node n4;
private static Node n5;
private static List<Integer> expectedDfsValues = Arrays.asList(4, 2, 5, 1, 3);
private static List<Integer> expectedBfsValues = Arrays.asList(1, 2, 3, 4, 5);
@BeforeAll
static void init() {
bt = new BinaryTree();
n4 = bt.makeNode(null, 4, null);
n5 = bt.makeNode(null, 5, null);
n2 = bt.makeNode(n4, 2, n5);
n3 = bt.makeNode(null, 3, null);
n1 = bt.makeNode(n2, 1, n3);
bt.setRoot(n1);
}
@Test
@DisplayName("이진 트리의 인스턴스 생성 확인")
void binary_tree_instance_create() {
assertNotNull(bt);
assertNotNull(n1);
assertNotNull(n2);
assertNotNull(n3);
assertNotNull(n4);
assertNotNull(n5);
}
@Test
@DisplayName("이진 트리 생성된 값 확인")
void create_value_check() {
assertEquals(1, n1.getValue());
assertEquals(2, n2.getValue());
assertEquals(3, n3.getValue());
assertEquals(4, n4.getValue());
assertEquals(5, n5.getValue());
}
@Test
@DisplayName("DFS 값 확인")
void dfs_values_check() {
// 예상 값: 4,2,5,1,3
bt.dfs(bt.getRoot());
List<Integer> values = bt.getDfsValues();
for (int i = 0; i < values.size(); i++) {
assertEquals(values.get(i), expectedDfsValues.get(i));
}
}
@Test
@DisplayName("BFS 값 확인")
void bfs_values_check() {
// 예상 값: 1, 2, 3, 4, 5
List<Integer> values = bt.bfs(bt.getRoot());
for (int i = 0; i < values.size(); i++) {
assertEquals(values.get(i), expectedBfsValues.get(i));
}
}
@Test
@DisplayName("탐색 시작 값이 null 인 경우")
void null_node_check() {
assertNotNull(bt.bfs(null));
bt.dfs(null);
assertNotNull(bt.getDfsValues());
}
}
References
'Programming > Algorithm' 카테고리의 다른 글
| [Codility] CountDiv (0) | 2021.11.03 |
|---|
최근댓글