14. 그래프 - 트리(Tree), 이진 탐색 트리(BST), 트리 순회(Tree Traversal)

트리

개념

• 정의: 데이터를 계층적인 구조로 표현할 때 사용하는 자료구조

 

용어

• 루트 노드(root node): 부모가 없는 최상위 노드
• 단말 노드(leaf node): 자식이 없는 노드
• 크기(size): 트리의 모든 노드 개수(N)
  • 기본적으로 트리 크기가 N이면 간선은 N-1개
• 깊이(depth): 루트 노드로부터 거리
• 높이(height): 깊이 중 최댓값
• 차수(degree): 각 노드의 자식 (간선) 개수

 

 

이진 탐색 트리(Binary Search Tree)

개념

• 정의: 이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조
• 특징: 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

 

탐색 진행 흐름

• 시간복잡도: O(logN)
  • 단, 트리 높이가 균등할때만 그럼
• 방법 
  • if target 값이면 탐색 종료
  • else if target 값보다 작으면 왼쪽 부분 탐방
  • else if target 값보다 크면 오른쪽 부분 탐방

 

트리의 순회(Tree Traversal)

개념

• 정의: 트리의 모든 노드를 한 번씩 방문하는 방법
• 종류
  • 전위 순회(pre-order traverse): 부모 노드먼저 방문 ( 방문 -> 왼쪽 -> 오른쪽 )
  • 중위 순회(in-oreder traverse) 왼쪽 자식 방문 후 부모 방문 (왼쪽 -> 방문 -> 오른쪽)
  • 후위 순회(post-order traverse): 오른쪽 자식 방문 후 부모 방문 (왼쪽 -> 오른쪽 -> 방문)
   

 

코드

class Node {
    String data;
    Node leftNode;
    Node rightNode;

    public Node(String data, Node leftNode, Node rightNode) {
        this.data = data;
        this.leftNode = leftNode;
        this.rightNode = rightNode;
    }
}

public class TreeTraversal {
    private static HashMap<String, Node> tree = new HashMap<>();

    public static void preOrder(Node node) {
        System.out.print(node.data + " ");
        if (node.leftNode != null) {
            preOrder(node.leftNode);
        }
        if (node.rightNode != null) {
            preOrder(node.rightNode);
        }
    }

    public static void inOrder(Node node) {
        if (node.leftNode != null) {
            inOrder(node.leftNode);
        }
        System.out.print(node.data + " ");
        if (node.rightNode != null) {
            inOrder(node.rightNode);
        }
    }

    public static void postOrder(Node node) {
        if (node.leftNode != null) {
            postOrder(node.leftNode);
        }
        if (node.rightNode != null) {
            postOrder(node.rightNode);
        }
        System.out.print(node.data + " ");
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine());
        
        for (int i = 0; i < n; i++) {
            String[] inputs = scanner.nextLine().split(" ");
            String data = inputs[0];
            Node leftNode = inputs[1].equals("None") ? null : tree.get(inputs[1]);
            Node rightNode = inputs[2].equals("None") ? null : tree.get(inputs[2]);
            tree.put(data, new Node(data, leftNode, rightNode));
        }

        preOrder(tree.get("A"));
        System.out.println();
        inOrder(tree.get("A"));
        System.out.println();
        postOrder(tree.get("A"));
    }
}