[Algorithm] Binary Tree

tngus2sh·2024년 9월 7일

algorithm

Algorithm

목록 보기

14/18

이진 트리

자식 노드가 최대 두개인 노드들로 구성된 트리

두 개의 자식 노드는 왼쪽 자식 노드, 오른쪽 자식 노드로 나눌 수 있다.

노드의 유한 집합으로서 공백이거나 루트와 두개의 분리된 이진트리인 경우 왼쪽 서브트리와 오른쪽 서브트리로 구성된다. (=자식을 최대 2개 가질 수 있다.)

종류

정 이진 트리(Full Binary Tree) : 각 노드가 0개 혹은 2개의 자식 노드를 갖는다.
완전 이진 트리(Complete Binary Tree) : 마지막 레벨을 제외한 모든 노드가 가득 차있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 한다.
포화 이진 트리(Perfect Binary Tree) : 정 이진트리이면서 완전 이진 트리인 경우이다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리
편향 이진 트리(Skewed Binary Tree) : 한쪽으로 편향된 모양의 트리

이진 탐색 트리(Binary Search Tree)

이진 탐색 + 연결 리스트를 결합한 이진 트리
최대 두 개인 자식 노드들로 구성되는 트리

이진 탐색의 효율적인 탐색 능력을 유지하면서 빈번한 자료 입력과 삭제를 가능하게끔 고안되었다.

특징

각 노드에 중복되지 않는 키(key)가 있다.
루트 노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다.
루트 노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다.
좌우 서브 트리도 모두 이진 탐색 트리여야 한다.

과정

1) 루트 노드의 키와 갖고자 하는 값을 비교, 만약 찾고자 하는 값이라면 탐색을 종료한다.
2) 찾고자 하는 값이 루트 노드의 키보다 작다면, 왼쪽 서브 트리로 탐색을 진행
3) 찾고자 하는 값이 루트 노드의 키보다 크다면 오른쪽 서브 트리로 탐색을 진행
4) 이 과정을 찾고자 하는 값을 찾을 때까지 반복해 진행한다.

구현

Binary Tree

// 이진 트리 구현
// 크기 상관 쓰지 않는 이진 트리

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

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

  Node (int value) {
    this.value = value;
    left = null;
    right = null;
  }
}

class BinaryTree {
  Node root;
  int size;

  BinaryTree() {
    root = null;
    size = 0;
  }

  void push(Node node) {
    if(size == 0) {
      this.root = node;
    } else {
      Queue<Node> q = new LinkedList<>();
      q.add(this.root);

      while (!q.isEmpty()) {
        Node curNode = q.poll();

        if(curNode.left == null) {
          curNode.left = node;
          break;
        }
        else {
          q.add(curNode.left);
        }

        if(curNode.right == null) {
          curNode.right = node;
          break;
        }
        else {
          q.add(curNode.right);
        }
      }
    }
    size++;
  }

  public int pop (Node node) {
    if (contain(node)) {
      Node lastNode = removeLastNode();

      if (root != null) {
        if (isSame(root, node)) {
          root.value = lastNode.value;
        }
        else {
          Queue<Node> q = new LinkedList<>();
          q.add(root);

          while (!q.isEmpty()) {
            Node curNode = q.poll();

            if(curNode.left != null) {
              if(isSame(curNode.left, node)) {
                curNode.left.value = lastNode.value;
                break;
              } else {
                q.add(curNode.left);
              }
            }

            if (curNode.right != null) {
              if (isSame(curNode.right, node)) {
                curNode.right.value = lastNode.value;;
                break;
              }
            }
          }
        }
      }
      size--;
      return 1;
    }
    return 0;
  }

  boolean contain(Node node) {
    boolean check = false;

    if (size != 0) {
      Queue<Node> q = new LinkedList<>();
      q.add(this.root);

      while (!q.isEmpty()) {
        Node curNode = q.poll();

        if (isSame(curNode, node)) {
          check = true;
          break;
        }

        if (curNode.left != null) {
          q.add(curNode.left);
        }
        if (curNode.right != null) {
          q.add(curNode.right);
        }
      }
    }
    return check;
  }

  // 해당 함수의 경우 마지막 리프 노드를 찾는 과정과 삭제 과정이 따로 동작한다. 그 이유는 리프 노드의 주소 값을 last에 넣어준다고 해도 트리에서 리프 노드를 삭제하기 위해선 리프 노드의 부모 노드가 필요 하기 때문이다.
  // 그래서 해당 부분을 이해 했으면 이 함수를 좀 더 최적화 하는 것이 가능해진다.
  // 그 방법은 Node 클래스에 멤버 변수로 Node parent를 생성해주고 이용하면 된다.
  private Node removeLastNode() {
    Node last = this.root;

    if(size == 1) {
      root = null;
    }
    else {
      Queue<Node> q = new LinkedList<>();
      q.add(last);

      while (!q.isEmpty()) {
        Node curNode = q.poll();
        last = curNode;

        if(curNode.left != null) {
          q.add(curNode.left);
        }

        if (curNode.right != null) {
          q.add(curNode.right);
        }
      }

      q.add(root);

      while (!q.isEmpty()) {
        Node curNode = q.poll();

        if (curNode.left != null) {
          if(isSame(curNode.left, last)) {
            curNode.left = null;
          } else {
            q.add(curNode.left);
          }
        }

        if (curNode.right != null) {
          if (isSame(curNode.right, last)) {
            curNode.right = null;
            break;
          } else {
            q.add(curNode.right);
          }
        }
      }
    }
    return last;
  }

  private boolean isSame(Node a, Node b) {
    if(a.value == b.value && a.left == b.left && a.right == b.right) {
      return true;
    }
    return false;
  }

  void printBFS(Node node) {

    Queue<Node> q = new LinkedList<>();
    q.add(node);

    while (!q.isEmpty()) {
      Node curNode = q.poll();
      System.out.println(curNode.value);

      if (curNode.left != null) {
        q.add(curNode.left);
      }

      if (curNode.right != null) {
        q.add(curNode.right);
      }
    }
  }

  void printDFS(Node curNode) {

    if (curNode.left == null && curNode.right == null) {
      System.out.println(curNode.value);
    } else {
      if (curNode.left != null) {
        printDFS(curNode.left);
      }
      System.out.println(curNode.value);
      if (curNode.right != null) {
        printDFS(curNode.right);
      }
    }
  }
}

public class Main {
}
/**
 * 참고한 사이트
 * [[Data Structure] Java 이진트리(Binary Tree) 구현](https://math-coding.tistory.com/164)
 */

Binary Search Tree - Generic

import java.util.Comparator;

class Node<E> {
  E value;

  /*
   *  부모 노드는 BinarySearchTree에서는 당장 쓰이진 않으나
   *  추후 용이하게 쓰이니 미리 부모노드를 가르키는 변수도 같이
   *  구현하면서 익숙해지는 거이 좋다.
   */

  Node<E> left;
  Node<E> right;
  Node<E> parent;

  Node(E value) {
    this(value, null);
  }

  Node(E value, Node<E> parent) {
    this.value = value;
    this.parent = parent;
    this.right = null;
    this.left = null;
  }
}

class BinarySearchTree<E> {
  private Node<E> root;   // 루트(최상단) 노드
  private int size;       // 요소(노드)의 개수

  private final Comparator<? super E> comparator;

  BinarySearchTree() {
    this(null);
  }

  BinarySearchTree(Comparator<? super E> comparator) {
    this.comparator = comparator;
    this.root = null;
    this.size = 0;
  }

  /**
   * Binary Search Tree에 삽입하는 메소드
   *
   * @param value 삽입하고자 하는 데이터
   * @return 정상적으로 삽입 되었을 경우 true, 중복 원소를 삽입할 경우 false를 반환
   */
  boolean add(E value) {

    /*
     * Comparator(사용자 지정 비교기)가 없을 경우(=null)에는 comparable,
     * 있을 경우에는 Comparator를 사용하는 메소드로 보낸다.
     * 그리고, 각 메소드는 정상적으로 삽입이 완료되었다면 null을 반환할 것이고,
     * 중복 원소를 삽입 할 경우 해당 value를 반환할 것이기 때문에
     * 비교 연산으로 null인지 아닌지 여부를 반환한다.
     */
    if(comparator == null) {
      return addUsingComparble(value) == null;
    }
    return addUsingComparator(value, comparator) == null;
  }

  // Comparable을 이용한 add메소드
  private E addUsingComparble(E value) {
    Node<E> current = root; // 탐색할 노드를 가르키는 current node

    // 만약 current가 null, 즉 root가 null이면 root에 새 노드를 만들고 null반환
    if(current == null) {
      root = new Node<E>(value);
      size++;
      return null;
    }

    Node<E> currentParent;    // current의 직전 탐색 노드를 가르키는 노드

    // 삽입 할 노드가 비교 될 수 있도록 한 변수를 만든다.
    @SuppressWarnings("unchecked")
    Comparable<? super E> compValue = (Comparable<? super E>) value;

    int compResult; // 비교 결과(양수, 0, 음수)를 담고 있을 변수

    do {
      // 다음 순회에서 curent의 부모노드를 가리킬 수 있도록 현재 current를 저장
      currentParent = current;

      compResult = compValue.compareTo(current.value);

      /*
       * 비교 결과 value가 current.value 보다 작으면
       * current를 current의 왼쪽 자식으로 갱신하고,
       * value보다 current.value가 크다면 current를 오른쪽
       * 자식으로 갱신하며, 같을 경우 순회를 중단하고 value를 반환한다.
       */
      if(compResult < 0) {
        current = current.left;
      } else if(compResult > 0) {
        current = current.right;
      }
      else {
        return value;
      }
    } while (current != null);

    // 순회가 완료되어 삽입해야 할 위치를 찾았다면 삽입 할 value를 노드로 만든다.
    Node<E> newNode = new Node<>(value, currentParent);

    // 직전 비교 결과에 따라 currentParent의 오른쪽 혹은 왼쪽 노드에 새 노드를 연결해준다.
    if(compResult < 0) {
      currentParent.left = newNode;
    }
    else {
      currentParent.right = newNode;
    }

    size++;
    return null;
  }

  // Comparator을 이용한 add
  private E addUsingComparator(E value, Comparator<? super E> comp) {

    Node<E> current = root;
    if(current == null) {
      root = new Node<>(value, null);
      size++;
      return null;
    }

    Node<E> currentParent;
    int compResult;
    do {
      currentParent = current;
      compResult = comp.compare(value, current.value);
      if(compResult < 0) {
        current = current.left;
      }
      else if(compResult > 0) {
        current = current.right;
      }
      else {
        return value;
      }
    } while (current != null);

    Node<E> newNode = new Node<>(value, currentParent);

    if(compResult < 0) {
      currentParent.left = newNode;
    }
    else {
      currentParent.right = newNode;
    }
    size++;
    return null;
  }

  /**
   * 삭제되는 노드의 자리를 대체할 노드(후계자)를 찾는 메소드
   * (오른쪽 자식 노드 중 가장 작은 노드를 찾음)
   *
   * @param node 삭제되는 노드(=대체되어야 할 노드)
   * @return 대체할 노드
   */
  private Node<E> getSuccessorAndUnlink(Node<E> node) {

    Node<E> currentParent = node; // 대체 할 노드의 부모노드를 가리키는 노드
    Node<E> current = node.right; // 초기에 오른쪽 자식 노드를 가리키도록 한다.

    /**
     * 처음 탐색하게되는 오른쪽 자식 노드(current)에서
     * current의 왼쪽 자식이 없다는 것은 current 노드,
     * 즉 오른쪽 첫 자식노드가 대체되는 노드가 된다는 것이다.
     *
     * 그렇기 때문에 대체해야하는 노드는 삭제되는 노드의 오른쪽 자식이 되며
     * 이에 대체되는 노드 자리(currentParent)의 오른쪽 자식은
     * current의 값이 반환되고, 상위 메소드에서 currentParent자리에
     * 값이 대체되게 된다.
     */

    if (current.left == null) {
      currentParent.right = current.right;
      if(currentParent.right != null) {
        currentParent.right.parent = currentParent;
      }
      current.right = null;
      return current;
    }

    // 가장 작은 노드를 찾을 때 까지 반복한다.
    while (current.left != null) {
      currentParent = current;
      current = current.left;
    }

    /*
     * 만약 후계자가 될 노드(가장 작은 노드)의 오른쪽 노드가 존재한다면
     * currentParent의 왼쪽 자식노드는 오른쪽 자식노드와 연결되어야 한다.
     *
     * 만약 current.right = null 이라면
     * 후계자가 될 노드의 자식노드는 존재하지 않으므로 자연스럽게
     * 후계자 노드의 부모노드는 후계자가 다른 노드로 대체되러 가기 때문에
     * 후계자의 부모 노드의 왼쪽 자식 노드는 자연스럽게 null을 가리키게 된다.
     */
    currentParent.left = current.right;
    if(currentParent.left != null) {
      currentParent.left.parent = currentParent;
    }

    current.right = null;
    return current;
  }

  /**
   * 삭제 할 노드에 대해 삭제를 수행하는 메소드
   *
   * @param node 삭제 할 노드
   * @return 삭제 후 대체 되고 난 뒤의 해당 위치의 노드를 반환
   */
  private Node<E> deleteNode(Node<E> node) {
    if (node != null) {
      // 자식노드가 없을 경우
      if (node.left == null && node.right == null) {
        // 삭제하려는 노드가 root일 경우 root를 끊어버리고 종료한다.
        if (node == root) {
          root = null;
        }
        // 그 외에는 단말 노드이므로 해당 노드만 삭제한다.
        // 자연스럽게 node의 부모노드는 null을 참조하게 된다.
        else {
          node = null;
        }
        return null;
      }

      // 양쪽의 자식 노드가 모두 있을 경우
      if(node.left != null && node.right != null) {
        // 대체 노드를 찾아온다. (앞선 만들었던 후계자를 찾는 메소드)
        Node<E> replacement = getSuccessorAndUnlink(node);

        // 삭제 된 노드에 대체 노드의 값을 대체해준다.
        node.value = replacement.value;
      }
      // 왼쪽 노드만 존재할 경우
      else if (node.left != null) {
        /*
         *  삭제할 노드가 root일 경우 왼쪽자식 노드(대체되는 노드)를
         *  삭제할 노드로 옮긴 다음 root를 대체노드를 가리키도록 변경한다.
         */
        if (node == root) {
          node = node.left;
          root = node;
          root.parent = null;
        } else {
          node = node.left;
        }
      }
      // 오른쪽 노드만 존재할 경우
      else {
        /*
         *  삭제할 노드가 root일 경우 오른쪽자식 노드(대체되는 노드)를
         *  삭제할 노드로 옮긴 다음 root를 대체노드를 가리키도록 변경한다.
         */
        if (node == root) {
          node = node.right;
          root = node;
          root.parent = null;
        } else {
          node = node.right;
        }
      }
    }
    return node;
  }

  /**
   * 삭제 메소드
   * @param o 삭제할 값
   * @return 삭제 된 노드의 value 값 혹은 매칭 값이 없을 경우 null을 반환한다.
   */

  public E remove(Object o) {

    if (root == null) {
      return null;
    }
    if (comparator == null) {
      return removeUsingComparable(o);
    } else {
      return removeUsingComparator(o, comparator);
    }
  }

  /**
   * Comparable을 이용한 데이터 삭제
   *
   * @param value 삭제하고자 하는 데이터
   * @return 정상적으로 삭제되었을 경우 value를 반환하나, 삭제할 노드가 없을 경우 null을 반환한다.
   */
  private E removeUsingComparable(Object value) {
    @SuppressWarnings("unchecked")
    E oldValue = (E) value;
    Node<E> parent = null, current = root;
    // 삭제하고자 하는 노드가 부모 노드로부터 왼쪽 자식 노드인지 오른쪽 자식 노드인지 알기 위한 변수
    boolean hasLeft = false;

    @SuppressWarnings("unchecked")
    Comparable<? super E> compValue = (Comparable<? super E>) value;

    // 삭제할 노드를 찾는다.
    do {
      int resComp = compValue.compareTo(current.value);

      // 삭제할 노드를 찾은 경우
      if(resComp == 0) {
        break;
      }

      parent = current;
      if (resComp < 0) {
        hasLeft = true;
        current = current.left;
      } else {
        hasLeft = false;
        current = current.right;
      }
    } while (current != null);

    // 만약 탐색 끝에 삭제해야할 노드를 차지 못했다면 null 반환
    if (current == null) {
      return null;
    }

    // 부모 노드가 없을 경우 == 삭제하는 노드가 root일 경우
    if (parent == null) {
      deleteNode(current);
      size--;
      return oldValue;
    }

    // 삭제 노드가 부모 노드의 왼쪽자식일 경우
    if (hasLeft) {
      parent.left = deleteNode(current);
      // 만약 새로 이어질 노드가 존재한다면, 해당 대체 노드의 부모 노드도 갱신
      if (parent.left != null) {
        parent.left.parent = parent;
      }
    }
    // 삭제 노드가 부모 노드의 오른쪽 자식일 경우
    else {
      parent.right = deleteNode(current);
      // 만약 새로 이어질 노드가 존재한다면, 해당 대체 노드의 부모 노드도 갱신
      if (parent.right != null) {
        parent.right.parent = parent;
      }
    }
    size--;
    return oldValue;
  }

  /**
   * Comparator을 이용한 데이터 삭제
   *
   * @param value 삭제하고자 하는 데이터
   * @return 정상적으로 삭제되었을 경우 value를 반환하나, 삭제할 노드가 없을경우 null을 반환한다.
   */

  private E removeUsingComparator(Object value, Comparator<? super E> comp) {

    @SuppressWarnings("unchecked")
    E oldValue = (E) value;
    Node<E> parent = null, current = root;
    boolean hasLeft = false;

    @SuppressWarnings("unchecked")
    E compValue = (E) value;

    do {
      int resComp = comp.compare(compValue, current.value);

      if(resComp == 0) {
        break;
      }

      parent = current;
      if (resComp < 0) {
        hasLeft = true;
        current = current.left;
      } else {
        hasLeft = false;
        current = current.right;
      }
    } while (current != null);

    if (current == null) {
      return null;
    }

    if (parent == null) {
      deleteNode(current);
      size--;
      return oldValue;
    }

    if (hasLeft) {
      parent.left = deleteNode(current);
      if (parent.left != null) {
        parent.left.parent = parent;
      }
    } else {
      parent.right = deleteNode(current);
      if (parent.right != null) {
        parent.right.parent = parent;
      }
    }
    size--;
    return oldValue;
  }

  /**
   * BinarySearchTree에 있는 원소의 개수를 반환해주는 메소드
   *
   * @return BinarySearchTree에 있는 원소의 개수를 반환
   */
  public int size() {
    return this.size;
  }

  /**
   * BinarySearchTree가 비어있는지를 판단하는 메소드
   *
   * @return BinarySearchTree가 비어있을 경우 true, 아닐 경우 false를 반환
   */
  public boolean isEmpty() {
    return size() == 0;
  }

  /**
   * 해당 객체가 BinarySearchTree에 존재하는지를 판단하는 메소드
   *
   * @param o 찾고자 하는 객체
   * @return 해당 객체가 존재 할 경우 true, 아닐 경우 false를 반환
   */
  public boolean contains(Object o) {
    // comparator가 null일 경우 Comparable로 비교하도록 한다.
    if (comparator == null) {
      return containsUsingComparable(o);
    }
    return containsUsingComparator(o, comparator);
  }

  /**
   * Comparable을 이용한 객체 존재 여부를 판단하는 메소드
   *
   * @param o 찾고자 하는 객체
   * @return 해당 객체가 존재 할 경우 true, 아닐 경우 false를 반환
   */
  private boolean containsUsingComparable(Object o) {

    // 비교 가능한 변수로 만든다.
    @SuppressWarnings("unchecked")
    Comparable<? super E> value = (Comparable<? super E>) o;

    Node<E> node = root;
    while (node != null) {
      int res = value.compareTo(node.value);
      if (res < 0) {
        node = node.left;
      } else if (res > 0) {
        node = node.right;
      }
      // res == 0 이라는 것은 같다는 의미
      else {
        return true;
      }
    }
    return false;
  }

  /**
   * Comparable을 이용한 객체 존재 여부를 판단하는 메소드
   *
   * @param o 찾고자 하는 객체
   * @param comparator 사용자에 의해 BinarySearchTree에 지정된 비교기
   * @return 해당 객체가 존재 할 경우 true, 아닐 경우 false를 반환
   */

  private boolean containsUsingComparator(Object o, Comparator<? super E> comparator) {
    @SuppressWarnings("unchecked")
    E value = (E) o;
    Node<E> node = root;
    while (node != null) {
      int res = comparator.compare(value, node.value);
      if (res < 0) {
        node = node.left;
      } else if (res > 0) {
        node = node.right;
      } else {
        return true;
      }
    }
    return false;
  }

  /**
   * BinarySearchTree를 초기화 하는 메소드
   */

  public void clear() {
    size = 0;
    /*
     *  root를 끊어주면 하위 모든 노드들도 더이상
     *  참조할 수 없기 떄문에 GC 처리 된다.
     */
    root = null;
  }

  // <순회> (재귀적)

  /**
   * 전위 순회
   * (부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드)
   */
  public void preOrder() {
    preOrder(this.root);
  }

  public void preOrder(Node<E> o) {
    // null이 아닐 떄 까지 재귀적으로 순회
    if (o != null) {
      System.out.print(o.value + " ");    // 부모 노드
      preOrder(o.left);     // 왼쪽 자식 노드
      preOrder(o.right);    // 오른쪽 자식 노드
    }
  }

  /**
   * 중위 순회 (오름차순)
   * (왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드)
   */
  public void inOrder() {
    inOrder(this.root);
  }

  public void inOrder(Node<E> o) {
    if (o != null) {
      inOrder(o.left);      // 왼쪽 자식 노드
      System.out.print(o.value + " ");    // 부모 노드
      inOrder(o.right);     // 오른쪽 자식 노드
    }
  }

  /**
   * 역중위 순회 (내림차순)
   * (오른쪽 자식 노드 -> 부모 노드 -> 왼쪽 자식 노드)
   */

  public void reverseInOrder() {
    reverseInOrder(this.root);
  }

  public void reverseInOrder(Node<E> o) {
    if (o != null) {
      inOrder(o.right);     // 오른쪽 자식 노드
      System.out.print(o.value + " ");    // 부모 노드
      inOrder(o.left);      // 왼쪽 자식 노드

    }
  }

  /**
   * 후위 순회
   * (왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 부모 노드)
   */
  public void postOrder() {
    postOrder(this.root);
  }

  public void postOrder(Node<E> o) {
    if (o != null) {
      postOrder(o.left);    // 왼쪽 자식 노드
      postOrder(o.right);   // 오른쪽 자식 노드
      System.out.print(o.value + " ");    // 부모 노드
    }
  }
}

public class Main {
  public static void main(String[] args) {

    BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>();

    // 예제에 있는 트리와 동일하게 구성
    tree.add(23);
    tree.add(12);
    tree.add(40);
    tree.add(7);
    tree.add(16);
    tree.add(1);
    tree.add(14);
    tree.add(17);
    tree.add(29);
    tree.add(55);
    tree.add(61);

    System.out.print("중위 순회 : ");
    tree.inOrder(); 	// 중위 순회
    System.out.println();

    System.out.print("역중위 순회 : ");
    tree.reverseInOrder();	// 역중위 순회
    System.out.println();

  }
}

/*
 * 참고한 사이트
 * https://st-lab.tistory.com/300
 */

Binary Search Tree - Basic

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

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

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

  public Node getLeft() {
    return left;
  }

  public void setLeft(Node left) {
    this.left = left;
  }

  public Node getRight() {
    return right;
  }

  public void setRight(Node right) {
    this.right = right;
  }

  public int getValue() {
    return value;
  }

  public void setValue(int value) {
    this.value = value;
  }
}

/*
조건 3가지
1. 어떤 노드 N을 기준으로 왼쪽 서브 트리 노드의 모든 키 값은 노드 N의 키 값보다 작아야 한다.
2. 오른쪽 서브 트리 노드의 키 값은 노드 N의 키 값보다 커야 한다.
3. 같은 키 값을 가지는 노드는 존재하지 않는다.
*/
class BinaryTree {
  Node root;

  private boolean find(int value) {
    Node curNode = root;

    while (curNode != null) {
      if (curNode.getValue() == value) {
        return true;
      } else if (curNode.getValue() > value) {
        curNode = curNode.getLeft();
      } else {
        curNode = curNode.getRight();
      }
    }
    return false;
  }

  public boolean insert(int value) {
    Node newNode = new Node(value); // 값을 받아서 새로운 newNode 생성

    if(find(value)) { // find Method를 호출하여 같은 value를 가진 Node가 존재하는지 확인
      return false;
    }

    if(root == null) {
      root = newNode;
      return true;
    }

    Node curNode = root;
    Node parent;
    while (true) {
      parent = curNode;

      if (value < curNode.getValue()) {
        curNode = curNode.getLeft();
        if(curNode == null) {
          parent.setLeft(newNode);
          return true;
        }
      } else {
        curNode = curNode.getRight();
        if(curNode == null) {
          parent.setRight(newNode);
          return true;
        }
      }
    }
  }

  // 전위 탐색: Root -> Left -> Right
  // 전위 탐색 => 깊이 우선 탐색(DFS)가 된다.(Stack 활용)
  private List<Integer> preOrderTraverse(Node focusNode, List<Integer> integers) {
    if(focusNode != null) {
      integers.add(focusNode.getValue());
      preOrderTraverse(focusNode.getLeft(), integers);
      preOrderTraverse(focusNode.getRight(), integers);
    }
    return integers;
  }

  // 중위 탐색: Left -> Root -> Right
  // 중위 탐색 => 오름차순 정렬
  private List<Integer> inOrderTraverse(Node focusNode, List<Integer> integers) {
    if(focusNode != null) {
      inOrderTraverse(focusNode.getLeft(), integers);
      integers.add(focusNode.getValue());
      inOrderTraverse(focusNode.getRight(), integers);
    }
    return integers;
  }

  // 후위 탐색: Left -> Right -> Root
  private List<Integer> postOrderTraverse(Node focusNode, List<Integer> integers) {
    if(focusNode != null) {
      postOrderTraverse(focusNode.getLeft(), integers);
      postOrderTraverse(focusNode.getRight(), integers);
      integers.add(focusNode.getValue());
    }
    return integers;
  }

  // 너비 우선 탐색(BFS) -> Queue를 이용
  public List<Integer> BFS(Node focusNode) {
    if(focusNode == null) {
      return null;
    }
    List<Integer> result = new ArrayList<>();
    Queue<Node> queue = new LinkedList<>();

    queue.add(focusNode);

    while (!queue.isEmpty()) {
      int size = queue.size();
      for(int i = 0 ; i < size; i++) {
        Node curNode = queue.poll();

        if(curNode.getLeft() != null) {
          queue.add(curNode.getLeft());
        }
        if(curNode.getRight() != null) {
          queue.add(curNode.getRight());
        }
        result.add(curNode.getValue());
      }
    }
    return result;
  }
}

public class Main {
}

/*
 * 참고한 사이트 
 *  - [자바 [JAVA] - Binary Search Tree (이진 탐색 트리) 구현하기](https://k3068.tistory.com/30)
 */