언제쯤 이 코드리뷰가 물흐르듯 될까😭
하루종일 삽질해서 비니루라도 찾으면 좋겠다.
import java.util.*;
public class Solution {
// 트리를 구성하는 노드 클래스입니다.
public static class Node {
private int data;
private Node left;
private Node right;
/* 생성자 */
public Node(int data) {
this.setData(data);
setLeft(null);
setRight(null);
}
public int getData() {
return data;
}
public Node getLeft() {
return left;
}
public Node getRight() {
return right;
}
public void setData(int data) {
this.data = data;
}
public void setLeft(Node left) {
this.left = left;
}
public void setRight(Node right) {
this.right = right;
}
}
//이진 탐색 트리의 클래스입니다.
public static class binarySearchTree {
public Node root;
public binarySearchTree(){
root = null;
}
// tree에 value를 추가하는 메서드
public void insert(int data) { //리턴타입이 없는 insert메서드(int타입의 데이터가 인자로 들어온다)
Node newNode = new Node(data);// data 의 값이 저장된 새 노드 생성(왼쪽, 오른쪽 노드는 null인 상태)
//root에 값이 없을때
if (root == null) {//만약 루트가 null값이라면, (즉 트리가 비어있는 상태라면)
root = newNode; // data가 저장된 newNode가 저장됨.
}
if(root.data == data){return;} //중복일때 정지. root의 데이터값과 입력받은 데이터값이 같으면 메서드실행하지 않음
// -> void타입은 리턴타입이 없다고 하였는데 59번에서는 왜 return문이 등장하는지?
// root에 값이 있고 && root의 데이터가 입력받은 데이터의 값과 다를때
Node currentNode = root; // 현재노드는 root가 됨
//-> 현재노드에 root값을 넣어주는이유? 첫 시작점을 current가 루트(최상단 노드)부터 시작하겠다는 의미
Node parentNode = null; //부모노드는 null
//-> 부모노드를 NUll로 만드는 이유? 실제 이진트리에서 좌측,우측으로 이동해서 현재노드를 변경하게 되는데 current노드가 변경되기 전에 현재노드를 기억하기 위해서 저장하는 과정이다.
// 트리구조자체는 항상 자식노드를 가지게 되어있는 자료구조 인데, 기준점에 따라 부모노드가 달라질 수 있다.
while (true) { //특별한 경우가 아닌 이상 반복문을 순회하겠다.
parentNode = currentNode; //현재노드는 부모노드가 됨
if (data < currentNode.getData()) { // 만일 데이터가 현재노드보다 작은경우 왼쪽 노드를 가져온다
currentNode = currentNode.getLeft();
if (currentNode == null) { // 좌측노드
parentNode.setLeft(newNode);
return;
}else if(currentNode.data == newNode.data) return; //데이터를 추가하지 않겠다
} else { // 해당 노드보다 클 경우
currentNode = currentNode.getRight(); //우측의 값을 넣어줌
if (currentNode == null) {
parentNode.setRight(newNode); // 값이 비어있으면 새로운 값을 넣어주겠다
return;
}else if(currentNode.data == newNode.data) return;
}
}
}
// tree의 value값을 탐색합니다.
public boolean contains(int data) {
Node currentNode = root;
while (currentNode != null) { //
// 찾는 value값이 노드의 value와 일치한다면, true를 리턴합니다.
if (currentNode.data == data) {
return true;
}
if (currentNode.data > data) {
// 찾는 value값이 노드의 value 보다 작다면, 현재 노드를 left로 변경후 다시 반복합니다.
currentNode = currentNode.left;
}else {
// 찾는 value값이 노드의 value 보다 크다면, 현재 노드를 right로 변경후 다시 반복합니다.
currentNode = currentNode.right;
}
}
return false;
}
/*
트리의 순회에 대해 구현을 합니다.
지금 만드려고 하는 이 순회 메서드는 단지 순회만 하는 것이 아닌, 함수를 매개변수로 받아 콜백 함수에 값을 적용시킨 것을 순회해야 합니다.
전위 순회를 통해 어떻게 탐색하는지 이해를 한다면 중위와 후위 순회는 쉽게 다가올 것입니다.
*/
// 이진 탐색 트리를 전위 순회하는 메서드를 만듭니다.
public ArrayList<Integer> preorderTree(Node root, int depth, ArrayList<Integer> list) { //전위 순회
if (root != null) {
list.add(root.getData());
preorderTree(root.getLeft(), depth + 1, list);
preorderTree(root.getRight(), depth + 1, list);
}
return list;
}
public ArrayList<Integer> inorderTree(Node root, int depth, ArrayList<Integer> list) { //중위 순회
if (root != null) {
inorderTree(root.getLeft(), depth + 1, list);
list.add(root.getData());
inorderTree(root.getRight(), depth + 1, list);
}
return list;
}
public ArrayList<Integer> postorderTree(Node root, int depth, ArrayList<Integer> list) { //후위 순회
if (root != null) {
postorderTree(root.getLeft(), depth + 1, list);
postorderTree(root.getRight(), depth + 1, list);
list.add(root.getData());
}
return list;
}
}
}