5주차 과제: BinaryTree 실습

 

꽤 오래 걸렸다. 구현하는데, 다른 분들의 코드를 보아도 잘 이해가 되지 않아서 많이 애먹었던 것 같다..

 

과제 (Optional)

int 값을 가지고 있는 이진 트리를 나타내는 Node 라는 클래스를 정의하세요.
int value, Node left, right를 가지고 있어야 합니다.

BinrayTree라는 클래스를 정의, 
주어진 노드를 기준으로 출력하는 bfs(Node node)와 dfs(Node node) 메소드를 구현하세요.
* DFS는 왼쪽, 루트, 오른쪽 순으로 순회하세요.

 

실습한 코드 보러가기

doyoung0205/live-study

 

 

 

Node 클래스

public class Node {

    private final int value;
    private Node left;
    private Node right;

}

 

위의 클래스를 바탕으로 기능을 입혔다.​

왼쪽 자식 노드의 값은 자기 자신의 값보다 작아야 하는 것과 같은 제약 사항이나 Node 를 가지고 BinaryTree 를 구현 할 때, 필요한 Node 의 메소드 들을 작성.

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

    public int getValue() {
        return value;
    }

    public Node getLeft() {
        return left;
    }

    public Node getRight() {
        return right;
    }

    public void setLeft(int value) throws IllegalAccessException {
        if (value >= this.value) {
            throw new IllegalAccessException("왼쪽 자식 노드의 값은 부모 노드의 값보다 작다.");
        }
        this.left = new Node(value);
    }

    public void setLeft(Node node) throws IllegalAccessException {
        if (node.getValue() >= this.value) {
            throw new IllegalAccessException("왼쪽 자식 노드의 값은 부모 노드의 값보다 작다.");
        }
        this.left = node;
    }

    public void setRight(int value) throws IllegalAccessException {
        if (value <= this.value) {
            throw new IllegalAccessException("오른쪽 자식 노드의 값은 부모 노드의 값보다 크다.");
        }
        this.right = new Node(value);
    }

    public void setRight(Node node) throws IllegalAccessException {
        if (node.value <= this.value) {
            throw new IllegalAccessException("오른쪽 자식 노드의 값은 부모 노드의 값보다 크다.");
        }
        this.right = node;
    }


    public boolean isEmptyLeft() {
        return this.left == null;
    }

    public boolean isEmptyRight() {
        return this.right == null;
    }

    public boolean isRightByNode(final Node node) {
        if (this.right == null || node == null) {
            return false;
        }
        return this.right.equals(node);
    }

    public void rightClear() {
        this.right = null;
    }

    public boolean isLeftByNode(final Node node) {
        if (this.left == null || node == null) {
            return false;
        }
        return this.left.equals(node);
    }

    public void leftClear() {
        this.left = null;
    }

    public boolean isEmptyChildAll() {
        return this.left == null && this.right == null;
    }

 

BinrayTree

기본적으로 뿌리 노드인 root 로 부터 자식 노드들을 추가하고 삭제하는 기능을 가지고 있는 클래스 이다.

어려운 점은, root 로 부터 시작해서 자식을 추가해야 하기 때문에, 추가할 자리를 찾거나 삭제하고나서 어떻게 해야 할 것인가? 이 부분이 좀 어려웠다.

노드를 추가하는 예시

 

해당 값을 가진 노드를 추가하는 메소드

// 자식 노드를 추가하는 메소드
    public void insertNode(final int value) throws IllegalAccessException {

        if (checkRootNode(value)) return;

        // 자식을 추가하는 노드
        Node nodeToAdd = root;

        // 순회 하면서 자식을 추가하는 노드 찾아서
        // 값이 크면 우측, 작으면 좌측 에 추가
        while (true) {

            final int nodeToAddValue = nodeToAdd.getValue();

            //  노드 내 중복된 값은 존재할 수 없다.
            if (nodeToAddValue == value) {
                System.out.println("노드 내 중복된 값이 존재하여 삽입할 수 없습니다.");
                return;
            }

            if (nodeToAddValue > value) {
                //값이 작아 좌측으로 빠지는 경우
                if (nodeToAdd.isEmptyLeft()) {
                    nodeToAdd.setLeft(value);
                    return;
                }

                // 자식을 추가 하는 노드 왼쪽 자식 노드로 이동
                nodeToAdd = nodeToAdd.getLeft();


            } else /* (nodeToAddValue < value) */ {
                //값이 커 우측으로 빠지는 경우
                if (nodeToAdd.isEmptyRight()) {
                    nodeToAdd.setRight(value);
                    return;
                }

                // 자식을 추가 하는 노드 오른쪽 자식 노드로 이동
                nodeToAdd = nodeToAdd.getRight();

            }

        }

    }

 

해당 값을 가진 노드를 삭제하는 메소드

public void deleteNode(final int value) throws IllegalAccessException {

        if (root == null) {
            System.out.println("이진트리가 존재하지 않습니다.");
            return;
        }

        // 삭제할 노드
        Node nodeToRemove = root;
        // 삭제할 노드의 부모 노드
        Node parentNodeToRemove;

        // 삭제할 노드 찾기
        // 노드 순회 시작
        do {

            parentNodeToRemove = nodeToRemove;

            if (nodeToRemove.getValue() > value) {
                // 값이 작아 좌측으로 빠지는 경우
                if (nodeToRemove.getLeft() == null) {
                    System.out.println("삭제할 값이 존재하지 않습니다.");
                    return;
                }

                nodeToRemove = nodeToRemove.getLeft();

            } else if (nodeToRemove.getValue() < value) {
                // 값이 커 우측으로 빠지는 경우
                if (nodeToRemove.getRight() == null) {
                    System.out.println("삭제할 값이 존재하지 않습니다.");
                    return;
                }

                nodeToRemove = nodeToRemove.getRight();
            }

            if (nodeToRemove.getValue() == value) {
                break;
            }

        } while (nodeToRemove.getValue() != value);


        // 삭제할 노드의 자식이 없는 경우
        if (nodeToRemove.isEmptyChildAll()) {
            // 삭제할 노드가 root 인 경우
            if (nodeToRemove.equals(root)) {
                root = null;
            }
            // 삭제할 노드의 부모 노드의 오른쪽 자식과 삭제할 노드가 같을 떄
            else if (parentNodeToRemove.isRightByNode(nodeToRemove)) {
                parentNodeToRemove.rightClear();
            }
            // 삭제할 노드의 부모 노드의 왼쪽 자식과 삭제할 노드가 같을 떄
            else if (parentNodeToRemove.isLeftByNode(nodeToRemove)) {
                parentNodeToRemove.leftClear();
            }
            // 위 두 경우의 수가 아닐 때
            else {
                throw new IllegalAccessException("삭제할 노드의 부모 노드의 자식과 삭제할 노드가 " +
                        "일치하는 노드가 없음");
            }

        }
        // 왼쪽 노드 자식만 존재하는 경우
        else if (nodeToRemove.isEmptyLeft()) {

            if (nodeToRemove.equals(root)) {
                root = nodeToRemove.getLeft();
            } else if (parentNodeToRemove.isRightByNode(nodeToRemove)) {
                /*
                 * 삭제 대상의 왼쪽 자식 노드를 삭제 대상 위치에 둔다.
                 */
                parentNodeToRemove.setRight(nodeToRemove.getLeft());
            } else {
                parentNodeToRemove.setLeft(nodeToRemove.getLeft());
            }

        }
        // 오른쪽 노드 자식만 존재하는 경우
        else if (nodeToRemove.isEmptyRight()) {

            if (nodeToRemove.equals(root)) {
                root = nodeToRemove.getRight();
            } else if (parentNodeToRemove.isRightByNode(nodeToRemove)) {
                /*
                 * 삭제 대상의 오른쪽 자식 노드를 삭제 대상 위치에 둔다.
                 */
                parentNodeToRemove.setRight(nodeToRemove.getRight());
            } else {
                parentNodeToRemove.setLeft(nodeToRemove.getRight());
            }
        }
        /*
         * 두 개의 자식 노드가 존재하는 경우
         * 1. 삭제할 노드의 왼쪽 서브 트리에 있는 가장 큰 값 노드를 올리거나
         * 2. 오른쪽 서브 트리에 있는 가장 작은 값 노드를 올리면 된다.
         * 구현 코드는 2번째 방법을 사용한다.
         */
        else {

            // 삭제 대상 노드의 자식 노드 중에서 대체될 노드 (nodeToReplace) 를 찾는다.
            Node parentNodeToReplace = nodeToRemove;

            // 삭제 대상의 오른쪽 서브 트리 탐색 지정
            Node nodeToReplace = nodeToRemove.getRight();

            while (!nodeToReplace.isEmptyLeft()) {
                parentNodeToReplace = nodeToReplace;
                nodeToReplace = nodeToReplace.getLeft();
            }

            if (!nodeToRemove.isRightByNode(nodeToReplace)) {

                // 가장 작은 값을 선택하기 때문에 대체 노드의 왼쪽 자식은 빈 노드가 된다.
                parentNodeToReplace.setLeft(nodeToReplace.getRight());

                // 대체할 노드의 오른쪽 자식 노드를 삭제할 노드의 오른쪽으로 지정한다.
                nodeToReplace.setRight(nodeToRemove.getRight());
            }

            // 삭제할 노드가 루트 노드인 경우 대체할 노드로 바꾼다.
            if (nodeToRemove.equals(root)) {
                root = nodeToReplace;
            } else if (parentNodeToRemove.isRightByNode(nodeToRemove)) {
                parentNodeToRemove.setRight(nodeToReplace);
            } else {
                parentNodeToRemove.setLeft(nodeToReplace);
            }

            // 삭제 대상 노드의 왼쪽 자식을 잇는다.
            nodeToReplace.setLeft(nodeToRemove.getLeft());

        }
    }

 

두 개의 자식이 가진 노드를 삭제하는 경우는 이해하기 어려워서 직접 종이를 찢어서 이해 해보았다.

 

T29노드를 삭제하는 영상

 

Test

Junit5 과 샘플데이터를 만들어 테스틑 해보았다.

 @Test
    @DisplayName("이진트리에 제대로 들어 갔을 경우")
    void insertNode() throws IllegalAccessException {

        // given
        final Node root = sampleBinaryTree().getRoot();

        assertAll(() -> {
            assertEquals(root.getLeft().getValue(), 10);
            assertEquals(root.getLeft().getLeft().getValue(), 4);
            assertEquals(root.getLeft().getLeft().getLeft().getValue(), 3);
            assertEquals(root.getRight().getValue(), 29);
            assertEquals(root.getRight().getLeft().getValue(), 28);
            assertEquals(root.getRight().getLeft().getLeft().getValue(), 27);
            assertEquals(root.getRight().getRight().getValue(), 40);
            assertEquals(root.getRight().getRight().getLeft().getValue(), 33);
            assertEquals(root.getRight().getRight().getRight().getValue(), 50);
            assertEquals(root.getRight().getRight().getLeft().getRight().getValue(), 35);
        });

    }


    @Test
    @DisplayName("이진트리에 값을 삭제 하는 경우")
    void deleteNode() throws IllegalAccessException {
        // given
        final Node root = sampleBinaryTree().getRoot();

        // when
        assertEquals(root.getRight().getValue(), 29);
        BinaryTreeTest.binaryTree.deleteNode(29);

        // then

        assertAll(() -> {
            assertEquals(root.getRight().getValue(), 33);
            assertNotEquals(root.getRight().getValue(), 29);
        });
    }

 

 

---

 

BFS (너비우선탐색)

출처:  https://blog.naver.com/swoh1227/222175350122

 

Queue의 FIFO 를 이용해서 현재 노드를 확인하면서 자식 노드들을 뒤의 순서로 저장을 반복해서 탐색하는 방식이다.

    //BFS 구현
    public boolean bfs(int value) {

        //BFS 는 Queue 를 이용한다.

        final Queue<Node> queue = new LinkedList<>();
        //root 를 Queue 에 넣고 시작
        queue.add(root);

        final StringBuilder log = new StringBuilder();

        while (true) {

            Node currentNode = queue.poll();

            if (currentNode == null) {
                System.out.println("찾으려는 값이 없습니다.");
                return false;
            }

            BFSLogging(queue, currentNode);

            if (checkNodeFromBFS(value, currentNode, log)) {
                return true;
            }

            insertNodeFromBFS(queue, currentNode);
        }

    }

    /**
     * 검사한 노드의 자식이 있으면 Queue 에 저장한다.
     */
    private void insertNodeFromBFS(Queue<Node> queue, Node tempNode) {
        /* 좌측을 조사하지 않았다면 왼쪽 자식 노드 추가 **/
        final Node leftNode = tempNode.getLeft();

        //노드가 null 이면 queue 에 넣지 않는다.
        if (leftNode != null) {
            queue.add(leftNode);
        }

        final Node rightNode = tempNode.getRight();

        //노드가 null 이면 queue 에 넣지 않는다.
        if (rightNode != null) {
            queue.add(rightNode);
        }
    }

    private boolean checkNodeFromBFS(int value, Node tempNode, StringBuilder log) {
        if (tempNode.getValue() == value) {
            System.out.println("찾은 값 :: " + tempNode.getValue());
            System.out.println(log.toString());
            return true;
        } else {
            log.append(tempNode.getValue()).append("  →  ");
        }
        return false;
    }

    private void BFSLogging(Queue<Node> queue, Node tempNode) {
        System.out.print("tempNode :: " + tempNode.getValue() + "    |   ");

        System.out.print("queue :: ");
        queue.forEach(node -> {
            System.out.print(node.getValue() + ", ");
        });
        System.out.println();
    }

 

DFS (깊이 우선 탐색)

출처: https://blog.naver.com/swoh1227/222175350122

 

Stack의 LIFO와 HashMap 을 이용해서 구현했다.

자식이 없을 때 까지, 자식 노드로 이동하고 다시 자식이 있는 부모 노드로 올라오면서 다시 자식이 있는 노드로 내려가는 방식이다.

/**
* DFS(깊이탐색) 구현
*/
public boolean dfs(int value) {

    //DFS 스택구현
    final Stack<Node> stack = new Stack<>();

    //Root 로 부터 시작
    stack.push(root);
    System.out.print(root.getValue() + "  →   ");

    //해당노드를 방문했는지 여부(왼쪽, 오른쪽 모두 체크했을때 해당 맵에 데이터 PUT)
    Map<Node, Integer> checkMap = new HashMap<>();

    //탐색시작
    while (true) {
    	//스택이 비었을 경우 모든 데이터 탐색 완료.
	    if (stack.isEmpty()) {
        	System.out.print(" 찾으려는 데이터가 없습니다.");
            break;
        }

        Node currentNode = stack.peek();

        //LEFT 값이 결과 값이면 break;
        if ((currentNode.getLeft() != null && currentNode.getLeft().getValue() == value)) {
        	System.out.print(currentNode.getLeft().getValue());
            return true;
        }

        //RIGHT 값이 결과 값이면 break;
        if ((currentNode.getRight() != null && currentNode.getRight().getValue() == value)) {
          System.out.print(currentNode.getRight().getValue());
          return true;
        }

        // LEFT 가 존재하면서 LEFT 에 방문한적이 없으면 PUSH
        if (currentNode.getLeft() != null && !checkMap.containsKey(currentNode.getLeft())) {
          System.out.print(currentNode.getLeft().getValue() + "  →   ");
          stack.push(currentNode.getLeft());
          continue;
        }

        //RIGHT 가 존재하면서 RIGHT 에 방문한적이 없으면 PUSH
        if (currentNode.getRight() != null && !checkMap.containsKey(currentNode.getRight())) {
    	    System.out.print(currentNode.getRight().getValue() + "  →   ");
	        stack.push(currentNode.getRight());
        	continue;
        }


            //양쪽에 모두 존재하지 않을 경우 스택에서 POP, 체크
            checkMap.put(currentNode, 1);
            stack.pop();
        }

        return false;
    }

 

 

 

출처: blog.naver.com/swoh1227/222175350122