이진 트리 순회

불과 반년전만 해도 이름만 들었지 마냥 먼곳에 있다고 생각했던 자료구조들이다.
근데 공부하면서 깨닫는 것은 뭐를 알아야 준비를 하고 공부도 하고
재밌게 문제도 풀 수 있다는 것이다. 그것이 바로 코딩테스트 😱
DFS니 BFS니 하려면
일단 스택, 큐, 배열, 재귀에 대해서 알아야된다고 생각했다.
물론 그리고 지금 포스팅하는 이 이진 트리에 대해서도 좀 짚고 넘어가야 한다고 봤다.

이진트리란?

이진트리는 각각의 노드가 아래 자식 노드를 최대 두개를 가진 트리 자료 구조이다.

위 이미지는 위키백과 에서 가져와봤다.
깊이(depth)는 3이고 크기는 9인 이진트리이다.

     1
  2     3
4  5   6  7

이런식으로 구성된 트리가 있을 때 전위 표기식으로 순서를 나타내는 알고리즘을 구성해보자

코드

public class Main {
    private static class Node {
        private int value;

        private Node left;
        private Node right;

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

    private static void dfs(Node n) {
        if (n == null) {
            return;
        }

        System.out.print(n.value + " ");
        dfs(n.left);
        dfs(n.right);
    }

}

자기 자신의 노드 그리고 left, right의 자식 노드를 알고있어서 재귀로 다음 노드를 호출하며

null인 경우에는 바로 return을 해주어 바로 다음 로직으로 이동하게끔 구현이 되었다.

전위 순회로 출력하게 되면 1 2 4 5 3 6 7 순서로 나오게 된다.

자료구조

자료 구조의 사전적인 의미는,
효율적인 접근 및 수정을 가능케하는 자료의 조직, 관리, 저장을 의미한다.
그래서 이 자료구조는,
데이터들의 값 모임, 데이터간 관계 들을 의미한다.
이 사전적 의미를 보니까 알고리즘과 뗄래야 뗄 수가 없는거 같다.
결국 이 선택에 따라 효율적으로 알고리즘을 설계를 할 수 있으니까 말이다.

들어가며

이 자료구조들은 당연히 여러 가지가 있으며, 각각의 자료구조는 각자의 연산과 목적에 맞춰져 있다.

단순히 알고리즘 문제들만 풀 때 자료구조를 선택한다? 답은 NO

어떠한 기능을 설계함에 있어 자료구조를 선택하는 것은 필수일 것이다.
자꾸 예를 알고리즘으로 들어서 그렇지만, 이만큼 알고리즘과 뗄래야 뗄 수가 없다는것.
자료구조가 명확해지면, 그에 따라오는 알고리즘이 반드시 필요한게 있을 거라고 본다.

종류

자료의 특성, 크기, 사용법, 연산에 따라 여러가지 종류가 있다.
크게 단순 구조, 선형 구조, 비선형 구조, 파일 구조로 나눌 수 있다.

단순 구조

• True/False, 정수, 실수, 문자 및 문자열과 같이 컴퓨터가 기본적으로 제공하는 자료형

선형 구조

• Array(배열)
  • 가장 일반적인 구조
  • 메모리 상에 같은 타입의 자료가 연속적으로 저장
  • 자료값을 나타내는 가장 작은 단위
• LinkedList
  • 노드를 하나의 단위로 한다.
  • 노드는 자료와 다음 노드를 가리키는 참조값으로 구성
  • 점 조직 같은 느낌
• Stack
  • 후입선출(Last-In-First-Out)
  • 먼저 저장된 것이 마지막에 나오게 되는구조
  • 자료의 나열 순서를 바꾸고 싶다면 스택에 넣었다가 꺼내면 역순으로 변경된다.
• Queue
  • 선입선출(First-In-First-Out)
  • 먼저 저장된 것이 먼저 나오게 되는 구조
• Deque
  • 양쪽에서 넣기 빼기를 할 수 있는 구조

비 선형 구조

• Graph
  • 꼭짓점과 꼭짓점을 잇는 변으로 구성된다.
• Tree
  • 뿌리와 뿌리 또는 다른 꼭짓점을 하나의 부모로 갖는 꼭짓점들로 이루어진 구조
  • 부모와 자식의 관계는 변으로 표현

파일 구조

하드디스크 같은 보조 기억장치에 저장되는 파일에 대한 자료구조
메모리에 한번에 로드할 수 없는 대용량의 자료
파일 구성 방식에 따라 순차, 색인, 직접으로 나뉘게 된다.