[JAVA] Tree 이진트리 구현

이진트리란 

 

자식 노드가 최대 2개인  노드로  구성된 트리이다.

-> 이 말을 해석 해보자면 부모 노드로 부터 자식노드가 0 ~2개 사이로 존재 할 수 있다.

 

더 자세히 그림으로 살펴보자.

left(10) root(5) right(null)	left(10) root(5) right(20)	left(null) root(5) right(20)	left(null) root(5) right(null)
이진 트리가 맞음	이진 트리가 맞음	이진 트리가 맞음	이진 트리가 맞음

 이런 구조를 가질 수 있다.

 

그럼 위 그림을 통해 Node 구조를 만들어 보자.

 

1. 한개의 노드를 봤을때 Value 값이 필요함 

2. 노드에서 는 left 노드 , right 노드 포함할 수도 있고 없을 수도 있다.

 

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

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

        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;
        }

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

Node class를 정의 했다. 이제 이 Node를 이용해 이진 트리를 만들어보자.

 

 

이진트리를 만들기전에 3가지의 전제조건 부터 알아보자.

 

1. 어떤 노드 N을 기준으로 왼쪽 서브 트리 노드의 모든 키 값은 노드 N의 키 값 보다 작아야 한다.

2. 오른쪽 서브 트리 노드의 키 값은 노드 N의 키 값보다 커야 한다.

3. 같은 키의 값을 갖는 노드는 존재하지 않는다. 

 

위의 전제조건을 이용하여 Insert 코드를 만들어보자

private boolean find(int value){
        Node currentNode =root;
        while (currentNode!=null){
            if(currentNode.getValue()==value){
                return true;
            }else if(currentNode.getValue() >value) {
                currentNode = currentNode.getLeft();
            }else {
                currentNode = currentNode.getRight();
            }
        }
        return false;
    }

 public boolean insert(int value){
        Node newNode = new Node(value); //값을 받아서 새로운 newNode 생성
        if(find(value)){ //find method를 호출하여 value 가 있는지 체크 3번 전제조건 확인
            return false;
        }
        if(root == null){ // root 가 null 이면 newNode 를 root로 변경후 return
            root =newNode;
            return true;
        }
        Node currentNode = root; 
        Node parent;
        while (true){
            parent = currentNode;
            if(value<currentNode.getValue()){  //value 보다 cur.value 가 더 크면  
                currentNode = currentNode.getLeft();  //왼쪽 노드로이동  1번 전제조건 확인
                if(currentNode==null){
                    parent.setLeft(newNode);
                    return true;
                }
            }else {
                currentNode = currentNode.getRight();  // cur.value 보다  value 가 더 크면 
                if(currentNode==null){
                    parent.setRight(newNode); //오른쪽 노드로이동  2 번전제조건 확인
                    return true;
                }
            }
        }
    }

 

다음은 이진트리의 탐색 방법 4가지를 알아보자

 

1. 전위 탐색(PreOrderTraversal)  : root -> left ->right  

전위 탐색이 곧 - >깊이우선탐색(DFS) 가 됨 (stack 활용)

 private List<Integer> inOrderTraverse(Node focusNode, List<Integer> integers) {
        if (focusNode != null) {
            integers.add(focusNode.getValue());
            inOrderTraverse(focusNode.getLeft(),integers);
            inOrderTraverse(focusNode.getRight(),integers);
        }
        return integers;
    }

   

2. 중위 탐색(InOrderTraversal) : left -> root > right

중위탐색 -> 오름차순 정렬

private List<Integer> inOrderTraverse(Node focusNode, List<Integer> integers) {
        if (focusNode != null) {
            inOrderTraverse(focusNode.getLeft(),integers);
            integers.add(focusNode.getValue());
            inOrderTraverse(focusNode.getRight(),integers);
        }
        return integers;
    }

 

3. 후위 탐색(PostOrderTraversal) : left ->right ->root

 private List<Integer> postOrderTraverse(Node focusNode,List<Integer> integers) {
        if (focusNode != null) {
            postOrderTraverse(focusNode.getLeft(),integers);
            postOrderTraverse(focusNode.getRight(),integers);
            integers.add(focusNode.getValue());
        }
        return integers;
    }

 

4. 너비우선탐색(BFS)

-> Queue 를 이용

public List<Integer> BFS(Node focusNode){
        if(focusNode == null){
            return null;
        }
        List<Integer> result =  new ArrayList<>();
        Queue<Node> queue = new LinkedList<>();

        queue.add(focusNode);

        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Node poll = queue.poll();

                if(poll.getLeft() !=null){
                    queue.add(poll.getLeft());
                }
                if(poll.getRight() !=null){
                    queue.add(poll.getRight());
                }
                result.add(poll.getValue());
            }

        }
        return result;
    }

 

---

Test 코드

class BinaryTreeTest {

    BinaryTree binaryTree;

    @BeforeEach
    void beforeEach(){
        binaryTree = new BinaryTree();
        binaryTree.insert(5);
        binaryTree.insert(1);
        binaryTree.insert(2);
        binaryTree.insert(6);
        binaryTree.insert(7);
        binaryTree.insert(10);
        binaryTree.insert(9);

    }

    @Test
    @DisplayName("객체 추가")
    void insert(){
        //when
        boolean insert_20 = binaryTree.insert(20);
        boolean insert_dup_10 = binaryTree.insert(10);
        //then
        assertThat(insert_20).isTrue();
        assertThat(insert_dup_10).isFalse();
    }

    @Test
    @DisplayName("전위 순회 ,깊이우선탐색(DFS)")
    void preOrderTravers(){
        //when
        List<Integer> preOrderTraverse = binaryTree.Traverse(binaryTree.root, BinaryTree.PRE_ORDER_TRAVERSE);
        //then
        assertThat(preOrderTraverse).isEqualTo(List.of(5, 1, 2, 6, 7, 10, 9));
    }
    @Test
    @DisplayName("너비우선탐색(BFS)")
    void BFS(){
        //when
        List<Integer> preOrderTraverse = binaryTree.BFS(binaryTree.root);
        //then
        assertThat(preOrderTraverse).isEqualTo(List.of(5, 1, 6, 2, 7, 10, 9));
    }
    @Test
    @DisplayName("중위 순회")
    void inOrderTravers(){
        //when
        List<Integer> preOrderTraverse = binaryTree.Traverse(binaryTree.root, BinaryTree.IN_ORDER_TRAVERSE);
        //then
        assertThat(preOrderTraverse).isEqualTo(List.of(1, 2, 5, 6, 7, 9, 10));
    }

    @Test
    @DisplayName("후위 순회")
    void postOrderTravers(){
        //when
        List<Integer> preOrderTraverse = binaryTree.Traverse(binaryTree.root, BinaryTree.POST_ORDER_TRAVERSE);
        //then
        assertThat(preOrderTraverse).isEqualTo(List.of(2, 1, 9, 10, 7, 6, 5));
    }


}

전체소스코드 : 바로가기