ksundong/자료구조-스터디-4주차.md

## 자료구조-스터디-4주차.md

      
    Raw
  

              자료구조-스터디-4주차.md
            
          
    자바 자료구조 스터디 4주차

이 md 파일은 Typora 에서 작성되었습니다. 읽으실 때, Typora 에서 읽으시는 것이 가장 보기에 좋습니다.
[TOC]
큐(Queue)

큐의 이해와 ADT 정의

큐는 스택과 같이 언급이 많이되고 비교가 많이 되죠.
특성 정도는 기억해주는 것이 좋습니다 FIFO(First In First Out, 선입선출) 특성은 반드시 알고 있어야 합니다.
큐(Queue)의 이해

스택에 비해 큐는 이해하기 쉬운 자료입니다. Queue 자체가 대기열의 의미를 가지고 있기 때문이죠. 즉 줄을 서는 것을 연상하면 됩니다.
큐의 ADT 정의


enqueue: 큐에 데이터를 넣는 연산
dequeue: 큐에서 데이터를 꺼내는 연산

위의 두 가지가 핵심 연산입니다.
인터페이스를 정의해봅시다!
Queue.java
package queue;

/**
 * Queue 자료구조의 ADT, 인터페이스
 *
 * @param <E> 데이터의 파라미터 타입
 * @author dion
 */
public interface Queue<E> {

  /**
   * 큐에 저장된 데이터의 개수를 반환합니다.
   *
   * @return 데이터의 개수
   */
  int size();

  /**
   * 큐가 비어있는지 여부를 반환합니다.
   *
   * @return 큐가 비어있으면 true, 그렇지 않으면 false
   */
  boolean isEmpty();

  /**
   * 큐에 파라미터로 전달된 데이터를 마지막에 저장합니다.
   *
   * @param data 저장할 데이터
   */
  void enqueue(E data);

  /**
   * 큐의 처음에 위치한 데이터를 꺼냅니다. 이 함수를 호출하기 위해서는 데이터가 하나 이상 있음이 보장되어야 합니다.
   *
   * @return 처음에 위치했던 데이터
   */
  E dequeue();

  /**
   * 큐의 처음에 위치한 데이터를 확인합니다. 이 함수를 호출하기 위해서는 데이터가 하나 이상 있음이 보장되어야 합니다.
   *
   * @return 처음에 위치한 데이터
   */
  E peek();
}
큐 또한 선형자료구조 임으로 배열과 연결 리스트 둘 다 구현 가능합니다.
또한 우리는 먼저 테스트를 만들고 이를 구현하면서 원하는대로 동작하는지 검증하는 식으로 구현해봅시다.
테스트 코드 작성

QueueTest.java
class QueueTest {

  @Test
  @DisplayName("배열_기반_큐_생성_테스트")
  void 배열_기반_큐_생성_테스트() {
    Queue<Integer> queue = ArrayQueue<>();

    assertThat(queue).isNotNull();
    assertThat(queue.isEmpty()).isTrue();
    assertThat(queue.size()).isEqualTo(0);
  }

  @Test
  @DisplayName("배열_기반_큐_생성_테스트")
  void 배열_기반_큐_EmptyQueueException_테스트() {
    Queue<Integer> queue = ArrayQueue<>();

    assertThat(queue).isNotNull();
    assertThat(queue.isEmpty()).isTrue();
    assertThat(queue.size()).isEqualTo(0);
    assertThatThrownBy(queue::dequeue).isInstanceOf(EmptyQueueException.class);
    assertThatThrownBy(queue::peek).isInstanceOf(EmptyQueueException.class);
  }

  @Test
  @DisplayName("배열_기반_큐_데이터_저장_테스트")
  void 배열_기반_큐_데이터_저장_테스트() {
    Queue<Integer> queue = ArrayQueue<>();

    queue.enqueue(1);
    queue.enqueue(2);
    queue.enqueue(3);
    queue.enqueue(4);
    queue.enqueue(5);
    
    assertThat(queue).isNotNull();
    assertThat(queue.isEmpty()).isFalse();
    assertThat(queue.size()).isEqualTo(5);
  }

  @Test
  @DisplayName("배열_기반_큐_데이터_저장_후_제거_테스트")
  void 배열_기반_큐_데이터_저장_후_제거_테스트() {
    Queue<Integer> queue = ArrayQueue<>();

    queue.enqueue(1);
    queue.enqueue(2);
    queue.enqueue(3);
    queue.enqueue(4);
    queue.enqueue(5);

    assertThat(queue).isNotNull();
    assertThat(queue.isEmpty()).isFalse();
    assertThat(queue.size()).isEqualTo(5);
    assertThat(queue.peek()).isEqualTo(1);
    assertThat(queue.dequeue()).isEqualTo(1);
    assertThat(queue.size()).isEqualTo(4);
    assertThat(queue.peek()).isEqualTo(2);
    assertThat(queue.dequeue()).isEqualTo(2);
    assertThat(queue.size()).isEqualTo(3);
    assertThat(queue.peek()).isEqualTo(3);
    assertThat(queue.dequeue()).isEqualTo(3);
    assertThat(queue.size()).isEqualTo(2);
    assertThat(queue.peek()).isEqualTo(4);
    assertThat(queue.dequeue()).isEqualTo(4);
    assertThat(queue.size()).isEqualTo(1);
    assertThat(queue.peek()).isEqualTo(5);
    assertThat(queue.dequeue()).isEqualTo(5);
    assertThat(queue.isEmpty()).isTrue();
    assertThat(queue.size()).isEqualTo(0);
  }
}
EmptyQueueException은 직접 작성해야하는 예외입니다.
EmptyQueueException.java
public class EmptyQueueException extends RuntimeException {

  public EmptyQueueException() {
    super("Queue is Emtpy.");
  }
}
큐의 배열 기반 구현

큐는 일반적인 선형구조로 구현하면 매우 성능이 구려지게됩니다. 그래서 이 책에선 다른 구조를 고려하는 것 같네요.
원형 큐(Circular Queue)의 소개

끝을 가리키는 포인터가 순환하도록 만든 큐입니다. 논리적으로 원형 구조를 이루게됩니다.
그리고 꽉 채우지 않는다는 점이 핵심인 것 같아요.
꽉채우지 않았을 때, 텅 빈 상태는 F와 R이 같은 것을 가리킨다는 점.
꽉 채웠을 때, R이 가리키는 위치의 앞부분을 F가 가리킨다는 점.
데이터를 넣을 때, R을 먼저 움직이고 데이터를 넣고, 이것은 데이터를 뺄 때도 F를 먼저 움직이고 데이터를 뺀다는 점입니다.
원형 큐의 구현

ArrayQueue.java
public class ArrayQueue<E> implements Queue<E> {

  private static final int INITIAL_CAPACITY = 100;

  private int front;
  private int rear;
  private int size;
  private Object[] queueArray;

  public ArrayQueue() {
    queueArray = new Object[INITIAL_CAPACITY];
  }

  @Override
  public int size() {
    return this.size;
  }

  @Override
  public boolean isEmpty() {
    return this.size == 0;
  }

  @Override
  public void enqueue(E data) {

  }

  @Override
  public E dequeue() {
    return null;
  }

  @Override
  public E peek() {
    return null;
  }
  
  private int nextIndex(int pos) {
    return pos == INITIAL_CAPACITY - 1 ? 0 : pos + 1;
  }
}
CircularQueue라고 책에는 쓰여있는데, 그냥 귀찮아서 ArrayQueue로 썼습니다.
참고하시길 바랍니다.
front와  rear는 초기화시에 위치가 0입니다. (같은 위치를 가리키므로)
size는 편의를 위해 넣었습니다.
마지막 인덱스를 반환하는 함수는 외부에서 구현 정도를 알 필요가 없으므로 테스트에서는 제외합니다.
배열 기반 Queue enqueue 메소드 구현

@Override
public void enqueue(E data) {
  if (nextIndex(this.rear) == this.front) { // 큐가 꽉 찬 경우(this.size == 100).
    return;
  }

  this.rear = nextIndex(this.rear);
  queueArray[this.rear] = data;
  this.size++;
}
사실 return이 아니라 Exception을 주는 편이 더 좋겠죠?
나머지 코드는 읽어보시면 이해가 가실거라고 생각합니다.
배열 기반 Queue dequeue 메소드 구현

@Override
public E dequeue() {
  if (isEmpty()) {
    throw new EmptyQueueException();
  }

  this.front = nextIndex(this.front);
  this.size--;
  return (E) queueArray[this.front];
}
이 역시 마찬가지로 읽어보시면 이해가 가실 것입니다.
배열 기반 Queue peek 메소드 구현

@Override
public E peek() {
  if (isEmpty()) {
    throw new EmptyQueueException();
  }

  return (E) queueArray[nextIndex(this.front)];
}
큐의 연결 리스트 기반 구현

큐는 연결리스트로 구현하면 훨씬 손쉽게 구현이 가능합니다.
연결 리스트 기반 큐 테스트 코드 작성하기

@Test
@DisplayName("연결_리스트_기반_큐_생성_테스트")
void 연결_리스트_기반_큐_생성_테스트() {
  Queue<Integer> queue = new LinkedListQueue<>();

  assertThat(queue).isNotNull();
  assertThat(queue.isEmpty()).isTrue();
  assertThat(queue.size()).isEqualTo(0);
}

@Test
@DisplayName("연결_리스트_기반_큐_생성_테스트")
void 연결_리스트_기반_큐_EmptyQueueException_테스트() {
  Queue<Integer> queue = new LinkedListQueue<>();

  assertThat(queue).isNotNull();
  assertThat(queue.isEmpty()).isTrue();
  assertThat(queue.size()).isEqualTo(0);
  assertThatThrownBy(queue::dequeue).isInstanceOf(EmptyQueueException.class);
  assertThatThrownBy(queue::peek).isInstanceOf(EmptyQueueException.class);
}

@Test
@DisplayName("연결_리스트_기반_큐_데이터_저장_테스트")
void 연결_리스트_기반_큐_데이터_저장_테스트() {
  Queue<Integer> queue = new LinkedListQueue<>();

  queue.enqueue(1);
  queue.enqueue(2);
  queue.enqueue(3);
  queue.enqueue(4);
  queue.enqueue(5);

  assertThat(queue).isNotNull();
  assertThat(queue.isEmpty()).isFalse();
  assertThat(queue.size()).isEqualTo(5);
}

@Test
@DisplayName("연결_리스트_기반_큐_데이터_저장_후_제거_테스트")
void 연결_리스트_기반_큐_데이터_저장_후_제거_테스트() {
  Queue<Integer> queue = new LinkedListQueue<>();

  queue.enqueue(1);
  queue.enqueue(2);
  queue.enqueue(3);
  queue.enqueue(4);
  queue.enqueue(5);

  assertThat(queue).isNotNull();
  assertThat(queue.isEmpty()).isFalse();
  assertThat(queue.size()).isEqualTo(5);
  assertThat(queue.peek()).isEqualTo(1);
  assertThat(queue.dequeue()).isEqualTo(1);
  assertThat(queue.size()).isEqualTo(4);
  assertThat(queue.peek()).isEqualTo(2);
  assertThat(queue.dequeue()).isEqualTo(2);
  assertThat(queue.size()).isEqualTo(3);
  assertThat(queue.peek()).isEqualTo(3);
  assertThat(queue.dequeue()).isEqualTo(3);
  assertThat(queue.size()).isEqualTo(2);
  assertThat(queue.peek()).isEqualTo(4);
  assertThat(queue.dequeue()).isEqualTo(4);
  assertThat(queue.size()).isEqualTo(1);
  assertThat(queue.peek()).isEqualTo(5);
  assertThat(queue.dequeue()).isEqualTo(5);
  assertThat(queue.isEmpty()).isTrue();
  assertThat(queue.size()).isEqualTo(0);
}
연결 리스트 기반 큐 구현하기

"큐는 enqueue와 dequeue가 이루어지는 위치가 다르다." 는 점을 꼭 염두에두고 코딩을 해야합니다.
LinkedListQueue.java
public class LinkedListQueue<E> implements Queue<E> {

  private int size;
  private Node<E> front;
  private Node<E> rear;

  @Override
  public int size() {
    return this.size;
  }

  @Override
  public boolean isEmpty() {
    return this.size == 0;
  }

  @Override
  public void enqueue(E data) {

  }

  @Override
  public E dequeue() {
    return null;
  }

  @Override
  public E peek() {
    return null;
  }

  private static class Node<T> {

    private T data;
    private Node<T> next;

    public Node(T data) {
      this.data = data;
    }
  }
}
front와 rear는 다른 위치를 가리킬 수 있도록 둘 다 참조로 선언하였습니다.
enqueue 메소드 구현하기

@Override
public void enqueue(E data) {
  Node<E> newNode = new Node<>(data);
  if (isEmpty()) {
    this.front = newNode;
  } else {
    this.rear.next = newNode;
  }
  this.rear = newNode;
  this.size++;
}
책이랑 조금 구현이 다른게, this.front를 직접 체크하기 보단 isEmpty를 사용해주는 편이 더 좋을 것 같아서 그렇게 작성했습니다.
dequeue 메소드 구현하기

@Override
public E dequeue() {
  if (isEmpty()) {
    throw new EmptyQueueException();
  }
  E retData = this.front.data;
  this.front = this.front.next;
  this.size--;

  return retData;
}
제일 헷갈렸던게, rear를 꼭 비워주지 않아도 될까? 라고 생각했는데, 필요없다시네요.
peek 메소드 구현하기

@Override
public E peek() {
  if (isEmpty()) {
    throw new EmptyQueueException();
  }

  return this.front.data;
}
덱(Deque)의 이해와 구현

시뮬레이션 예제는 굳이 봐야하나? 라는 생각이 들어서 일단 넘어갔습니다.
필요하면 따로 공부해보는 것이 좋을 것 같아요.
덱은 Double Ended Queue의 약자로 데크라도고 읽고 그렇습니다.
제일 큰 특징은 양 쪽 모두에서 넣고 뺄 수 있어서, Queue나 Stack으로도 사용이 가능하다는 점입니다.
파이썬에서는 리스트가 Stack과 Queue 연산을 모두 가지고 있지만, dequeue연산을 할 때 시간복잡도가 O(n)이 되는데, 이럴 때 dequeue 자료구조를 사용해서 최적화를 합니다.
덱의 이해와 ADT의 정의

덱의 설명은 위에서 했고 인터페이스만 정의해봅시다.
Deque.java
/**
 * Deque 자료구조의 ADT, 인터페이스
 *
 * @param <E> 데이터의 파라미터 타입
 * @author dion
 */
public interface Deque<E> {

  /**
   * 덱에 저장된 데이터의 개수를 반환합니다.
   *
   * @return 데이터의 개수
   */
  int size();

  /**
   * 덱이 비어있는지 여부를 반환합니다.
   *
   * @return 덱이 비어있으면 true, 그렇지 않으면 false
   */
  boolean isEmpty();

  /**
   * 덱의 앞부분에 데이터를 추가합니다.
   *
   * @param data 저장할 데이터
   */
  void addFirst(E data);

  /**
   * 덱의 뒷부분에 데이터를 추가합니다.
   *
   * @param data 저장할 데이터
   */
  void addLast(E data);

  /**
   * 덱의 앞부분에 위치한 데이터를 제거합니다.
   *
   * @return 덱의 앞부분에 위치했던 데이터
   */
  E removeFirst();

  /**
   * 덱의 뒷부분에 위치한 데이터를 제거합니다.
   *
   * @return 덱의 뒷부분에 위치했던 데이터
   */
  E removeLast();

  /**
   * 덱의 앞부분에 위치한 데이터를 반환합니다.
   *
   * @return 덱의 앞부분에 위치한 데이터
   */
  E getFirst();

  /**
   * 덱의 뒷부분에 위치한 데이터를 반환합니다.
   *
   * @return 덱의 뒷부분에 위치한 데이터
   */
  E getLast();
}
덱 테스트 코드 작성

DequeTest.java
class DequeTest {

  @Test
  @DisplayName("덱의_생성_및_초기화_테스트")
  void 덱의_생성_및_초기화_테스트() {
    Deque<Integer> deque = new LinkedListDeque<>();

    assertThat(deque).isNotNull();
    assertThat(deque.size()).isEqualTo(0);
    assertThat(deque.isEmpty()).isTrue();
  }

  @Test
  @DisplayName("덱에_데이터_삽입_테스트")
  void 덱에_데이터_삽입_테스트() {
    Deque<Integer> deque = new LinkedListDeque<>();

    deque.addFirst(3);
    deque.addFirst(2);
    deque.addFirst(1);
    deque.addLast(4);
    deque.addLast(5);
    deque.addLast(6);

    assertThat(deque).isNotNull();
    assertThat(deque.size()).isEqualTo(6);
    assertThat(deque.isEmpty()).isFalse();
  }

  @Test
  @DisplayName("덱에_데이터_삽입_앞에서_삭제_테스트")
  void 덱에_데이터_삽입_앞에서_삭제_테스트() {
    Deque<Integer> deque = new LinkedListDeque<>();

    deque.addFirst(3);
    deque.addFirst(2);
    deque.addFirst(1);
    deque.addLast(4);
    deque.addLast(5);
    deque.addLast(6);

    assertThat(deque).isNotNull();
    assertThat(deque.size()).isEqualTo(6);
    assertThat(deque.isEmpty()).isFalse();
    assertThat(deque.getFirst()).isEqualTo(1);
    assertThat(deque.getLast()).isEqualTo(6);
    assertThat(deque.removeFirst()).isEqualTo(1);
    assertThat(deque.size()).isEqualTo(5);
    assertThat(deque.getFirst()).isEqualTo(2);
    assertThat(deque.getLast()).isEqualTo(6);
    assertThat(deque.removeFirst()).isEqualTo(2);
    assertThat(deque.size()).isEqualTo(4);
    assertThat(deque.getFirst()).isEqualTo(3);
    assertThat(deque.getLast()).isEqualTo(6);
    assertThat(deque.removeFirst()).isEqualTo(3);
    assertThat(deque.size()).isEqualTo(3);
    assertThat(deque.getFirst()).isEqualTo(4);
    assertThat(deque.getLast()).isEqualTo(6);
    assertThat(deque.removeFirst()).isEqualTo(4);
    assertThat(deque.size()).isEqualTo(2);
    assertThat(deque.getFirst()).isEqualTo(5);
    assertThat(deque.getLast()).isEqualTo(6);
    assertThat(deque.removeFirst()).isEqualTo(5);
    assertThat(deque.size()).isEqualTo(1);
    assertThat(deque.getFirst()).isEqualTo(6);
    assertThat(deque.getLast()).isEqualTo(6);
    assertThat(deque.removeFirst()).isEqualTo(6);
    assertThat(deque.size()).isEqualTo(0);
    assertThat(deque.isEmpty()).isTrue();
  }

  @Test
  @DisplayName("덱에_데이터_삽입_뒤에서_삭제_테스트")
  void 덱에_데이터_삽입_뒤에서_삭제_테스트() {
    Deque<Integer> deque = new LinkedListDeque<>();

    deque.addFirst(3);
    deque.addFirst(2);
    deque.addFirst(1);
    deque.addLast(4);
    deque.addLast(5);
    deque.addLast(6);

    assertThat(deque).isNotNull();
    assertThat(deque.size()).isEqualTo(6);
    assertThat(deque.isEmpty()).isFalse();
    assertThat(deque.getFirst()).isEqualTo(1);
    assertThat(deque.getLast()).isEqualTo(6);
    assertThat(deque.removeLast()).isEqualTo(6);
    assertThat(deque.size()).isEqualTo(5);
    assertThat(deque.getFirst()).isEqualTo(1);
    assertThat(deque.getLast()).isEqualTo(5);
    assertThat(deque.removeLast()).isEqualTo(5);
    assertThat(deque.size()).isEqualTo(4);
    assertThat(deque.getFirst()).isEqualTo(1);
    assertThat(deque.getLast()).isEqualTo(4);
    assertThat(deque.removeLast()).isEqualTo(4);
    assertThat(deque.size()).isEqualTo(3);
    assertThat(deque.getFirst()).isEqualTo(1);
    assertThat(deque.getLast()).isEqualTo(3);
    assertThat(deque.removeLast()).isEqualTo(3);
    assertThat(deque.size()).isEqualTo(2);
    assertThat(deque.getFirst()).isEqualTo(1);
    assertThat(deque.getLast()).isEqualTo(2);
    assertThat(deque.removeLast()).isEqualTo(2);
    assertThat(deque.size()).isEqualTo(1);
    assertThat(deque.getFirst()).isEqualTo(1);
    assertThat(deque.getLast()).isEqualTo(1);
    assertThat(deque.removeLast()).isEqualTo(1);
    assertThat(deque.size()).isEqualTo(0);
    assertThat(deque.isEmpty()).isTrue();
  }

  @Test
  @DisplayName("덱이_비어있을_때_예외_처리_테스트")
  void 덱이_비어있을_때_예외_처리_테스트() {
    Deque<Integer> deque = new LinkedListDeque<>();

    assertThat(deque).isNotNull();
    assertThat(deque.size()).isEqualTo(0);
    assertThat(deque.isEmpty()).isTrue();
    assertThatThrownBy(deque::getFirst).isInstanceOf(EmptyDequeException.class);
    assertThatThrownBy(deque::removeFirst).isInstanceOf(EmptyDequeException.class);
    assertThatThrownBy(deque::getLast).isInstanceOf(EmptyDequeException.class);
    assertThatThrownBy(deque::removeLast).isInstanceOf(EmptyDequeException.class);
  }
}
예외 클래스 작성

EmptyDequeException.java
public class EmptyDequeException extends RuntimeException {

  public EmptyDequeException() {
    super("Deque is Emtpy.");
  }
}
Deque 구현하기

LinkedListDeque.java
public class LinkedListDeque<E> implements Deque<E> {

  private int size;
  private Node<E> head;
  private Node<E> tail;

  @Override
  public int size() {
    return this.size;
  }

  @Override
  public boolean isEmpty() {
    return this.size == 0;
  }

  @Override
  public void addFirst(E data) {

  }

  @Override
  public void addLast(E data) {

  }

  @Override
  public E removeFirst() {
    return null;
  }

  @Override
  public E removeLast() {
    return null;
  }

  @Override
  public E getFirst() {
    return null;
  }

  @Override
  public E getLast() {
    return null;
  }

  private static class Node<T> {

    private T data;
    private Node<T> next;
    private Node<T> prev;

    public Node(T data) {
      this.data = data;
    }
  }
}
양방향 연결리스트와 거의 동일한 구조입니다.
추가 기능 구현하기

LinkedListDeque.java
@Override
public void addFirst(E data) {
  Node<E> newNode = new Node<>(data);
  if (isEmpty()) {
    this.tail = newNode;
  } else {
    this.head.prev = newNode;
  }

  newNode.next = this.head;
  this.head = newNode;
  this.size++;
}

@Override
public void addLast(E data) {
  Node<E> newNode = new Node<>(data);
  if (isEmpty()) {
    this.head = newNode;
  } else {
    this.tail.next = newNode;
  }

  newNode.prev = this.tail;
  this.tail = newNode;
  this.size++;
}
first는 head에 last는 tail에 넣는 과정입니다.
맨 먼저 노드를 생성하고, 이에 대한 처리로직은 비슷합니다.
코드를 보시고 충분히 이해하실 수 있는 부분인 것 같아요.
삭제, 조회 기능 구현하기

@Override
public E removeFirst() {
  if (isEmpty()) {
    throw new EmptyDequeException();
  }

  E data = this.head.data;
  this.head = this.head.next;
  this.size--;
  return data;
}

@Override
public E removeLast() {
  if (isEmpty()) {
    throw new EmptyDequeException();
  }

  E data = this.tail.data;
  this.tail = this.tail.prev;
  this.size--;
  return data;
}

@Override
public E getFirst() {
  if (isEmpty()) {
    throw new EmptyDequeException();
  }

  return this.head.data;
}

@Override
public E getLast() {
  if (isEmpty()) {
    throw new EmptyDequeException();
  }

  return this.tail.data;
}
삭제 로직도 어려움이 없는 편입니다.
조회는 아주 간단하게 구현이 가능했습니다.
트리(Tree)

드디어 트리네요. 트리는 좀 다르기 때문에 또 학습이 어려워질 수 있을 것 같습니다. 그래도 화이팅!
트리의 개요

트리는 대표적인 비선형 자료구조입니다. 보통 그래프의 일종이라고 하는데, 둘의 특성이 너무 다르고, 트리쪽이 훨씬 이해하기 쉬워서 트리를 먼저 배우나봅니다.
트리의 접근

트리는 계층적 관계를 표현하는 자료구조 입니다.
여기서 윤성우 아저씨께서 자료구조는 표현에 초점이 맞춰져 있다고 하니, 트리는 아마도 삭제하는 기능같은 것은 없나봅니다.
트리가 표현할 수 있는 것들

제일 대표적인 예는 역시 디렉토리 인 것 같습니다.
트리는 거꾸로 뒤집어진 나무를 생각하면 되고, 그래서 최상단 노드를 root라고 하는 것입니다.
트리 관련 용어

용어 관련해서 코딩테스트에서 문제가 나오는 경우가 많으므로, 영어로 된 용어도 기억해두는게 좋을 것 같습니다.
이진 트리(Binary Tree)와 서브 트리(Sub Tree)

이진 트리라는 것 자체가 재귀를 표현하기 좋다보니 정의도 재귀를 썼네요.

포화 이진 트리: 모든 레벨이 꽉 찬 이진트리
완전 이진 트리: 모든 레벨이 꽉 찬 상태는 아니지만, 차곡차곡 빈 틈 없이 노드가 채워진 이진 트리

보통의 트리는 위에서 아래, 왼쪽에서 오른쪽 순으로 판단합니다.
이진 트리의 구현

이진 트리의 ADT 작성

BinaryTreeNode.java
/**
 * Tree 자료구조의 ADT, 인터페이스이자 Node의 인터페이스
 *
 * @param <E> 데이터의 파라미터 타입
 * @author dion
 */
public interface BinaryTreeNode<E> {

  /**
   * 해당 노드에 저장된 데이터를 반환합니다.
   *
   * @return 저장된 데이터
   */
  E getData();

  /**
   * 해당 노드의 왼쪽 서브트리를 반환합니다.
   *
   * @return 왼쪽 서브트리
   */
  BinaryTreeNode<E> getLeftSubTree();

  /**
   * 왼쪽 서브트리를 등록합니다.
   *
   * @param subTree 대상이 될 노드
   */
  void setLeftSubTree(BinaryTreeNode<E> subTree);

  /**
   * 해당 노드의 오른쪽 서브트리를 반환합니다.
   *
   * @return 오른쪽 서브트리
   */
  BinaryTreeNode<E> getRightSubTree();

  /**
   * 오른쪽 서브트리를 등록합니다.
   *
   * @param subTree 대상이 될 노드
   */
  void setRightSubTree(BinaryTreeNode<E> subTree);
}
이진 트리 테스트 코드 작성

BinaryTreeNodeTest.java
class BinaryTreeNodeTest {

  @Test
  @DisplayName("이진_트리_생성_및_초기화_테스트")
  void 이진_트리_생성_및_초기화_테스트() {
    BinaryTreeNode<Integer> bt = new BinaryTreeNodeImpl<>(1);

    assertThat(bt).isNotNull();
    assertThat(bt.getData()).isEqualTo(1);
    assertThat(bt.getLeftSubTree()).isNull();
    assertThat(bt.getRightSubTree()).isNull();
  }

  @Test
  @DisplayName("이진_트리_저장_및_출력_테스트")
  void 이진_트리_저장_및_출력_테스트() {
    BinaryTreeNode<Integer> bt1 = new BinaryTreeNodeImpl<>(1);
    BinaryTreeNode<Integer> bt2 = new BinaryTreeNodeImpl<>(2);
    BinaryTreeNode<Integer> bt3 = new BinaryTreeNodeImpl<>(3);
    BinaryTreeNode<Integer> bt4 = new BinaryTreeNodeImpl<>(4);

    bt1.setLeftSubTree(bt2);
    bt1.setRightSubTree(bt3);
    bt2.setLeftSubTree(bt4);

    assertThat(bt1).isNotNull();
    assertThat(bt2).isNotNull();
    assertThat(bt3).isNotNull();
    assertThat(bt4).isNotNull();
    assertThat(bt1.getData()).isEqualTo(1);
    assertThat(bt2.getData()).isEqualTo(2);
    assertThat(bt3.getData()).isEqualTo(3);
    assertThat(bt4.getData()).isEqualTo(4);
    assertThat(bt1.getLeftSubTree().getData()).isEqualTo(2);
    assertThat(bt1.getRightSubTree().getData()).isEqualTo(3);
    assertThat(bt1.getLeftSubTree().getLeftSubTree().getData()).isEqualTo(4);
    assertThat(bt1.getLeftSubTree().getRightSubTree()).isNull();
  }
}
이진 트리 구현

BinaryTreeNode.java
public class BinaryTreeNodeImpl<E> implements BinaryTreeNode<E> {

  private final E data;
  private BinaryTreeNode<E> left;
  private BinaryTreeNode<E> right;

  public BinaryTreeNodeImpl(E data) {
    this.data = data;
  }

  @Override
  public E getData() {
    return this.data;
  }

  @Override
  public BinaryTreeNode<E> getLeftSubTree() {
    return this.left;
  }

  @Override
  public void setLeftSubTree(BinaryTreeNode<E> subTree) {
    this.left = subTree;
  }

  @Override
  public BinaryTreeNode<E> getRightSubTree() {
    return this.right;
  }

  @Override
  public void setRightSubTree(BinaryTreeNode<E> subTree) {
    this.right = subTree;
  }
}
로직이랄게 따로 없습니다.
심지어 GC가 존재하는 자바는 메모리 관련 로직도 없어 한 눈에 들어오는 모습입니다.
이진 트리의 순회(Traversal)

재귀의 대표적인 사례라고 할 수 있겠습니다.
전위 중위 후위 모두 재귀로 이뤄지게 됩니다.
그리고 그 기준은 루트노드입니다.
순회가 가능한 트리 ADT 정의

TraversableBinaryTreeNode.java
/**
 * 순회한 정보를 반환할 수 있는 이진 트리
 *
 * @param <E> 파라미터 타입
 */
public interface TraversableBinaryTreeNode<E> {

  /**
   * 해당 노드에 저장된 데이터를 반환합니다.
   *
   * @return 저장된 데이터
   */
  E getData();

  /**
   * 해당 노드의 왼쪽 서브트리를 반환합니다.
   *
   * @return 왼쪽 서브트리
   */
  TraversableBinaryTreeNode<E> getLeftSubTree();

  /**
   * 왼쪽 서브트리를 등록합니다.
   *
   * @param subTree 대상이 될 노드
   */
  void setLeftSubTree(TraversableBinaryTreeNode<E> subTree);

  /**
   * 해당 노드의 오른쪽 서브트리를 반환합니다.
   *
   * @return 오른쪽 서브트리
   */
  TraversableBinaryTreeNode<E> getRightSubTree();

  /**
   * 오른쪽 서브트리를 등록합니다.
   *
   * @param subTree 대상이 될 노드
   */
  void setRightSubTree(TraversableBinaryTreeNode<E> subTree);

  /**
   * 전위 순회한 정보를 StringBuilder에 저장합니다.
   */
  void preorderTraverse(StringBuilder sb);

  /**
   * 중위 순회한 정보를 StringBuilder에 저장합니다.
   */
  void inorderTraverse(StringBuilder sb);

  /**
   * 후위 순회한 정보를 StringBuilder에 저장합니다.
   */
  void postorderTraverse(StringBuilder sb);
}
C언어에는 함수 포인터가 존재해서 함수를 넘길 수 있는데, Java는 그런면에서 애매한 부분이 있네요.
BinaryTreeNode의 확장된 버전이라고 생각하시면 될 것 같습니다.
순회가 가능한 트리 테스트 코드 작성

TraversableBinaryTreeNodeTest.java
class TraversableBinaryTreeNodeTest {

  @Test
  @DisplayName("순회_가능한_이진_트리_생성_및_초기화_테스트")
  void 순회_가능한_이진_트리_생성_및_초기화_테스트() {
    TraversableBinaryTreeNode<Integer> bt = new TraversableBinaryTreeNodeImpl<>(1);

    assertThat(bt).isNotNull();
    assertThat(bt.getData()).isEqualTo(1);
    assertThat(bt.getLeftSubTree()).isNull();
    assertThat(bt.getRightSubTree()).isNull();
  }

  @Test
  @DisplayName("순회_가능한_이진_트리_저장_및_출력_테스트")
  void 순회_가능한_이진_트리_저장_및_출력_테스트() {
    TraversableBinaryTreeNode<Integer> bt1 = new TraversableBinaryTreeNodeImpl<>(1);
    TraversableBinaryTreeNode<Integer> bt2 = new TraversableBinaryTreeNodeImpl<>(2);
    TraversableBinaryTreeNode<Integer> bt3 = new TraversableBinaryTreeNodeImpl<>(3);
    TraversableBinaryTreeNode<Integer> bt4 = new TraversableBinaryTreeNodeImpl<>(4);

    bt1.setLeftSubTree(bt2);
    bt1.setRightSubTree(bt3);
    bt2.setLeftSubTree(bt4);

    assertThat(bt1).isNotNull();
    assertThat(bt2).isNotNull();
    assertThat(bt3).isNotNull();
    assertThat(bt4).isNotNull();
    assertThat(bt1.getData()).isEqualTo(1);
    assertThat(bt2.getData()).isEqualTo(2);
    assertThat(bt3.getData()).isEqualTo(3);
    assertThat(bt4.getData()).isEqualTo(4);
    assertThat(bt1.getLeftSubTree().getData()).isEqualTo(2);
    assertThat(bt1.getRightSubTree().getData()).isEqualTo(3);
    assertThat(bt1.getLeftSubTree().getLeftSubTree().getData()).isEqualTo(4);
    assertThat(bt1.getLeftSubTree().getRightSubTree()).isNull();
  }

  @Test
  @DisplayName("순회_가능한_이진_트리_전위_순회_테스트")
  void 순회_가능한_이진_트리_전위_순회_테스트() {
    TraversableBinaryTreeNode<Integer> bt1 = new TraversableBinaryTreeNodeImpl<>(1);
    TraversableBinaryTreeNode<Integer> bt2 = new TraversableBinaryTreeNodeImpl<>(2);
    TraversableBinaryTreeNode<Integer> bt3 = new TraversableBinaryTreeNodeImpl<>(3);
    TraversableBinaryTreeNode<Integer> bt4 = new TraversableBinaryTreeNodeImpl<>(4);

    bt1.setLeftSubTree(bt2);
    bt1.setRightSubTree(bt3);
    bt2.setLeftSubTree(bt4);

    String expected = "1243";
    StringBuilder sb = new StringBuilder();
    bt1.preorderTraverse(sb);

    assertThat(sb.toString()).isEqualTo(expected);
  }

  @Test
  @DisplayName("순회_가능한_이진_트리_중위_순회_테스트")
  void 순회_가능한_이진_트리_중위_순회_테스트() {
    TraversableBinaryTreeNode<Integer> bt1 = new TraversableBinaryTreeNodeImpl<>(1);
    TraversableBinaryTreeNode<Integer> bt2 = new TraversableBinaryTreeNodeImpl<>(2);
    TraversableBinaryTreeNode<Integer> bt3 = new TraversableBinaryTreeNodeImpl<>(3);
    TraversableBinaryTreeNode<Integer> bt4 = new TraversableBinaryTreeNodeImpl<>(4);

    bt1.setLeftSubTree(bt2);
    bt1.setRightSubTree(bt3);
    bt2.setLeftSubTree(bt4);

    String expected = "4213";
    StringBuilder sb = new StringBuilder();
    bt1.inorderTraverse(sb);

    assertThat(sb.toString()).isEqualTo(expected);
  }

  @Test
  @DisplayName("순회_가능한_이진_트리_후위_순회_테스트")
  void 순회_가능한_이진_트리_후위_순회_테스트() {
    TraversableBinaryTreeNode<Integer> bt1 = new TraversableBinaryTreeNodeImpl<>(1);
    TraversableBinaryTreeNode<Integer> bt2 = new TraversableBinaryTreeNodeImpl<>(2);
    TraversableBinaryTreeNode<Integer> bt3 = new TraversableBinaryTreeNodeImpl<>(3);
    TraversableBinaryTreeNode<Integer> bt4 = new TraversableBinaryTreeNodeImpl<>(4);

    bt1.setLeftSubTree(bt2);
    bt1.setRightSubTree(bt3);
    bt2.setLeftSubTree(bt4);

    String expected = "4231";
    StringBuilder sb = new StringBuilder();
    bt1.postorderTraverse(sb);

    assertThat(sb.toString()).isEqualTo(expected);
  }
}
순회 기능 구현

재귀적으로 풀고 싶었는데, static method가 아니면 해결이 안되겠다 싶어서 가능한 선에서 구현하였습니다.
@Override
public void preorderTraverse(StringBuilder sb) {
  sb.append(this.data.toString());
  if (this.left != null) {
    this.left.preorderTraverse(sb);
  }
  if (this.right != null) {
    this.right.preorderTraverse(sb);
  }
}

@Override
public void inorderTraverse(StringBuilder sb) {
  if (this.left != null) {
    this.left.inorderTraverse(sb);
  }
  sb.append(this.data.toString());
  if (this.right != null) {
    this.right.inorderTraverse(sb);
  }
}

@Override
public void postorderTraverse(StringBuilder sb) {
  if (this.left != null) {
    this.left.postorderTraverse(sb);
  }
  if (this.right != null) {
    this.right.postorderTraverse(sb);
  }
  sb.append(this.data.toString());
}
수식 트리(Expression Tree)의 구현

처음 들어보는 트리네요.
수식 트리의 이해

이진 트리를 이용해서 수식을 표현한 것
수식 트리의 인터페이스 작성

ExpressionTree.java
/**
 * 수식 트리 인터페이스
 */
public interface ExpressionTree {

  /**
   * 트리의 값을 계산합니다.
   *
   * @return 트리를 가지고 연산한 값
   */
  int evaluateTree();

  /**
   * 전위 표기법으로 표현합니다.
   *
   * @param sb 표기법이 저장될 공간
   */
  void prefixTypeExpression(StringBuilder sb);

  /**
   * 중위 표기법으로 표현합니다.
   *
   * @param sb 표기법이 저장될 공간
   */
  void infixTypeExpression(StringBuilder sb);

  /**
   * 후위 표기법으로 표현합니다.
   *
   * @param sb 표기법이 저장될 공간
   */
  void postfixTypeExpression(StringBuilder sb);
}
수식 트리의 테스트 코드 작성

ExpressionTreeTest.java
class ExpressionTreeTest {

  InfixToPostfix infixToPostfix;

  @BeforeEach
  void setUp() {
    infixToPostfix = new InfixToPostfix();
  }

  @Test
  @DisplayName("수식_트리_테스트")
  void 수식_트리_테스트() {
    String infixExpression = "1 + 2";
    char[] postfixExpression = infixToPostfix.convertInputToPostfix(infixExpression);

    ExpressionTree expressionTree = new ExpressionTreeImpl(postfixExpression);
    assertThat(expressionTree.evaluateTree()).isEqualTo(3);

    StringBuilder sb = new StringBuilder();
    expressionTree.prefixTypeExpression(sb);
    assertThat(sb.toString()).isEqualTo("+12");

    sb = new StringBuilder();
    expressionTree.infixTypeExpression(sb);
    assertThat(sb.toString()).isEqualTo("1+2");

    sb = new StringBuilder();
    expressionTree.postfixTypeExpression(sb);
    assertThat(sb.toString()).isEqualTo("12+");
  }

  @Test
  @DisplayName("수식_트리_테스트2")
  void 수식_트리_테스트2() {
    String infixExpression = "1 + 2 * 7";
    char[] postfixExpression = infixToPostfix.convertInputToPostfix(infixExpression);

    ExpressionTree expressionTree = new ExpressionTreeImpl(postfixExpression);
    assertThat(expressionTree.evaluateTree()).isEqualTo(15);

    StringBuilder sb = new StringBuilder();
    expressionTree.prefixTypeExpression(sb);
    assertThat(sb.toString()).isEqualTo("+1*27");

    sb = new StringBuilder();
    expressionTree.infixTypeExpression(sb);
    assertThat(sb.toString()).isEqualTo("1+2*7");

    sb = new StringBuilder();
    expressionTree.postfixTypeExpression(sb);
    assertThat(sb.toString()).isEqualTo("127*+");
  }
}
후위 표기법의 수식을 기반으로 수식 트리 구성하기

여기서 예로 든 코드가 너무 맘에 안들어서 공부가 좀 된 것 같기도 하네요.
ExpressionTreeImpl.java
public class ExpressionTreeImpl implements ExpressionTree {

  private TraversableBinaryTreeNode<Character> root;

  public ExpressionTreeImpl(char[] postfixExpression) {
    Stack<TraversableBinaryTreeNode<Character>> stack = new ListStack<>();

    for (char expr : postfixExpression) {
      TraversableBinaryTreeNode<Character> node = new TraversableBinaryTreeNodeImpl<>(expr);
      if (!Character.isDigit(expr)) { // 숫자가 아니라면, 연산자임
        node.setRightSubTree(stack.pop());
        node.setLeftSubTree(stack.pop());
      }

      stack.push(node);
    }

    this.root = stack.pop();
  }

  @Override
  public int evaluateTree() {
    return 0;
  }

  @Override
  public void prefixTypeExpression(StringBuilder sb) {

  }

  @Override
  public void infixTypeExpression(StringBuilder sb) {

  }

  @Override
  public void postfixTypeExpression(StringBuilder sb) {

  }
}
스택은 제네릭을 이용해서 순회 가능한 노드를 담도록 했습니다. 그리고 for each문을 활용했습니다.
if 문 하나로 충분히 가능한 부분이어서 위와 같이 처리했어요.
그리고 나서 해당 노드를 스택에 넣도록 했습니다.
마지막으로 초기화 과정이 끝날 때, root에 마지막으로 저장되어있던 트리를 넣습니다.
수식 트리의 순회

@Override
public void prefixTypeExpression(StringBuilder sb) {
  this.root.preorderTraverse(sb);
}

@Override
public void infixTypeExpression(StringBuilder sb) {
  this.root.inorderTraverse(sb);
}

@Override
public void postfixTypeExpression(StringBuilder sb) {
  this.root.postorderTraverse(sb);
}
참 쉽죠?
수식 트리의 계산

@Override
public int evaluateTree() {
  return evaluateTree(this.root);
}

private int evaluateTree(TraversableBinaryTreeNode<Character> node) {
  TraversableBinaryTreeNode<Character> leftSubTree = node.getLeftSubTree();
  TraversableBinaryTreeNode<Character> rightSubTree = node.getRightSubTree();

  if (leftSubTree == null && rightSubTree == null) {
    return Character.getNumericValue(node.getData()); // 단말 노드는 피연산자임
  }

  int op1 = 0;
  int op2 = 0;
  if (leftSubTree != null) {
    op1 = evaluateTree(leftSubTree);
  }
  if (rightSubTree != null) {
    op2 = evaluateTree(rightSubTree);
  }

  switch (node.getData()) {
    case '+':
      return op1 + op2;
    case '-':
      return op1 - op2;
    case '*':
      return op1 * op2;
    case '/':
      if (op2 == 0) {
        throw new ArithmeticException("Can't be division by zero.");
      }
      return op1 / op2;
  }

  return 0;
}
좀 코드가 더럽게 나왔는데, 예외처리 하느라 그렇게 됬네요...
일단 왼쪽 서브트리와 오른쪽 서브트리가  null인 경우엔 숫자값을 반환하도록 합니다.
노드가 연산자인 경우에만 왼쪽 오른쪽 노드가 존재할 것이므로 위의 로직이 성립합니다.
혹시 코드가 이해가 안가셨다면 책을 참고하면서 읽어보시면 좋을 듯합니다.