[Java] 트리

 

 

Tree에 대한 이론은 앞서 정리했었다.

 

[알고리즘] 그래프 이론 기초

 

---

1. 이진트리 - 특성

 

• 높이 n(0부터 시작)에 위치한 노드의 최대 개수는 2^n개
• 높이가 n인 이진 트리가 가질 수 있는 노드의 …
  • 최소 개수는 n+1개다. → 변질(편향) 이진트리
  • 최대 개수는 2^(n+1)-1개다. → 포화 이진 트리

 

---

2. 이진 트리 - 구현

 

가. 배열 - 노드 번호를 인덱스로 사용

 

• 루트의 번호를 1로 함.
• n 레벨에 위치한 노드에 대하여 왼쪽에서 오른쪽으로 2^n부터 2^(n+1)-1까지 번호를 부여
• 노드 번호가 i인 노드의 …
  • 부모 노드 : i/2
  • 왼쪽 자식 노드 : 2 * i
  • 오른쪽 자식 노드 : 2 * i +1

 

이진트리를 배열로 표현할 때 주의점

• 주어진 트리가 편향 이진트리라면 배열로 표현하면 심각한 공간의 낭비가 발생한다.
• 트리의 중간에 새로운 노드를 삽입, 삭제할 경우 배열의 크기 변경이 필요해서 어렵고 비효율적이다.

 

---

나. 배열 - 값을 인덱스로 사용

 

노드 번호를 인덱스로 사용하지 않고 별도의 클래스를 정의하고 그곳의 멤버 변수로 저장한다.

 

대신 특정한 value값을 인덱스로 사용한다. (ex. 배열의 인덱스, ascii 코드)

 

• tree[value -'A'] : 주어지는 알파벳의 ascii 코드를 인덱스로 사용.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int N; // 알파벳 개수 26개
    static Node[] tree;
    static StringBuffer sb; 
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 초기화
        sb = new StringBuffer();
        N = Integer.parseInt(st.nextToken());
        tree = new Node[N];
        input(br);

        // 순회
        dfsByPreorder(tree[0]);
        sb.append("\n");
        dfsByInorder(tree[0]);
        sb.append("\n");
        dfsByPostorder(tree[0]);
        sb.append("\n");

        // 출력
        System.out.println(sb.toString());
        br.close();
    }

    static void input(BufferedReader br) throws Exception {
        for(int i=0; i<N; i++) { // 노드 저장
            String[] input = br.readLine().trim().split(" ");
            char value = input[0].charAt(0);
            char left = input[1].charAt(0);
            char right = input[2].charAt(0);

            // 자기 자신이 존재하는지
            if(tree[value -'A']== null) {
                tree[value -'A'] = new Node(value); // 없으면 생성
            }
            Node node = tree[value -'A'];

            // left가 존재하는지
            if(left!='.') {
                tree[left -'A'] = new Node(left);
                node.left = tree[left - 'A']; // left node 설정
            }

            // right가 존재하는지
            if(right!='.') {
                tree[right -'A'] = new Node(right);
                node.right = tree[right - 'A']; // right node 설정
            }
        }
    }
    // 전위 순회
    private static void dfsByPreorder(Node node) {
        if(node == null) return;
        sb.append(node.value);
        dfsByPreorder(node.left);
        dfsByPreorder(node.right);
    }
    // 중위 순회
    private static void dfsByInorder(Node node) {
        if(node == null) return;
        dfsByInorder(node.left);
        sb.append(node.value);
        dfsByInorder(node.right);
    }
    // 후위 순회
    private static void dfsByPostorder(Node node) {
        if(node == null) return;
        dfsByPostorder(node.left);
        dfsByPostorder(node.right);
        sb.append(node.value);
    }

    static class Node {
        char value;
        Node left;
        Node right;

        Node(char value){
            this.value = value;
        }
    }

}

1991번: 트리 순회

 

---

3. 트리의 완전 탐색

 

사용한 완전 이진트리.

import java.util.ArrayDeque;
import java.util.Queue;

// 완전이진트리 - 배열 구현
// 고정된 크기를 가진다.
public class CompleteBinaryTree<T> {

    private Object[] nodes;
    //private T[] nodes2;
    private final int SIZE;
    private int lastIndex;

    public CompleteBinaryTree(int size) {
        SIZE = size;
        nodes = new Object[size+1];
        //nodes2 = new T[size+1]; error
    }
    public boolean isEmpty() {
        return lastIndex == 0;
    }
    public boolean isFull() {
        return lastIndex == SIZE;
    }
    public void add(T e) {
        if(isFull()) {
            System.out.println("full");
            return;
        }
        lastIndex++;
        nodes[lastIndex] = e;
    }
}

public class CompleteBinaryTreeTest {

    public static void main(String[] args) {
        CompleteBinaryTree<Character> tree = new CompleteBinaryTree<>(10);

        for(int i=0; i<10; i++) {
            tree.add((char)(65+i));
        }

        tree.bfs();

    }

}

 

---

가. BFS

 

1) 일반

public class CompleteBinaryTree<T> {
    ...
    public void bfs() {
        if(isEmpty()) return;
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(1);

        while(!queue.isEmpty()) {
            int cur = queue.poll();
            System.out.println(nodes[cur]);

            // left node
            if(cur*2<=lastIndex) queue.offer(cur*2);
            // right node
            if(cur*2+1<=lastIndex) queue.offer(cur*2+1);
        }

    }

}

 

2) 너비 단위로 탐색

// 너비 단위로 탐색 - 너비 정보 저장
private void bfs2() {
    if(isEmpty()) return;
    Queue<int[]> queue = new ArrayDeque<>();
    queue.offer(new int[] {1,0}); // node number, breadth

    while(!queue.isEmpty()) {
        int[] cur = queue.poll();
        System.out.println(cur[0] +" : "+ cur[1]);

        // left node
        if(cur[0]*2<=lastIndex) queue.offer(new int[] {cur[0]*2, cur[1]+1});
        // right node
        if(cur[0]*2+1<=lastIndex) queue.offer(new int[] {cur[0]*2+1, cur[1]+1});
    }
}

• queue.offer(new int[]{1,0}); : 너비 정보를 따로 저장.

 

// 너비 단위로 탐색 - queue size 활용
private void bfs3() {
    if(isEmpty()) return;
    Queue<Integer> queue = new ArrayDeque<>();
    queue.offer(1);

    int cur=0, size=0, breadth=0;
    while(!queue.isEmpty()) {
        size=queue.size();
        System.out.print(breadth +" : ");
        while(size>0) {
            size--;
            cur = queue.poll();
            System.out.print(nodes[cur]+"\t");
            // left node
            if(cur*2<=lastIndex) queue.offer(cur*2);
            // right node
            if(cur*2+1<=lastIndex) queue.offer(cur*2+1);
        }
        System.out.println();
        ++breadth;
    }
}

• size=queue.size();, while(size>0) { : Queue의 사이즈를 활용해서 동일한 너비를 한 번에 처리.

 

1991번: 트리 순회

 

---

나. DFS

 

• 재귀로 구현.

private void dfsByPreorder(int cur) {
    // preorder
    System.out.println(nodes[cur]+"\t");
    // left node
    if(cur*2<=lastIndex) dfsByPreorder(cur*2);
    // right node
    if(cur*2+1<=lastIndex) dfsByPreorder(cur*2+1);
}

private void dfsByInorder(int cur) {
    // left node
    if(cur*2<=lastIndex) dfsByPreorder(cur*2);
    // inorder
    System.out.println(nodes[cur]+"\t");
    // right node
    if(cur*2+1<=lastIndex) dfsByPreorder(cur*2+1);
}

private void dfsByPostorder(int cur) {
    // left node
    if(cur*2<=lastIndex) dfsByPreorder(cur*2);
    // right node
    if(cur*2+1<=lastIndex) dfsByPreorder(cur*2+1);
    // postorder
    System.out.println(nodes[cur]+"\t");
}

 

---