들어가기에 앞서

해당 글을 작성하기에 앞서 이진트리는 어떤 것인지에 대한 사전 지식이 있어야 이해할 수 있는 글입니다.

만약 이진트리가 무엇인지 모른다면 이 글을 읽고 오시기 바랍니다.

이진 트리 순회

이진 트리를 순회하는 방법에는 어디서부터 확인하느냐로 4가지로 나눌 수 있습니다.

순회 방법에 따라 사용처가 다르게 나오게 되고, 이를 학습함으로써 좀 더 본인이 사용하고자 하는 목적에 알맞은 방법으로 알고리즘을 작성할 수 있습니다.

아래 보이는 이진 트리를 통해 각각의 순회 결과에 대해 알려드리겠습니다.

아래 이진 트리는 이 곳에서 코드로 확인해 보실 수 있습니다.

전위 순회 ( Pre-order Traversal )

전위 순회는 부모 노드 -> 왼쪽 노드 -> 오른쪽 노드 순으로 재귀하며 출력하는 방법입니다.

즉 가장 왼쪽부터 라인부터 탐색하며, 가장 깊은 Level의 오른쪽 노드부터 차근차근 탐색할 수 있게 해줍니다.

public void traversePreOrder(TreeNode<Integer> node) {
    if (node != null) {
        System.out.print(" " + node.getValue());
        traversePreOrder(node.getLeft());
        traversePreOrder(node.getRight());
    }
}

결과

사용처

• DFS 탐색
• 트리 복사

중위 순회 ( In-order Traversal )

중위 순회는 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식노드 순으로 순회하는 방법입니다.

public void traverseInOrder(TreeNode<Integer> node) {
    if (node != null) {
        traverseInOrder(node.getLeft());
        System.out.print(" " + node.getValue());
        traverseInOrder(node.getRight());
    }
}

결과

사용처

• 오름차순 정렬
• 정렬된 데이터 탐색

후위 순회 ( Post-order Traversal )

후위 순회는 왼쪽 자식노드 -> 오른쪽 자식노드 -> 부모 노드 순으로 순회하는 방법입니다.

public void traversePostOrder(TreeNode node) {
    if (node != null) {
        traversePostOrder(node.getLeft());
        traversePostOrder(node.getRight());
        System.out.print(" " + node.getValue());
    }
}

결과

사용처

• 메모리 해제
• 파일 구조 삭제
• 후위 표기법을 통한 연산

레벨 순회 ( Level-order Traveral )

레벨 순회는 root 부터 각 레벨마다 순차적으로 왼쪽부터 오른쪽으로 순회하는 방법입니다.

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

    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.print(" " + node.getValue());

        if (node.getLeft() != null) queue.add(node.getLeft());
        if (node.getRight() != null) queue.add(node.getRight());
    }
}

결과

사용처

• 최단 경로 탐색
• Bfs 탐색

Reference

https://www.w3schools.com/dsa/dsa_data_binarysearchtrees.php

Stack이란?

Stack은 한쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO( Last In First Out ) 자료구조입니다.

추상자료형( abstract data type, ADT )이며, 이는 논리적인 기능을 명시해 놓은 것이라 볼 수 있고, 이는 구현체가 이를 상속받아 구현하는 방식으로 자료형은 Stack이지만 구현은 여러 방법으로 구현할 수 있음을 의미합니다.

Stack은 Vector를 상속받아 구현을 하고 있는데 이는 Vector를 구현되 LIFO방식으로 데이터를 다룰 수 있게 다루기 위해 Stack이란 자료형이 존재한다 생각해 볼 수 있습니다.

우선 기본적인 기능을 확인해 보겠습니다.

Stack은 Vector를 상속한 ADT이기 때문에 기본적으로 Object []인 elementData로 데이터를 관리하고 있습니다.

배열의 크기는  기본적으로 10의 크기로 생성하고 있으며, resizing을 통해 많은 데이터가 들어오더라도 수용할 수 있습니다. 이렇듯 대부분의 기능은 동일하지만, 외부에서 접근할 수 있는 pop메서드를 확인해 보면 elemtnData의 Size를 확인하여 맨 마지막 데이터만을 추출할 수 있도록 구현되어 있는 것을 확인할 수 있습니다.

public synchronized E pop() {
    E       obj;
    int     len = size();

    obj = peek();
    removeElementAt(len - 1);

    return obj;
}

제공하는 기능

사용처

그럼 Stack은 어떤 곳에서 사용하게 될까요??

웹브라우저 History 즉 뒤로가기 앞으로가기 와 같은 기능처럼 history를 쌓아두고 이를 최신 것부터 접근하는 상황이 있다면 이럴때는 Stack을 사용함으로써 편하게 관리할 수 있습니다.

또한 재귀함수와 같이 연산이 루프를 도는 방향의 알고리즘을 구현을 한다면,

최근 접근 한 것들을 접근 할 수 있는 Stack을 통해 쉽게 최근에 넣은 데이터를 꺼내 연산을 하면서 손쉽게 구현할 수 있습니다. 백준 코딩 테스트

References

https://docs.oracle.com/javase/7/docs/api/java/util/Stack.html