[DS] 트리 순회 (DFS)

janeljs·2021년 4월 26일
0

자료구조

목록 보기
1/2
post-thumbnail

재귀로 DFS 구현

루트 노드에서 시작하여 노드에 자식이 있다면 자식 순서대로 recursiveDFS 메서드를 호출한다.

    private static void recursiveDFS(Node node) {
        if (node instanceof TextNode) {
            System.out.print(node);
        }
        for (Node child: node.childNodes()) {
            recursiveDFS(child);
        }
    }

반복문으로 DFS 구현

  1. root 노드를 스택에 push한다.
  2. 스택에서 꺼낸 노드가 TextNode이면 출력하고, 자식 노드들을 ArrayList에 담고 역순으로 정렬한다.
  3. ArrayList에 담긴 자식노드들을 스택에 push한다.
  4. 스택이 빌 때까지 2번과 3번을 반복한다.
  private static void iterativeDFS(Node root) {
        Deque<Node> stack = new ArrayDeque<Node>();
        stack.push(root);

        while (!stack.isEmpty()) {
            Node node = stack.pop();
            if (node instanceof TextNode) {
                System.out.print(node);
            }

            List<Node> nodes = new ArrayList<Node>(node.childNodes());
            Collections.reverse(nodes);

            for (Node child: nodes) {
                stack.push(child);
            }
        }
    }

참고

Deque vs. List

링크드 리스트의 인터페이스를 어떻게 선언하는지에 따라 사용할 수 있는 메서드의 종류가 달라진다.

  • Deque
  • List

Iterable

  • Iterable<T> 인터페이스를 구현하면 enhanced for문을 사용할 수 있다.

Iterator

  • 컬렉션에 저장된 요소를 접근하는데 사용되는 인터페이스
  • enumeration과 달리 iterator는 순회 동안 element를 제거할 수 있다.

Source

  • Think Data Structures Chapter 6-7
profile
알고리즘 풀이는 👉 janeljs.github.io 👈에 올려요💓

0개의 댓글