비선형 자료구조 - Tree

트리 (Tree)

노드와 링크로 구성된 자료구조 (그래프의 일종, Cycle 없음)
계층적 구조를 나타낼 때 사용

• 폴더 구조 (디렉토리, 서브 디렉토리)
• 조직도, 가계도, ...

트리의 구조

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

트리의 특징

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

이진 트리 (Binary Tree)

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

• 왼쪽 자식 : 부모 노드의 왼쪽 아래
• 오른쪽 자식 : 부모 노드의 오른쪽 아래

  

특징

• 포화 이진 트리의 높이가 n일 때, 노드의 수는 2의 n+1승 -1개
• 포화(or 완전) 이진 트리의 노드가 N일 때, 높이는 ㏒N
• 이진 트리의 노드가 N일 때, 최대 가능 높이는 N

포화 이진 트리 (Perfect Binary Tree)

모든 레벨에서 노드들이 꽉 채워져 있는 트리

완전 이진 트리 (Complete Binary Tree)

마지막 레벨을 제외하고는 노드들이 모두 채워져 있는 트리

정 이진 트리 (Full Binary Tree)

모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리

편향 트리 (Skewed Binary Tree)

한쪽으로 기울어진 트리

균형 이진 트리 (Balanced Binary Tree)

모든 노드의 좌우 서브 트리 높이가 1이상 차이 나지 않는 트리

이진 트리의 순회 (Traversal)

모든 노드를 빠트리거나 중복하지 않고 방문하는 연산

• 전위 순회, 중위 순회, 후외 순회, 레벨 순회

전위 순회 (Preorder Traversal

방문 순서 : 현재 노드 -> 왼쪽 노드 -> 오른쪽 노드

중위 순회 (Inorder Traversal)

방문 순서 : 왼쪽 노드 -> 현재 노드 -> 오른쪽 노드

후위 순회 (Postorder Traversal)

방문 순서 : 왼쪽 노드 -> 오른쪽 노드 -> 현재 노드

레벨 순회 (Levelorder Traversal)

방문 순서 : 위쪽 레벨부터 왼쪽 노드 -> 오른쪽 노드 (순차적으로)

이진 트리 구현

배열

레벨 순회 순으로 배열에 구성

PreOrder

 public void preOrder(int idx){
        System.out.print(this.arr[idx] + " ");
        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);
        }
    }

InOrder

 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);
        }
    }

PostOrder

public void postOrder(int idx){
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;
        if (left < this.arr.length) {
            this.postOrder(left);
        }
        if (right < this.arr.length){
            this.postOrder(right);
        }
        System.out.print(this.arr[idx] + " ");
    }

LevelOrder

public void levelOrder(int idx){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(this.arr[i] + " ");
        }
        System.out.println( );
    }

연결 리스트

값과 간선을 관리하기 위한 노드로 연결리스트 구성

Node 생성

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

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

///생성
BinaryTree2(char[] arr){
        Node[] nodes = new Node[arr.length];
        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];
    }

PreOrder

public void preOrder(Node node){
        if (node == null){
            return;
        }

        System.out.print(node.data + " ");
        this.preOrder(node.left);
        this.preOrder(node.right);
    }

InOrder

  public void inOrder(Node node){
        if (node == null){
            return;
        }
        this.inOrder(node.left);
        System.out.print(node.data + " ");
        this.inOrder(node.right);
    }

PostOrder

public void postOrder(Node node){
        if (node == null){
            return;
        }

        this.postOrder(node.left);
        this.postOrder(node.right);
        System.out.print(node.data + " ");
    }

LevelOrder

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){
                queue.offer(cur.left);
            }
            if (cur.right != null){
                queue.offer(cur.right);
            }
        }
    }