[자료구조] 18. 트리(Tree)의 개념

HashSet, LinkedHashSet 다음에 다루려던 것이 TreeSet이었는데 TreeSet이 내부적으로 Red-Black Tree로 구현되어있다. 그런데 또 Red-Black Tree를 이해하려면 BST(Binary Search Tree)도 이해해야 하고 결과적으로 TreeSet을 알아보기 전에 Tree 에 대한 개념과 이해를 선행해야겠다는 생각이 들었다. 그래서 트리에 대해 전반적으로 알아보고 차례대로 Tree 종류들을 알아보고 TreeSet을 다뤄보도록 할 것이다.

 

Tree

트리는 비선형구조이다. 일반적으로 대상 정보의 각 항목들을 계층적으로 연관되도록 구조화 시키고자 할 때 사용되는 자료구조이다. 데이터의 요소들이 단순한 나열이 아닌 부모 - 자식 관계의 계층적 구조로 표현된다. 아래 이미지를 보면서 자세히 알아보자.

 

• Node : 트리를 구성하고 있는 각 요소
• Edge (간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선
• Root Node : 트리의 최상위 게층에 존재하는 노드
• Level : 트리의 특정 깊이를 가지는 노드의 집합
• Degree (차수) : 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지(간선)의 수
• Terminal Node (= Leaf Node, 단말노드) : 하위에 다른 자식 노드를 갖지 않는 노드. 그림에서 주황색 노드들이 내부 노드이다.
• Internal Node (내부 노드, 비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드를 포함. 그림에서 파란색 노드들이 내부 노드이다.

 

트리 구현

 

트리는 종류에 따라서 구현하는 방법이 여러가지이긴하다. 세 가지로 구현해볼 것인데 1차원 배열, 2차원 배열, 클래스로 구현해볼 것이다.

1차원 배열 구현

주로 포화 이진 트리나, 완전 이진 트리의 경우 많이 쓰이는 방법이다. 그외의 이진트리도 저장이 불가능한 것은 아니나 메모리의 낭비가 심해진다. 따라서 포화 이진트리 또는 완전 이진트리를 1차원 배열로 구현해볼 것이다.

 

루트 노드는 1부터 시작한다. 부모 자식 관계의 트리 구조에서 인덱스를 계산하는데 있어서 루트 노드를 1로 두는 것이 용이하기 때문이다.

그리고 원하는 노드 n 개까지 총 n+1 크기의 1차원 배열로 구현한다. 배열 표현법에서는 인덱스만 알면 노드의 부모나 자식을 쉽게 알 수 잇다.

• 노드 i의 부모 노드 인덱스 = i/2
• 노드 i의 왼쪽 자식 인덱스 = 2 * i
• 노드 i의 오른쪽 자식 인덱스 = (2 * i) + 1

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

/**
 * 루트가 1인 완전 이진 트리, 포화 이진 트리를 1차원 배열에 저장 후 각 인덱스의 부모 노드를 출력한다.
 * 입력 : 첫 번째 줄에 트리 노드 개수 n 이 주어진다.
 * 출력 : 각 인덱스의 부모 노드를 출력한다.
 *
 * 포화 이진 트리이거나 완전 이진 트리이기 때문에 1차원 배열 n+1 만큼 번호 순서대로 저장하면 된다.
 */

public class Tree_Use_One_Dimension_Array {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] parent = new int[N + 1];      // 트리 저장을 위한 1차원 배열.

        for (int i = 2; i <= N; i++) {      // 1은 루트이므로 2부터 시작 (tree[1] = 0)
            parent[i] = i / 2;              // 노드 i 의 부모 인덱스 = i / 2
        }

        System.out.println(Arrays.toString(parent));
    }
}

 

2차원 배열 구현

 

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

/**
 * 이차원 배열로 구현한 트리의 전위, 중위, 후위 순회 결과 출력
 * 2차원 배열 [x][0] -> 노드 x 의 왼쪽 자식
 *          [x][1] -> 노드 x 의 오른쪽 자식
 *
 *          위 방법대로 저장하면서 트리 입력을 받는다.
 *
 * 입력 : 첫째 줄에 트리의 노드 개수 n 이 주어진다. (1 <= n <= 100)
 *      둘째 줄부터 트리의 정보가 주어진다. 각 줄은 3개의 숫자 a, b, c 로 이뤄진다.
 *      (노드 a의 왼쪽 자식 b, 오른쪽 자식 c
 *      자식노드가 존재하지 않다면 -1이 주어진다.
 *
 * 출력 : 첫째 줄에 전위순회, 둘째 줄에 중위순회, 셋째 줄에 후위순회 결과 출력
 *
 * 6
 * 0 1 2
 * 1 3 4
 * 2 -1 5
 * 3 -1 -1
 * 4 -1 -1
 * 5 -1 -1
 */
public class Tree_Use_Two_Dimension_Array {
    static int N;
    static int[][] tree;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        tree = new int[N][2];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            tree[a][0] = b;
            tree[a][1] = c;
        }

        System.out.println("전위 순회");
        preOrder(0);

        System.out.println("중위 순회");
        inOrder(0);

        System.out.println("후위 순회");
        postOrder(0);
    }

    // 전위순회 preOrder : Root -> Left -> Right
    public static void preOrder(int x) {
        // 자식 노드가 모두 없다면 순회를 멈춘다.
        if (tree[x][0] == -1 && tree[x][1] == -1) {
            System.out.print(x + " ");
        } else {
            System.out.print(x + " ");
            if (tree[x][0] != -1) {
                preOrder(tree[x][0]);
            }
            if (tree[x][1] != -1) {
                preOrder(tree[x][1]);
            }
        }

    }

    // 중위순회 inOrder : Left -> Root -> Right
    public static void inOrder(int x) {
        if (tree[x][0] == -1 && tree[x][1] == -1) {
            System.out.print(x + " ");
        } else {
            if (tree[x][0] != -1) {
                inOrder(tree[x][0]);
            }
            System.out.print(x + " ");
            if (tree[x][1] != -1) {
                inOrder(tree[x][1]);
            }
        }
    }

    // 후위순회 postOrder : Left -> Right -> Root
    public static void postOrder(int x) {
        if (tree[x][0] == -1 && tree[x][1] == -1) {
            System.out.print(x + " ");
        } else {
            if (tree[x][0] != -1) {
                postOrder(tree[x][0]);
            }
            if (tree[x][1] != -1) {
                postOrder(tree[x][1]);
            }
            System.out.print(x + " ");
        }
    }

}

트리 저장 방식은 코드의 주석에서 설명했지만 다시 설명하자면 x 노드의 왼쪽, 오른쪽 자식을 0, 1 인덱스에 입력을 받아 저장해나간다.

전위, 중위, 후위 순회에서 재귀를 이용하고 있다. 첫번째 분기에서 왼쪽, 오른쪽 모두 자식이 없는 즉 단말노드인 경우 출력을 하고 단말노드가 아니고 자식노드를 가지고 있다면 해당 값을 가지고 재귀를 타고 다시 검사를 한다. 그렇게 되면 각 순회 방식 조건에 맞게 단말노드들을 모두 출력하게 된다.

 

클래스 구현

트리를 표현할 노드 클래스를 하나 만든다. 하나의 노드는 데이터, 왼쪽, 오른쪽 자식을 가리키는 필드를 가진다. 마찬가지로 이를 활용하여 전, 중, 후위 순회를 출력해볼 것이다.

 

public class Node {
    int data; 
    Node left;
    Node right;

    public Node(int data) {
        this.data = data;
    }
}

 

트리 클래스는 아래의 메소드들로 구성된다.

• createNode() : 값을 추가한다.
• searchNode() : 값이 어느 위치에 추가할것인지 찾는다.
• preOrder, inOrder, postOrder

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

/**
 * 클래스로 구현한 이진 트리의 전, 중, 후 순휘 결과 출력
 * Class 에 data, left, right 값을 저장하여 구현
 *
 * 6
 * 0 1 2
 * 1 3 4
 * 2 -1 5
 * 3 -1 -1
 * 4 -1 -1
 * 5 -1 -1
 *
 */
public class Tree_Use_Class {
    public Node root;       // 초기 root 는 Null;

    public void createNode(int data, int leftData, int rightData) {
        // 초기 상태 - 루트 노드 생성
        if (root == null) {
            root = new Node(data);

            // 좌우 값이 있는 경우, 즉 -1이 아닌 경우 노드 생성
            if (leftData != -1) {
                root.left = new Node(leftData);
            }
            if (rightData != -1) {
                root.right = new Node(rightData);
            }
        }
        // 초기 상태가 아니라면, 루트 노드 생성 이후 만들어진 노드 중 어떤 것인지 찾는다.
        else {
            searchNode(root, data, leftData, rightData);
        }
    }

    public void searchNode(Node node, int data, int leftData, int rightData) {
        if (node == null) return;       // 도착한 노드가 Null 이면 재귀 종료 - 찾을 노드 X

        // 들어갈 위치를 찾았다면
        else if (node.data == data) {
            if (leftData != -1) {       // 값이 있는 경우에만 좌우 노드 생성
                node.left = new Node(leftData);
            }
            if (rightData != -1) {
                node.right = new Node(rightData);
            }
        }
        // 아직 찾지 못하고 탐색할 노드가 더 남았다면
        else {
            searchNode(node.left, data, leftData, rightData);
            searchNode(node.right, data, leftData, rightData);
        }
    }

    // 전위 : Root -> Left -> Right
    public void preOrder(Node node) {
        if (node != null) {
            System.out.print(node.data + " ");
            if (node.left != null) preOrder(node.left);
            if (node.right != null) preOrder(node.right);
        }
    }

    // 중위 : Left -> Root -> Right
    public void inOrder(Node node) {
        if (node != null) {
            if (node.left != null) inOrder(node.left);
            System.out.print(node.data + " ");
            if (node.right != null) inOrder(node.right);
        }
    }

    // 후위 : Left -> Right -> Root
    public void postOrder(Node node) {
        if (node != null) {
            if (node.left != null) inOrder(node.left);
            if (node.right != null) inOrder(node.right);
            System.out.print(node.data + " ");
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        Tree_Use_Class tree = new Tree_Use_Class();

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            tree.createNode(a, b, c);
        }

        System.out.println("전위 순회");
        tree.preOrder(tree.root);
        System.out.println();

        System.out.println("중위 순회");
        tree.inOrder(tree.root);
        System.out.println();

        System.out.println("후위 순회");
        tree.postOrder(tree.root);
        System.out.println();
    }
}

 

---

정리 

간단히 트리 개념을 짚고 넘어가는 것이라 트리 구성요소의 용어들과 전,중,후 순회 출력 구현을 해봤다. 다음 포스트에서는 BST, Red-Black Tree에 대해서 다뤄보도록 하겠다.

 

---

출처

트리(Tree)의 개념과 종류 / Java 구현

 

[Java] 트리(tree) 구현 - 1차원 배열 / 2차원 배열 / 클래스 3가지 방법 구현