트리(Tree)

트리

개요

• 노드의 링크로 구성된 자료구조 (그래프의 일종, Cycle 없음)
• 계층적 구조를 나타낼 때 사용
  - 폴더 구조(디렉토리, 서브 디렉토리)
  • 조직도, 가계도

구조

• 노드(Node): 트리 구조의 자료 값을 담고 있는 단위
• 에지(Edge): 노드 간의 연결선 (=link, branch)
• 루트 노드(Root): 부모가 없는 노드, 가장 위의 노드
• 잎새 노드(Leaf): 자식이 없는 노드 (=단말)
• 내부 노드(Internal): 잎새 노드를 제외한 모든 노드
• 부모(Parent): 연결된 두 노드 중 상위의 노드
• 자식(Child): 연결된 두 노드 중 하위의 노드
• 형제(Sibling): 같은 부모를 가지는 노드
• 깊이(Depth): 루트에서 어떤 노드까지의 간선의 수
• 레벨(Level): 트리의 특정 깊이를 가지는 노드 집합
• 높이(Height): 트리에서 가장 큰 레벨 값
• 크기(Size): 자신을 포함한 자식 노드의 개수
• 차수(Degree): 각 노드가 지닌 가지의 수
• 트리의 차수: 트리의 최대 차수

트리 구조에 대한 코드

// 트리 구조 구현

import java.util.LinkedList;
import java.util.Queue;

//4개의 멤버 변수를 가진 노드 클래스
class Node{
    char data;  //자신의 값
    Node left;  //왼쪽 자식 노드
    Node right; //오른쪽 자식 노드
    Node parent;    //부모 노드

    Node(char data, Node left, Node right, Node parent){
        this.data = data;
        this.left = left;
        this.right = right;
        this.parent = parent;
    }
}

class BinaryTree {
    Node head;

    BinaryTree(char[] arr){
        Node[] nodes = new Node[arr.length];
        //생성될 때 입력된 배열의 값들을 가져와서 Node 객체 배열에 입력
        for (int i = 0; i < arr.length; i++) {
            nodes[i] = new Node(arr[i], null, null, null);
        }

        //각 인덱스를 계산하여 부모-자식 관계를 연결해줌
        for (int i = 0; i < arr.length; i++) {
            int left = 2 * i + 1;
            int right = 2 * i + 2;

            if(left < arr.length){
                nodes[i].left = nodes[left];
                nodes[left].parent = nodes[i];
            }
            if(right < arr.length) {
                nodes[i].right = nodes[right];
                nodes[right].parent = nodes[i];
            }
        }
        this.head = nodes[0];
    }

    //원하는 값을 가진 노드를 찾는 메소드
    public Node searchNode(char data){
        Queue<Node> queue = new LinkedList<>();
        queue.add(this.head);

        //레벨 별로 큐에 계속 넣어가며 값을 찾음
        while(!queue.isEmpty()){
            //큐에서 값을 꺼내서 비교
            Node cur = queue.poll();

            //원하는 값이 맞으면 리턴 시켜줌
            if(cur.data == data){
                return cur;
            }

            //찾는 값이 아니고 자식 노드가 null이 아니면 그 자식 노드를 큐에 삽입
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }
        //끝까지 값이 안나오면 null을 리턴해줌
        return null;
    }

    //자신을 포함한 자식 노드의 개수를 체크하는 메소드
    public Integer checkSize(char data){
        Node node = this.searchNode(data);

        Queue<Node> queue = new LinkedList<>();
        queue.add(node);
        int size = 0;

        //큐에 자식 노드들을 계속 넣고, 큐에 들어있는 값들을 빼면서 size를 계산함
        while(!queue.isEmpty()){
            Node cur = queue.poll();

            if(cur.left != null){
                queue.offer(cur.left);
                size++;
            }

            if(cur.right != null){
                queue.offer(cur.right);
                size++;
            }
        }
        return size+1;  //크기는 본인 노드까지 합치는 것이기 때문에 +1 해야한다
    }
}

public class Main {

    public static void main(String[] args) {
        char[] arr = new char[10];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (char)('A' + i);
        }

        BinaryTree bt = new BinaryTree(arr);

        // Root node
        System.out.println("Root: " + bt.head.data);    //head가 루트 노드이므로

        // B's child node
        Node B = bt.searchNode('B');
        if(B.left != null){
            System.out.println("B -> left child: "+ B.left.data);
        }
        if(B.right != null){
            System.out.println("B -> right child: "+ B.right.data);
        }


        // F's parent node
        Node F = bt.searchNode('F');
        System.out.println("F -> parent: " + F.parent.data);


        // Leaf node
        System.out.print("Leaf node: ");
        for (int i = 0; i < arr.length; i++) {
            //cur에 전체 노드를 하나씩 넣어가며 검사
            Node cur = bt.searchNode((char)('A' + i));

            //cur에 left도 없고 right도 없으면 자식이 없는 것이므로 Leaf 노드이다
            if(cur.left == null && cur.right == null){
                System.out.print(cur.data + " ");
            }
        }
        System.out.println();


        // E's Depth
        Node E = bt.searchNode('E');
        Node cur = E;
        int cnt = 0;
        //cur에 부모 노드를 계속 할당해가다가, 부모 노드가 없으면 루트이므로 depth를 계산할 수 있다
        while(cur.parent != null){
            cur = cur.parent;
            cnt++;
        }
        System.out.println("E depth: " + cnt);


        // Level2 Node
        System.out.println("Level2 Node: ");
        for (int i = 0; i < arr.length; i++) {
            //전체 노드를 순회하며
            Node target = bt.searchNode((char)('A'+i));
            cur = target;
            cnt = 0;
            //cur에 계속 자신의 부모 노드를 할당한다. null이 나오면 루트노드까지 도달한것. 이때 할당하면서 cnt++를 해주면 레벨을 찾을 수 있다
            while(cur.parent != null){
                cur = cur.parent;
                cnt++;
            }
            if(cnt == 2){   //원하는 레벨을 가진 것들만 출력
                System.out.print(target.data + " ");
            }
        }
        System.out.println();


        // Height
        //레벨을 구한것과 비슷한게 전체를 돌면서 루트노드까지의 거리를 계산하고 그 중에서 최대값을 출력
        int maxCnt = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            Node target = bt.searchNode((char)('A'+i));
            cur = target;
            cnt = 0;
            while(cur.parent != null){
                cur = cur.parent;
                cnt++;
            }
            if(maxCnt < cnt){
                maxCnt = cnt;
            }
        }
        System.out.println("Height: " + maxCnt);


        // B's Size
        int size = bt.checkSize('B');
        System.out.println("B size = " + size);

    }
}

특징

• 하나의 노드에서 다른 노드로 이동하는 경로는 유일
• 노드가 N개인 트리의 Edge의 수는 N-1개
• Acyclic (Cycle이 존재하지 않음)
• 모든 노드는 서로 연결되어 있음
• 하나의 Edge를 끊으면 2개의 서브트리로 분리됨

---

이진트리

개요

• 각 노드는 최대 2개의 자식을 가질 수 있음
• 자식 노드는 좌우를 구분

종류

1. 포화 이진 트리 (Perfect binary tree)
   • 모든 레벨에서 노드들이 꽉 채워져 있는 트리
     
2. 완전 이진 트리 (Complete Binary tree)
   • 마지막 레벨을 제외하고 노드들이 모두 채워져 있는 트리
     
3. 정 이진 트리 (Full binary tree)
   • 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리
     
4. 편향 트리 (Skewed binary tree) = 사향 트리
   • 한쪽으로 기울어진 트리
     
5. 균형 이진 트리 (Balanced binary tree)
   • 모든 노드의 좌우 서브 트리 높이가 1이상 차이 나지 않는 트리
   • 탐색 속도가 훨씬 빠름
     

특징

• 포화 이진 트리의 높이가 h일 때, 노드의 수는 2^(ℎ+1)−1개
• 포화(or 완전) 이진 트리의 노드가 N개 일 때, 높이는 logN
• 이진 트리의 노드가 N개 일 때, 최대 가능 높이는 N

이진 트리의 순회 (Traversal)

• 모든 노드를 빠뜨리거나 중복하지 않고 방문하는 연산
• 순회 종류는 4가지
  - 전위 순회, 중위 순회, 후위 순회 -> DFS(깊이우선탐색)에서 사용
  • 레벨 순회 -> BFS(넓이우선탐색)에서 사용

---

1. 전위 순회
   • preorder Traversal
   • 방문 순서: 현재 노드 -> 왼쪽 노드 -> 오른쪽 노드
     
2. 중위 순회
   • Inorder Traversal
   • 방문 순서: 왼쪽 노드 -> 현재 노드 -> 오른쪽 노드
     
3. 후위 순회
   • Postorder Traversal
   • 방문 순서: 왼쪽 노드 -> 오른쪽 노드 -> 현재 노드
     
4. 레벨 순회
   • Levelorder Traversal
   • 방문 순서: 위쪽 레벨부터 "왼쪽 노드 -> 오른쪽 노드" 순

---

이진 트리 구현

1. 배열로 레벨 순회 순으로 구성한다
   
2. 값과 간선을 멤버로 갖고 있는 노드 객체로 연결리스트를 구성한다

---

이진트리 코드

배열

// 배열을 이용한 이진 트리 구성, 순회

class BinaryTree {
    char[] arr;

    BinaryTree(char[] data){
        this.arr = data.clone();
    }

    //전위 순회
    //순서: 현재 노드 -> 왼쪽 노드 -> 오른쪽 노드
    public void preOrder(int idx){
        System.out.print(this.arr[idx] + " ");  //현재 노드 방문

        //자식 노드들의 인덱스 계산
        //배열의 인덱스가 0부터 시작하기 때문에 +1과 +2를 해준다
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;

        //왼쪽 노드의 인덱스가 전체 크기보다 크지 않아야한다
        if(left < this.arr.length){
            //재귀로 다시 왼쪽 노드에서 전위 순회를 시작한다
            this.preOrder(left);
        }
        //오른쪽 노드의 인덱스가 전체 크기보다 크지 않아야한다
        if(right < this.arr.length){
            //재귀로 다시 오른쪽 노드에서 전위 순회를 시작한다
            this.preOrder(right);
        }
    }

    //중위 순회
    //순서: 왼쪽 노드 -> 현재 노드 -> 오른쪽 노드
    public void inOrder(int idx){
        int left = 2 * idx +1;
        int right = 2 * idx +2;

        if(left < this.arr.length){ //왼쪽 노드
            this.inOrder(left);
        }
        System.out.print(this.arr[idx] + " ");  //현재 노드

        if(right < this.arr.length){    //오른쪽 노드
            this.inOrder(right);
        }
    }

    //후위 순회
    //순서: 왼쪽 노드 -> 오른쪽 노드 -> 현재 노드
    public void postOrder(int idx){
        int left = idx * 2 + 1;
        int right = idx * 2 + 2;

        if(left < this.arr.length){ //왼쪽 노드
            this.postOrder(left);
        }
        if(right < this.arr.length){    //오른쪽 노드
            this.postOrder(right);
        }
        System.out.print(this.arr[idx] + " ");  //현재 노드
    }

    //레벨 순회
    //각 레벨에서 왼쪽->오른쪽 순으로 방문
    public void levelOrder(int idx){
        for (int i = idx; i < this.arr.length; i++) {
            System.out.print(this.arr[i] + " ");
        }
        System.out.println();
    }
}

public class Main {
    public static void main(String[] args) {
        // Test code
        char[] arr = new char[10];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (char)('A' + i);
        }

        BinaryTree bt = new BinaryTree(arr);

        System.out.println("== Preorder ==");
        bt.preOrder(0);
        System.out.println();

        System.out.println("== Inorder ==");
        bt.inOrder(0);
        System.out.println();

        System.out.println("== Postorder ==");
        bt.postOrder(0);
        System.out.println();

        System.out.println("== Levelorder ==");
        bt.levelOrder(0);
        System.out.println();
    }
}

연결리스트

// 연결 리스트를 이용한 이진 트리 구성, 순회

import java.util.LinkedList;
import java.util.Queue;

class Node{
    char data;
    Node left;
    Node right;

    Node(char data, Node left, Node right){
        this.data = data;
        this.left = left;
        this.right = right;
    }

}
class BinaryTree {
    Node head;
    BinaryTree(){}

    //입력 받은 배열을 인덱스 계산하여 순서대로 연결 리스트에 넣어줌
    BinaryTree(char[] arr){
        Node[] nodes = new Node[arr.length];

        //우선 각 값을 Node 객체에 넣어주고
        for (int i = 0; i < arr.length; i++) {
            nodes[i] = new Node(arr[i], null, null);
        }

        //인덱스에 맞춰서 연결시켜줌
        for (int i = 0; i < arr.length; i++) {
            int left = 2 * i + 1;
            int right = 2 * i + 2;

            if (left < arr.length) {
                nodes[i].left = nodes[left];
            }
            if(right < arr.length){
                nodes[i].right = nodes[right];
            }
        }
        this.head = nodes[0];
    }

    //전위 순회
    public void preOrder(Node node){
        if(node == null){   //노드가 없으면 종료. 재귀 종료 조건으로 비어있는 노드까지 가면 종료되고, 재귀가 순차적으로 끝난다
            return;
        }
        System.out.print(node.data + " ");
        preOrder(node.left);
        preOrder(node.right);
    }

    //중위 순회
    public void inOrder(Node node){
        if(node == null){
            return;
        }
        inOrder(node.left);
        System.out.print(node.data + " ");
        inOrder(node.right);
    }

    //후위 순회
    public void postOrder(Node node){
        if(node == null){
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.data + " ");
    }

    //레벨 순회
    //큐를 사용하여 출력
    public void levelOrder(Node node){
        Queue<Node> queue = new LinkedList<>();
        queue.add(node);    //출력을 시작할 노드를 맨처음 큐에 추가
        while(!queue.isEmpty()){
            Node cur = queue.poll();    //큐에서 꺼내옴

            System.out.print(cur.data + " ");
            if(cur.left != null){   //cur의 left가 있으면 큐에 추가
                queue.offer(cur.left);
            }
            if(cur.right != null){  //cur의 right가 있으면 큐에 추가
                queue.offer(cur.right);
            }
        }
    }

}


public class Main {
    public static void main(String[] args) {
        // Test code
        char[] arr = new char[10];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (char)('A' + i);
        }

        BinaryTree bt = new BinaryTree(arr);

        System.out.println("== Preorder ==");
        bt.preOrder(bt.head);
        System.out.println();

        System.out.println("== Inorder ==");
        bt.inOrder(bt.head);
        System.out.println();

        System.out.println("== Postorder ==");
        bt.postOrder(bt.head);
        System.out.println();

        System.out.println("== Levelorder ==");
        bt.levelOrder(bt.head);
        System.out.println();
    }
}