5주차 과제 : 추가사항

이진탐색트리

package com.example.demo;

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

    Node(int value){
        this.value=value;
        this.left=this.right=null;
    }
    //Node 추가
    public Node addNode(Node cur,int value){
        if(cur==null)return new Node(value);
        if(cur.value<value)
            cur.right = addNode(cur.right,value);
        else
            cur.left = addNode(cur.left,value);
        return cur;
    }
    //Node 삭제
    public Node removeNode(Node cur,int value){
        if(cur==null)return null;
        if(cur.value==value){
            //왼쪽 자식노드가 존재할때
            if(cur.left!=null)
                return find_node(cur,cur.left);
            //왼쪽 자식노드가 존재하지 않을때
            else
                return cur.right;
        }
        if(cur.value<value)
            cur.right = removeNode(cur.right,value);
        else
            cur.left = removeNode(cur.left,value);
        return cur;
    }
    //삭제한 노드에 대처되는 노드
    public Node find_node(Node pre,Node cur){
        if(cur.right==null){
            pre.right=null;
            return cur;
        }
        return find_node(cur,cur.right);
    }
    //전위탐색
    public void preorder(Node cur){
        if(cur==null)return;
        System.out.println("preorder : " + cur.value);
        preorder(cur.left);
        preorder(cur.right);
    }
    //중위탐색
    public void inorder(Node cur){
        if(cur==null)return;
        inorder(cur.left);
        System.out.println("inorder : " + cur.value);
        inorder(cur.right);
    }
    //후위탐색
    public void postorder(Node cur){
        if(cur==null)return;
        postorder(cur.left);
        postorder(cur.right);
        System.out.println("postorder : " + cur.value);
    }
}

TESTCODE

package com.example.demo;

import org.junit.jupiter.api.*;

import static org.junit.jupiter.api.Assertions.*;

@TestInstance(TestInstance.Lifecycle.PER_CLASS)
@TestMethodOrder(MethodOrderer.OrderAnnotation.class)
class NodeTest {
    Node node;
    @BeforeAll
    void beforAll(){
        node = new Node(3);
    }
    @Test
    void test(){
        node.addNode(node,10);
        node.addNode(node,7);
        node.addNode(node,4);
        node.addNode(node,5);
        node.addNode(node,6);

        node = node.removeNode(node,10);
        postorder();
        node =node.removeNode(node,3);
        postorder();
    }
    void preorder(){
        node.preorder(node);
    }
    void inorder(){
        node.inorder(node);
    }
    void postorder(){
        node.postorder(node);
    }
}

BFS

package com.example.demo;

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

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

    Node(int value){
        this.value=value;
        this.left=this.right=null;
    }
    //Node 추가
    public Node addNode(Node cur,int value){
        if(cur==null)return new Node(value);
        if(cur.value<value)
            cur.right = addNode(cur.right,value);
        else
            cur.left = addNode(cur.left,value);
        return cur;
    }
    //Node 삭제
    public Node removeNode(Node cur,int value){
        if(cur==null)return null;
        if(cur.value==value){
            //왼쪽 자식노드가 존재할때
            if(cur.left!=null)
                return find_node(cur,cur.left);
            //왼쪽 자식노드가 존재하지 않을때
            else
                return cur.right;
        }
        if(cur.value<value)
            cur.right = removeNode(cur.right,value);
        else
            cur.left = removeNode(cur.left,value);
        return cur;
    }
    //삭제한 노드에 대처되는 노드
    public Node find_node(Node pre,Node cur){
        if(cur.right==null){
            pre.right=null;
            return cur;
        }
        return find_node(cur,cur.right);
    }
    //전위탐색
    public void preorder(Node cur){
        if(cur==null)return;
        System.out.println("preorder : " + cur.value);
        preorder(cur.left);
        preorder(cur.right);
    }
    //중위탐색
    public void inorder(Node cur){
        if(cur==null)return;
        inorder(cur.left);
        System.out.println("inorder : " + cur.value);
        inorder(cur.right);
    }
    //후위탐색
    public void postorder(Node cur){
        if(cur==null)return;
        postorder(cur.left);
        postorder(cur.right);
        System.out.println("postorder : " + cur.value);
    }
    //BFS
    public void BFS(Node node){
        Queue<Node> q = new LinkedList<>();
        q.add(node);
        while(!q.isEmpty()){
            Node cur = q.poll();
            System.out.println("Queue : " + cur.value);
            if(cur.left!=null)
                q.add(cur.left);
            if(cur.right!=null)
                q.add(cur.right);
        }
    }
}

TESTCODE

package com.example.demo;

import org.junit.jupiter.api.*;

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

import static org.junit.jupiter.api.Assertions.*;

@TestInstance(TestInstance.Lifecycle.PER_CLASS)
@TestMethodOrder(MethodOrderer.OrderAnnotation.class)
class NodeTest {
    Node node;
    @BeforeAll
    void beforAll(){
        node = new Node(3);
    }
    @Test
    void test(){
        node.addNode(node,10);
        node.addNode(node,7);
        node.addNode(node,4);
        node.addNode(node,5);
        node.addNode(node,6);

        //node = node.removeNode(node,10);
        //postorder();
        //node =node.removeNode(node,3);
        //postorder();

        node.BFS(node);
    }
    //preorder==DFS
    void preorder(){
        node.preorder(node);
    }
    void inorder(){
        node.inorder(node);
    }
    void postorder(){
        node.postorder(node);
    }
}

+DFS는 preorder과 로직이 같습니다. 현재 Binary_Search_Tree 로 기반으로 DFS와 BFS를 실행하였기 때문에 단순히 DFS는 preorder과 같고 BFS는 왼쪽,오른쪽 자식의 존재여부만 확인하면 됩니다. 다만 단방향 그래프의 특성상 싸이클이 존재하지 않으므로 별도로 상태배열을 만들어줄 필요성이 없으나 양방향 그래프인 경우 반드시 상태배열을 생성하여 방문하였는지 체크해주어야 합니다.