11 to 9, Day 25

Today, ToDoList

• 큐 자료구조
• 트리 자료구조

---

큐 자료구조

package queue;

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

public class MyStack<T> extends Stack<T> {

    Queue<T> queue = new LinkedList<>();

    //Queue로 Stack을 구현하기
    @Override
    public T pop() {
        Queue<T> tempQueue = new LinkedList<>();
        while (queue.size() > 1) {
            tempQueue.offer(queue.poll());
        }
        T result = queue.poll();
        queue = tempQueue;
        return result;
    }

    @Override
    public synchronized T peek() {
        Queue<T> tempQueue = new LinkedList<>();
        while (queue.size() > 1) {
            tempQueue.offer(queue.poll());
        }
        T result = queue.peek();
        tempQueue.offer(queue.poll());
        queue = tempQueue;
        return result;
    }

    @Override
    public T push(T item) {
        queue.offer(item);
        return item;
    }

    public static void main(String[] args) {
        MyStack<Integer> myStack = new MyStack<>();
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        System.out.println(myStack.queue);
        System.out.println(myStack.peek());
        System.out.println(myStack.peek());
        System.out.println(myStack.peek());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
    }
}

---

트리 자료구조

• 루트 : 부모 노드가 없는 노드
• 엣지 : 부모에서 자식으로 연결되는 선
• 리프 : 자식 노드가 없는 노드
• 시블링 : 부모 노드가 같은 노드들
• 레벨 : 0(루트)레벨 부터 다음 자식방향으로 커지는 단계
• 노드의 깊이 : 루트에서 해당 노드까지의 길이
• 노드의 높이 : 해당 노드에서 가장 깊은 리프까지의 길이
• 트리의 깊이 : 모든 노드의 깊이 중 최대값
• 트리의 높이 : 모든 노드의 높이 중 최대값
• 노드의 크기 : 해당 노드를 포함한 자손 노드의 수

이진 트리

각 노드의 자식 노드의 수가 최대 2개이다.

• 엄격한 이진 트리 : 모든 노드가 2개의 자식 노드를 가지거나 자식 노드가 없다.
• 포화 이진 트리 : 엄격한 이진트리에서 모든 리프노드가 같은 레벨이다.
• 완전 이진 트리 : 마지막 레벨이 h일때 h-1까지는 포화상태이며 h레벨에서는 가능한 왼쪽으로 채워져있다.

이진 검색 트리 (BST)

검색용 이진 트리

• 어떤 노드 왼쪽 서브 트리의 모든 값들은 해당 노드의 값 보다 작아야 한다.
• 어떤 노드 오른쪽 서브 트리의 모든 값들은 해당 노드의 값 보다 커야 한다.
• 왼쪽 서브 트리나 오른쪽 서브트리 모두 각각 이진 검색 트리이다.

트리 순회

• 전위탐색 : 노드, 왼쪽, 오른쪽 또는 노드, 오른쪽, 왼쪽
• 중위탐색 : 왼쪽, 노드, 오른쪽 또는 오른쪽, 노드, 왼쪽
• 후위탐색 : 왼쪽, 오른쪽, 노드 또는 오른쪽, 왼쪽, 노드
• 레벨탐색 (BFS) : 레벨 0 -> H

package tree;

import java.util.Stack;

public class MyTree {

    private static class Node {
        Node left;
        Node right;
        int value;

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

    //중위탐색 - 재귀
    public void inOrder1(Node root) {
        if ( root == null ) {
            return;
        }

        inOrder1(root.left);
        System.out.print(root.value);
        inOrder1(root.right);
    }

    //중위탐색 - 순회
    public void inOrder2(Node root) {
        if ( root == null ) {
            return;
        }

        Stack<Node> stack = new Stack<>();
        Node current = root;

        while (true) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }

            if (stack.isEmpty()) {
                break;
            }

            current = stack.pop();
            System.out.print(current.value);
            current = current.right;
        }
    }

    //후위탐색에서 n번째 값을 출력하기
    //시간복잡도 O(N), 공간복잡도 O(LogN)
    int count = 0;
    public void postOrder(Node root, int num) {
        if ( root == null ) {
            return;
        }

        postOrder(root.left, num);
        postOrder(root.right, num);
        if ( ++count == num ) {
            System.out.println(root.value);
            count = 0;
        }
    }

    //트리의 높이 구하기
    public int solution(Node root) {
        if ( root == null ) {
            return -1;
        }

        int leftValue = solution(root.left);
        int rightValue = solution(root.right);

        if ( leftValue > rightValue ) {
            return leftValue + 1;
        } else {
            return rightValue + 1;
        }
    }

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        Node node8 = new Node(8);

        //      1
        //    2   3
        //   4 5 6 7
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        MyTree myTree = new MyTree();
        myTree.inOrder1(node1);
        System.out.println("");
        myTree.inOrder2(node1);
        System.out.println("");
        myTree.postOrder(node1, 4);
        System.out.println(myTree.solution(node1));
    }
}