210812

Today I learned..

오늘 배운 내용 소스코드
Source
오늘은 자바로 간단한 이진 트리 구조를 구현해보았습니다.

트리

트리란?
연결리스트, 배열 등의 자료구조들은 선형구조(일렬로 데이터가 나열된 구조)인 반면, 트리는 이름 그대로 루트(뿌리)에서 자식노드들이 가지, 잎처럼 퍼져나아가는 구조입니다.

다양한 구조가 있는데, 그 중에서 오늘은 이진 트리 구조를 구현했습니다.(한 노드당 자식노드가 2개 이하로 있는 트리 구조)

class TreeNode {
    private TreeNode left;
    private TreeNode right;
    private Object data;

    public TreeNode(Object item) {
        left = null;
        right = null;
        this.data = item;
    }
    public void addLeftSubTree(TreeNode sub) {
        if (this.left != null) return;
        this.left = sub;
    }
    public void addRightSubTree(TreeNode sub) {
        if (this.right != null) return;
        this.right = sub;
    }
    public Object getData() {
        return this.data;
    }
    public TreeNode getLeftSubTree() {
        return this.left;
    }
    public TreeNode getRightSubTree() {
        return this.right;
    }
}

// 메인 메소드
public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);

	// 트리 연결
        node1.addLeftSubTree(node2);
        node1.addRightSubTree(node3);
        node2.addLeftSubTree(node4);
        node2.addRightSubTree(node5);
        node3.addLeftSubTree(node6);
        node3.addRightSubTree(node7);
    }

클래스로 left, right 노드 값을 저장할 수 있도록 하고, 각 노드에 하나씩 자식 노드들을 연결하여주면 완성입니다 😄

트리 순회

물론 이렇게 만든 트리를 그냥 두어선 아무런 의미도 없으니 우린 탐색을 진행할 것 입니다. 탐색은 간단하게 후위, 중위, 전위 순회 탐색이 있습니다. 루트부터 시작하여 각 탐색방법의 특징은 다음과 같습니다.

• 전위 순회 : 루트 디렉토리부터 시작하여, 왼쪽 자식노드, 오른쪽 자식노드 순으로 탐색을 진행합니다.
• 중위 순회 : 왼쪽 최말단 노드부터 시작하여 부모노드에 연결된 오른쪽 노드들을 하나씩 탐색합니다.
• 후위 순회 : 왼쪽 최말단 노드부터 오른쪽 최말단 노드들, 그 다음에 부모 노드를 하나씩 탐색합니다.

구현은 다음과 같습니다.

    /**
     * 전위 순회
     * @param node
     */
    static void preOrder(TreeNode node) {
        if (node == null) return;
        System.out.format(" %s ", node.getData());
        preOrder(node.getLeftSubTree());
        preOrder(node.getRightSubTree());
    }

    /**
     * 중위 순회
     * @param node
     */
    static void inOrder(TreeNode node) {
        if (node == null) return;
        inOrder(node.getLeftSubTree());
        System.out.format(" %s ", node.getData());
        inOrder(node.getRightSubTree());
    }

    /**
     * 후위 순회
     * @param node
     */
    static void postOrder(TreeNode node) {
        if (node == null) return;
        postOrder(node.getLeftSubTree());
        postOrder(node.getRightSubTree());
        System.out.format(" %s ", node.getData());
    }

Tomorrow I will learn..

• 이것이 코딩테스트다 그리디 알고리즘
• Vue.js 공부

Comment

• 확실히 중괄호를 코드블록으로 사용하는 언어들을 많이 쓴 사람으로써 무언가를 개발할 떄엔 파이썬 같은 개행문자가 필요한 언어보단 자바같은 딱딱(?)해보이는 언어가 더 편한 묘한 기분..
• 내일은 조금 이르게 공부를 시작해볼까 합니다..