클래스

목표 및 학습할 것

목표 : 자바의 Class에 대해 학습하세요.

클래스 정의하는 방법

클래스는 객체를 정의해 놓은 것으로, 객체를 만들기 위해 사용된다. 또한, 클래스는 class 명령어를 통해 정의할 수 있다.

class Animal {

}

객체 만드는 방법 (new 키워드 이해하기)

객체는 클래스에 의해 만들어지는 것으로 흔히 이야기하는 인스턴스를 포함합니다.

Animal animal = new Animal();

메소드 정의하는 방법

객체는 변수와 메소드를 가질 수 있는데, 메소드는 우리가 이야기하는 함수라고 할 수 있다.

메소드의 장점과 작성지침
- 반복적인 코드를 줄이고 코드의 관리가 용이하다.
- 하나의 메소드는 하나의 기능만 수행하도록 작성하자.
메소드 정의
- 메소드는 클래스 영역에만 작성할 수 있다.
```
// 예제
int sum(int a, int b) {
  return a+b;
}
```

또, 참고할 만한 관련 개념으로 메소드 오버로딩이 있다.

메소드 오버로딩이란 하나의 클래스에 같은 이름의 메소드를 여러 개 정의하는 것이다.
오버로딩의 조건
- 메소드 이름이 같아야 한다.
- 메소드 매개변수 개수나 타입이 달라야 한다.
- 매개변수가 같고, 리턴 타입이 다른경우 오버로딩이 성립되지 않는다.
예제
- 대표적으로 System.out.println() 메소드가 있다.

생성자 정의하는 방법

생성자란 인스턴스가 생성될 때마다 실행되는 인스턴스 초기 실행 메소드이다.

Card card = new Card();

생성자의 조건 및 특징

생성자의 이름은 클래스의 이름과 같다.
생성자는 리턴값이 없다.
클래스에 생성자가 없으면, 컴파일러가 디폴트 생성자를 추가한다.

this 키워드 이해하기

this는 인스턴스 자기자신을 가리키는 참조변수로, 인스턴스 변수와 지역변수를 구별하는데 쓰인다.

과제

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

binary search tree 구현

// binary search tree
class Node {
    int value;
    Node left;
    Node right;

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

class BinaryTree {
    Node root;

    BinaryTree(Node root) {
        this.root = root;
    }
}

add 함수는 value가 root에서부터 작으면 left, 크면 right쪽으로 이동하며 넣을 위치를 찾은 후에 더합니다.

    public void add(int value) {
        root = addRecursive(root, value);
    }

    private Node addRecursive(Node current, int value) {
        if (current == null) {
            return new Node(value);
        }

        if (value < current.value) {
            current.left = addRecursive(current.left, value);
        } else if (value > current.value) {
            current.right = addRecursive(current.right, value);
        } else {
            return current;
        }

        return current;
    }

find 함수는 recursive하게 구현할 수 있습니다.

    public boolean containsNode(int value) {
        return containsNodeRecursive(root, value);
    }

    private boolean containsNodeRecursive(Node current, int value) {
        if (current == null) {
            return false;
        }
        if (value == current.value) {
            return true;
        }
        return value < current.value 
            ? containsNodeRecursive(current.left, value) 
            : containsNodeRecursive(current.right, value);
    }

delete 함수는 3 케이스를 보어야 합니다.

child가 없는 경우 : node를 null로 반환
child가 1개인 경우 : node를 유일한 child로 반환
child가 2개인 경우 : node를 right child 중 가장 작은 값으로 바꾸고, 가장 작은 값의 위치를 삭제

delete 함수 전체를 보면 아래와 같습니다.

    public void delete(int value) {
        root = deleteRecursive(root, value);
    }

    private Node deleteRecursive(Node current, int value) {
        if (current == null) {
            return null;
        }
        if (value == current.value) {
            // 1. child가 없는 경우
            if (current.left == null && current.right == null) {
                return null;
            }
            // 2. child가 1개인 경우
            if (current.right == null) {
                return current.left;
            }
            if (current.left == null) {
                return current.right;
            }
            // 3. child가 2개인 경우
            int smallestValue = findSmallestValue(current.right);
            current.value = smallestValue;
            current.right = deleteRecursive(current.right, smallestValue);
            return current;
        }
        if (value < current.value) {
            current.left = deleteRecursive(current.left, value);
        } else {
            current.right = deleteRecursive(current.right, value);
        }
        return current;
    }
    private int findSmallestValue(Node root) {
        return root.left == null ? root.value : findSmallestValue(root.left);
    }

dfs (Depth-First Search)

depth-first search에는 여러 방법이 있습니다.

in-order : left -> node -> right
pre-order : node -> left -> right

post-order : left -> right -> node

 public void traverseInOrder(Node node) {
     if (node != null) {
         traverseInOrder(node.left);
         System.out.print(" " + node.value);
         traverseInOrder(node.right);
     }
 }

 public void traversePreOrder(Node node) {
     if (node != null) {
         System.out.print(" " + node.value);
         traversePreOrder(node.left);
         traversePreOrder(node.right);
     }
 }

 public void traversePostOrder(Node node) {
     if (node != null) {
         traversePostOrder(node.left);
         traversePostOrder(node.right);
         System.out.print(" " + node.value);
     }
 }

bfs (Breadth-First Search)

같은 레벨의 노드들을 방문(왼쪽 -> 오른쪽) 후 다음 레벨로 넘어가는 방식입니다.

    public void traverseLevelOrder() {
        if (root == null) {
            return;
        }

        Queue<Node> nodes = new LinkedList<>();
        nodes.add(root);

        while (!nodes.isEmpty()) {
            Node node = nodes.remove();
            System.out.print(" " + node.value);

            if (node.left != null) {
                nodes.add(node.left);
            }

            if (node.right != null) {
                nodes.add(node.right);
            }
        }
    }

출처 : https://www.baeldung.com/java-binary-tree

Share on

Twitter Facebook LinkedIn

Software Engineer

클래스