이진트리

이진 트리 순회

불과 반년전만 해도 이름만 들었지 마냥 먼곳에 있다고 생각했던 자료구조들이다.
근데 공부하면서 깨닫는 것은 뭐를 알아야 준비를 하고 공부도 하고
재밌게 문제도 풀 수 있다는 것이다. 그것이 바로 코딩테스트 😱
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 순서로 나오게 된다.