자료구조) Tree, Binary Tree (트리, 이진트리)

Tree

용어 : Root, Child, Parent, Siblings, Leaf=Terminal, Branch=Internal, Degree, Height, Level
=> 모든 노드의 Degree(차수)가 2이하

---

Binary Tree

구현

• 순차 자료구조 (ex. 배열)

Node (of Node i)	Index	Condition
Parent	floor( i/2 )	i > 1
Left Child	2i	2i ≤ n
Right Child	2i+1	(2i+1) ≤ n
Root	1	0 < n

• 연결 자료구조 (ex. 하단 코드)

class TreeNode {
    Object data;
    TreeNode left;
    TreeNode right;
}

Traversal (순회)

: Pre-order, In-order, Post-order

D L R
(D : 현재노드, L : 왼쪽 서브트리, R : 오른쪽 서브트리)

1. Pre-order Traversal (전위 순회) : DLR 순서

   PreOrder(현재 트리 노드의 위치 cur){
   Print(cur’s value)
   If(cur’s left exist){
    Pre-Order(cur->left)
   }
   If(cur’s right exist){
    Pre-Order(cur->right)
   }
   }

2. In-order Traversal (중위 순회) : LDR 순서

   InOrder(현재 트리 노드의 위치 cur){
   If(cur’s left exist){
    In-Order(cur->left)
   }
   Print(cur’s value)
   If(cur’s right exist){
    In-Order(cur->right)
   }
   }

3. Post-order Traversal (후위 순회) : LRD 순서

   PostOrder(현재 트리 노드의 위치 cur){
   If(cur’s left exist){
    Post-Order(cur->left)
   }
   If(cur’s right exist){
    Post-Order(cur->right)
   }
   Print(cur’s value)
   }

실습

Input	Output
첫 줄에 트리 노드의 개수 N이 주어집니다. (1 ≤ N ≤ 1,000) 두번째 줄부터 N개의 줄에 0번째 노드부터 N-1번째 노드의 부모 노드가 주어집니다. (-1일 경우 해당 노드가 루트 노드임을 의미합니다.)	각 해당 트리 구조의 Pre-Order, In-Order, Post-Order Traversal 결과를 출력합니다.

import java.util.*;

public class Test {
    static final int EMPTY = -1;
    static final int TREE_MAX_SIZE = 10000;
    static int child[][];
    static int root = 0, N, P;

    static void insert(int parent_idx, int child_idx) {
        if (parent_idx == -1) root = child_idx;
        else if (child[parent_idx][0] == EMPTY) {
            child[parent_idx][0] = child_idx;
        }
        else if (child[parent_idx][1] == EMPTY) {
            child[parent_idx][1] = child_idx;
        }
        else {
            // tree_node has left, right
        }
    }

    static void pre_order(int cur) {
        int left = child[cur][0];
        int right = child[cur][1];
        System.out.print(String.valueOf(cur) + ' ');
        if (left != EMPTY) {
            pre_order(left);
        }
        if (right != EMPTY) {
            pre_order(right);
        }
    }

    static void in_order(int cur) {
        int left = child[cur][0];
        int right = child[cur][1];

        if (left != EMPTY) {
            pre_order(left);
        }
        System.out.print(String.valueOf(cur) + ' ');
        if (right != EMPTY) {
            pre_order(right);
        }
    }

    static void post_order(int cur) {
        int left = child[cur][0];
        int right = child[cur][1];

        if (left != EMPTY) {
            post_order(left);
        }
        if (right != EMPTY) {
            post_order(right);
        }
        System.out.print(String.valueOf(cur) + ' ');
    }

    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        child = new int[TREE_MAX_SIZE][2];
        for (int i = 0; i < TREE_MAX_SIZE; i++)
            for (int j = 0; j < 2; j++)
                child[i][j] = EMPTY;
        N = scanner.nextInt();
        for (int i = 0; i < N; i++) {
            P = scanner.nextInt();
            if (P == -1) {
                root = i;
            }
            else {
                insert(P, i);
            }
        }
        pre_order(root);
        System.out.println("");
        in_order(root);
        System.out.println("");
        post_order(root);
        System.out.println("");
    }
}

Special case

• Full Binary Tree

모든 노드가 포화.
최대 노드 수 : 2^(h+1)-1

• Complete Binary Tree

Full BT에서 뒤에서부터 몇개 빠진 형태
노드 수가 n개일때,
Full BT에서 1번 - n번 노드는 위치가 일치하고
n+1번 - 2^(h+1)-1번 노드는 공백

• Skewed Binary Tree
• Heap
• Binary Search Tree
• Segment Tree
• Binary Indexed Tree