이진검색트리

BinaryTree.java

package com.javaStudyTest.binaryTree;

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

public class BinaryTree {
    private Node root;

    public BinaryTree() {
        this.root = null;
    }

    /**
     * Node 삽입
     * 먼저 트리를 정렬된 상태로 유지하기 위해 새 노드를 추가할 위치를 찾아야 합니다. 루트 노드부터 다음 규칙을 따르겠습니다:
     * 새 노드의 값이 현재 노드의 값보다 낮으면 왼쪽 자식으로 이동합니다.
     * 새 노드의 값이 현재 노드의 값보다 크면 오른쪽 자식으로 이동합니다.
     * 현재 노드가 널이면 리프 노드에 도달한 것이고, 그 위치에 새 노드를 삽입할 수 있습니다.
     * @param root
     * @param value
     * @return Node
     */
    private Node insertNode(Node root, int value){
        if(root==null){
          return new Node(value);
        }
        if(root.getValue()<=value){
            root.setRight(insertNode(root.getRight(),value));
        }else{
            root.setLeft(insertNode(root.getLeft(),value));
        }
        return root;
    }

    public void add(int value){
        root = insertNode(root,value);
    }


    /**
     * dfs 왼쪽->루트->오른쪽 순으로 순회하며 출력
     */
    public void dfs(Node node){
        if(node!=null){
            dfs(node.getLeft());
            System.out.print(node.getValue()+" ");
            dfs(node.getRight());
        }
    }


    public void bfs(Node node){
       if(node==null)return;

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

        while(!q.isEmpty()){
            Node cur = q.remove();
            System.out.print(" " + cur.getValue());

            if(cur.getLeft()!=null)q.add(cur.getLeft());
            if(cur.getRight()!=null)q.add(cur.getRight());
        }

    }


    public Node getRoot() {
        return root;
    }
}