[Java] Node와 BinaryTree 구현

목차 (클릭시 해당 목차로 이동)

---

 

 

 

과제

• int 값을 가지고 있는 이진 트리를 나타내는 Node 라는 클래스를 정의하세요.
• int value, Node left, right를 가지고 있어야 합니다.
• BinrayTree라는 클래스를 정의하고 주어진 노드를 기준으로 출력하는 bfs(Node node)와 dfs(Node node) 메소드를 구현하세요.
• DFS는 왼쪽, 루트, 오른쪽 순으로 순회하세요.

 

 

 

 

 

Node.class

 

package javastudy.ch5.assignment;

public class Node {
    private int value;
    private Node left;
    private Node right;

    public Node() {
        this.left = null;
        this.right = null;
    }

    public Node(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }
}

 

 

 

BinaryTree

 

package javastudy.ch5.assignment;

import java.util.*;

public class BinaryTree {

    private Node root;
    private int size;

    public BinaryTree() {
        this.root = null;
        this.size = 0;
    }

    public int getSize() {
        return size;
    }

    public void insertNode(Node node) {

        this.size += 1;

        if (root == null) {
            root = node;
            return;
        }

        Node parentNode = root;
        Node currentNode = root;
        boolean isLeft = true;

        while (currentNode != null) {
            parentNode = currentNode;
            if (node.getValue() < currentNode.getValue()) {
                currentNode = currentNode.getLeft();
                isLeft = true;
            } else {
                currentNode = currentNode.getRight();
                isLeft = false;
            }
        }

        if (isLeft) {
            parentNode.setLeft(node);
        } else {
            parentNode.setRight(node);
        }

    }

    public List<Integer> bfs(Node node) {

        if (node == null) {
            throw new NullPointerException("node is null");
        }

        Queue<Node> queue = new LinkedList<>();
        List<Integer> result = new ArrayList<>();
        queue.add(node);

        while (queue.size() != 0) {
            Node currentNode = queue.poll();
            result.add(currentNode.getValue());

            if (currentNode.getLeft() != null) {
                queue.add(currentNode.getLeft());
            }

            if (currentNode.getRight() != null) {
                queue.add(currentNode.getRight());
            }
        }

        return result;
    }

    public List<Integer> dfs(Node node) {
        if (node == null) {
            throw new NullPointerException("node is null");
        }

        Stack<Node> stack = new Stack<>();
        stack.push(node);

        List<Integer> result = new ArrayList<>();
        dfs(node, stack, result);
        return result;
    }

    private void dfs(Node node, Stack<Node> stack, List<Integer> result) {
        Node currentNode = stack.pop();
        result.add(node.getValue());

        if (currentNode.getLeft() != null) {
            stack.push(currentNode.getLeft());
            dfs(currentNode.getLeft(), stack, result);
        }

        if (currentNode.getRight() != null) {
            stack.push(currentNode.getRight());
            dfs(currentNode.getRight(), stack, result);
        }
    }
}

 

 

 

 

Test

 

 

 

 

 

BFS (너비 우선 탐색) 순회 결과

 

루트와 가까운 것부터 탐색하므로

6 -> 3 -> 10 -> 1 -> 8 -> 2 -> 7 가 나와야 합니다.

 

 

 

DFS (깊이 우선 탐색) 순회 결과

 

루트부터 가장 깊은곳까지 탐색하므로 (과제 상에선 왼쪽노드부터)

6 -> 3 -> 1 -> 2 -> 10 -> 8 -> 7 가 나와야 합니다.

 

 

package javastudy.ch5.assignment;

import org.apache.commons.lang3.StringUtils;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import static org.junit.jupiter.api.Assertions.*;

class BinaryTreeTest {

    @Test
    public void BinaryTreeTest() throws Exception {
        //given

        BinaryTree tree = new BinaryTree();

        Node head = new Node(6);

        tree.insertNode(head);
        tree.insertNode(new Node(3));
        tree.insertNode(new Node(10));
        tree.insertNode(new Node(1));
        tree.insertNode(new Node(2));
        tree.insertNode(new Node(8));
        tree.insertNode(new Node(7));
        //when

        //then
        List<Integer> bfs = tree.bfs(head);
        List<Integer> bfsRes = Arrays.asList(6, 3, 10, 1, 8, 2, 7);

        Assertions.assertEquals(bfs, bfsRes);
        System.out.println(StringUtils.join(bfs, ", "));

        System.out.println("===");

        List<Integer> dfs = tree.dfs(head);
        List<Integer> dfsRes = Arrays.asList(6, 3, 1, 2, 10, 8, 7);
        Assertions.assertEquals(dfs, dfsRes);
        System.out.println(StringUtils.join(dfs, ", "));


    }

}