CS - Data Structure - Tree (트리)

[ Tree ]

 

노드(Node)와 간선(Edge)로 이루어진 자료구조

 

최상위 노드를 루트(root) 노드라고 부른다.

 

 

노드는 여러 개의 자식 노드를 가질 수 있다.

 

자식 노드를 최대 2개까지 가지는 노드를 '이진 트리' (binary tree) 라고 부른다.

 

 

[ 트리 순회 방식 ]

 

 

1. 전위 순회 (pre-order)

 

    루트 -> 왼쪽 자식 -> 오른쪽 자식 순으로 방문

 

    10 -> 20 -> 40 -> 50 -> 30

 

public static void dfs(int cur) {  // cur := 현재 탐색 중인 정점의 번호

    if(cur > n) return;

    System.out.println(arr[cur]);
    dfs(cur*2);
    dfs(cur*2 + 1);
}

 

2. 중위 순회 (In-order)

 

    왼쪽 자식 -> 루트 -> 오른쪽 자식 순으로 방문

 

    40 -> 20 -> 50 -> 10 -> 30

 

public static void dfs(int cur) {  // cur := 현재 탐색 중인 정점의 번호

    if(cur > n) return;
    
    dfs(cur*2);
    System.out.println(arr[cur]);
    dfs(cur*2 + 1);
}

 

3. 후위 순회 (post-order)

 

    왼쪽 자식 -> 오른쪽 자식 -> 루트 순으로 방문

 

    40 -> 50 -> 20 -> 30 -> 10

 

public static void dfs(int cur) {  // cur := 현재 탐색 중인 정점의 번호

    if(cur > n) return;
    
    dfs(cur*2);
    dfs(cur*2 + 1);
    System.out.println(arr[cur]);
}

 

 

루트의 위치에 따라 전위, 중위, 후위로 보면 편하다.