[Data Structure] BST

package tree;

import java.util.ArrayList;
import java.util.List;

public class BinarySearchTree<T extends Comparable<T>> implements ITree<T> {

	private Node<T> root;
	private int size;

	public BinarySearchTree() {
		this.root = null;
		this.size = 0;
	}

	// 구현 순서 1
	public T min() {
		return this.minNode(this.root);
	}

	private T minNode(Node<T> node) {
		// BST에서 가장 왼쪽 마지막에 있는 노드가 최솟값
		T minData = node.data;
		while (node.left != null) { // 해당노드 기준 왼쪽노드가 비어있지 않다면
			node = node.left; // 현재 노드를 왼쪽의 노드로 변경
			minData = node.data; // 해당 노드의 데이터 값
		}
		return minData; // 데이터 값 리턴
	}

	// 구현 순서 2
	public T max() {
		return this.maxNode(root);
	}

	private T maxNode(Node<T> node) {
		// BST에서 가장 오른쪽에 위치한 노드가 최댓값
		T maxData = node.data;
		while (node.right != null) { // 해당노드 기준 오른쪽 노드가 비어있지 않다면
			node = node.right; // 현재 노드를 오른쪽 노드로 변경
			maxData = node.data; // 해당 노드의 데이터 값
		}
		return maxData; // 데이터 값 리턴
	}

	// 구현 순서 7
	@Override
	public void insert(T val) {
		this.root = this.insertNode(this.root, val);
		this.size++;
	}

	// 재귀호출
	private Node<T> insertNode(Node<T> node, T val) {
		if (node == null) {
			return new Node<T>(val);
		}
		if (val.compareTo(node.data) < 0) {
			node.left = insertNode(node.left, val);
		} else if (val.compareTo(node.data) > 0) {
			node.right = insertNode(node.right, val);
		}
		return node;
	}

	// 구현 순서 8
	@Override
	public void delete(T val) {
		deleteNode(root, val);
	}

	// 재귀호출
	private Node<T> deleteNode(Node<T> node, T val) {
		if (node == null) {
			return null;
		}
		if (val.compareTo(node.data) < 0) {
			node.left = deleteNode(node.left, val);
		} else if (val.compareTo(node.data) > 0) {
			node.right = deleteNode(node.right, val);
		} else {
			// val == node.data
			this.size--;
			if (node.left == null) {
				return node.right;
			} else if (node.right == null) {
				return node.left;
			}
			node.data = this.minNode(node.right);
			node.right = deleteNode(node.right, node.data);
		}
		return node;
	}

	// 구현 순서 6
	@Override
	public boolean contains(T val) {

		return containsNode(root, val);
	}

	// 재귀호출
	private boolean containsNode(Node<T> node, T val) {
		if (node == null) { // 노드가 비어있다면
			return false;
		}
		// a.compareTo(b)
		// a < b -> -1
		// a == b -> 0
		// a> b -< 1
		if (val.compareTo(node.data) == 0) { // val == node.data
			return true;
		} else if (val.compareTo(node.data) < 0) { // val < node.data
			return containsNode(node.left, val); // 왼쪽 서브리스트로
		}
		// 오른쪽 서브리스트로
		return containsNode(node.right, val); // val.complareTo(node.data) < 0 => val > node.data
	}

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

	// 구현 순서 3
	// 전위 탐색
	public List<T> preOrder() {
		return preOrderTree(root, new ArrayList<>());
	}

	// 재귀호출
	private List<T> preOrderTree(Node<T> node, List<T> visited) {
		if (node == null) // 더이상 탐색할 데이터가 없음
			return visited;

		visited.add(node.data); // 방문한 노드의 데이터를 리스트에 담는다
		preOrderTree(node.left, visited); // 왼쪽 노드로 이동
		preOrderTree(node.right, visited);  // 오른쪽 노드로 이동

		return visited;
	}

	// 구현 순서 4
	// 중위 탐색
	public List<T> inOrder() {
		return inOrderTree(root, new ArrayList<>());
	}

	// 재귀호출
	private List<T> inOrderTree(Node<T> node, List<T> visited) {
		if (node == null)
			return visited;
		inOrderTree(node.left, visited); // 왼쪽 노드로 이동
		visited.add(node.data); // 방문한 노드의 데이터를 리스트에 담는다
		inOrderTree(node.right, visited);  // 오른쪽 노드로 이동
		return visited;
	}

	// 구현 순서 5
	// 후위 탐색
	public List<T> postOrder() {
		return postOrderTree(root, new ArrayList<>());
	}

	// 재귀호출
	private List<T> postOrderTree(Node<T> node, List<T> visited) {
		if (node == null)
			return visited;

		postOrderTree(node.left, visited); // 왼쪽 노드로 이동
		postOrderTree(node.right, visited);  // 오른쪽 노드로 이동
		visited.add(node.data); // 방문한 노드의 데이터를 리스트에 담는다

		return visited;
	}

	private class Node<T> {
		T data;
		Node<T> left;
		Node<T> right;

		Node(T data) {
			this.data = data;
		}
	}
}