[자료구조 & 알고리즘] 6. 트리, 이진 트리, 트리 순회, BFS, DFS

트리, 이진 트리, 트리 순회, BFS, DFS

1. 트리 (Tree)

• 서로 연결된 Node의 계층형 자료구조로써, Root와 부모-자식 관계의 Subtree로 구성.

• 관련 용어 정리

     - 노드 (Node) : 트리를 구성하는 기본 원소

     - 간선 (Edge) : 노드 간에 연결된 선

     - 루프 노드 (Root) : 트리는 항상 루트에서 시작. 가장 위에 있는 노드.

     - 리프 노드 (Leaf) : 더 이상 뻗어나갈 수 없는 마지막 노드

     - 자식 노드 (Child), 부모 노드 (Parent), 형제 노드 (Sibling)

     - 차수 (Degree) : 각 노드가 갖는 자식의 수. 모든 노드의 차수가 n개 이하인 트리를 n진 트리라고 함.

     - 조상 (Ancestor) : 위쪽으로 간선을 따라가며 만나는 모든 노드

     - 자손 (Descendant) : 아래쪽으로 간선을 따라가며 만나는 모든 노드

     - 레벨 (Level) : 루트 노드에서 떨어진 거리.

     - 높이 (Height) : 루트 노드에서 가장 멀리 있는 리프 노드까지의 거리. 즉, 리프 노드 중에 최대 레벨 값.

     - 서브트리 (Subtree) : 트리의 어떤 노드를 루트로 하고, 그 자손으로 구성된 트리.

 

2. 이진 트리 (Binary Tree)

• 모든 노드의 최대 차수가 2개 이하인 트리

• 완전 이진 트리 (Complete Binary Tree)

     - 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 이진 트리

     - 노드에는 값, 왼쪽 자식 노드 주소, 오른쪽 자식 노드 주소가 들어감.

public class Node<T> {
    private T value;
    private Node<T> leftChild;
    private Node<T> rightChild;

    public Node(T value) {
        this.value = value;
    }

    public T getValue() {
        return value;
    }

    public void setValue(T value) {
        this.value = value;
    }

    public Node<T> getLeftChild() {
        return leftChild;
    }

    public void setLeftChild(Node<T> leftChild) {
        this.leftChild = leftChild;
    }

    public Node<T> getRightChild() {
        return rightChild;
    }

    public void setRightChild(Node<T> rightChild) {
        this.rightChild = rightChild;
    }
}

private Node<String> makeCompleteBinaryTree() {
    Node<String> root = new Node<>("A");
    root.setLeftChild(new Node<>("B"));
    root.setRightChild(new Node<>("C"));
    root.getLeftChild().setLeftChild(new Node<>("D"));
    root.getLeftChild().setRightChild(new Node<>("E"));
    root.getRightChild().setLeftChild(new Node<>("F"));
    return root;
}

 

3. 트리 순회 (Tree Traversal)

• Tree Search(트리 탐색)이라고도 불리며 트리의 모든 노드를 방문하는 과정을 말함.

• 탐색 순서에 따라 크게 너비 우선 탐색과 깊이 우선 탐색으로 나뉨.

 

4. 너비 우선 탐색 (BFS, Breadth First Search)

• 0 레벨 노드 전부 탐색 -> 1 레벨 노드 전부 탐색 -> 2 레벨 노드 전부 탐색... 이런 순서대로 같은 레벨의 노드를 우선으로 탐색

• Queue를 통해 구현

     - 탐색해야 할 노드의 대기줄 역할

     - 각 노드를 순회를 순회하면서 자식 노드의 존재 여부 확인 후 대기열인 Queue에 넣음.

private void bfs(Node<String> binaryTree) {
    Queue<Node<String>> nodeQueue = new LinkedList<>();
    nodeQueue.add(binaryTree);
    while(!nodeQueue.isEmpty()) {
        Node<String> currentNode = nodeQueue.poll();
        System.out.println(currentNode.getValue());
        if(currentNode.getLeftChild() != null) nodeQueue.add(currentNode.getLeftChild());
        if(currentNode.getRightChild() != null) nodeQueue.add(currentNode.getRightChild());
    }
}

     - Queue에 A 노드 저장 (Queue : {A}) -> Queue에서 A 노드 꺼내며 방문 (Queue : {}) -> A 노드의 자식 노드인 B, C 노드 Queue에 저장 (Queue : {B, C}) -> B 노드 꺼내며 방문 (Queue : {C}) -> B 노드의 자식 노드인 D, E 노드 Queue에 저장 (Queue : {C, D, E}) -> ...

• 낮은 레벨의 노드부터 차례대로 순회하여 레벨 순서 순회(Level Order Traversal)이라고도 함.

 

5. 깊이 우선 탐색 (DFS, Depth First Search)

• 시작 노드에서부터 하나의 방향으로 마지막 노드까지 탐색한 후 분기점으로 돌아와 다시 다른 방향으로 마지막 노드까지 탐색하고... 를 반복하는 방법

• 스택을 통한 구현과 재귀를 통한 구현이 있음.

     - 재귀가 직관적이고 구현이 쉬워 재귀를 보통 사용함.

• 트리는 여러 개의 서브 트리로 구성된다는 것을 이용하여 재귀를 구현함.

     - 한 루트 노드가 가진 자식 노드들을 모두 접근하는 함수를 만들고 이를 재귀 함수로 만들면, 그 자식 노드가 다시 루트 노드가 되어 자식 노드를 방문하고, 그 자식 노드가 다시 루트 노드가 되어 자식 노드를 방문하고...를 반복하며 깊게 깊게 들어가여 모든 노드를 순회함.

private void dfs(Node<String> binaryTree) {
    if(binaryTree == null) return;
    dfs(binaryTree.getLeftChild());
    dfs(binaryTree.getRightChild());
}

     - A -> B -> D -> B -> E -> B -> A -> C -> F -> C -> A 순서로 진행.

 

• 노드에 관한 동작 수행을 언제 하냐에 따라 전위, 중위, 후위 순회로 나뉨.

     - 전위 순회 (Preorder Traversal)

          - 자식 노드에 접근하기 전에 동작 실행.

          - 동작 결과 : A -> B -> D -> E -> C -> F

private void preorder(Node<String> binaryTree) {
    if(binaryTree == null) return;
    System.out.println(binaryTree.getValue());
    preorder(binaryTree.getLeftChild());
    preorder(binaryTree.getRightChild());
}

 

     - 중위 순회 (Inorder Traversal)

          - 한 자식 노드에 접근 후 동작 실행, 그 후 남은 한 자식 노드에 접근.

          - 동작 결과 : D -> B -> E -> A -> F -> C

private void inorder(Node<String> binaryTree) {
    if(binaryTree == null) return;
    preorder(binaryTree.getLeftChild());
    System.out.println(binaryTree.getValue());
    preorder(binaryTree.getRightChild());
}

 

     - 후위 순회 (Postorder Traversal)

          - 자식 노드에 모두 접근한 후 동작 실행.

          - 동작 결과 : D -> E -> B -> F -> C -> A

private void postorder(Node<String> binaryTree) {
    if(binaryTree == null) return;
    preorder(binaryTree.getLeftChild());
    preorder(binaryTree.getRightChild());
    System.out.println(binaryTree.getValue());
}