앞서 배운 링크드리스트, 해쉬 모두 어렵지만 유독 트리는 더더욱 구현이 어려운 것 중 하나인 것 같아요😭 그래도 트리만 넘으면 큰 고비 하나 넘은 것이니 화이팅합시다 👊

트리는 양이 너무 방대하다보니, 1과 2로 나눠서 정리해보겠습니다 😘

이진 트리

: Branch가 최대 2개이고, 검색에 매우 유용하다.

public class hash{
    public Node root=null;
    public static void main(String[] args) {
        hash mytree=new hash();
        mytree.Insert(3);
        mytree.Insert(5);
        mytree.Insert(1);
        mytree.Insert(4);
        System.out.println(mytree.root.left.data);
        System.out.println(mytree.root.right.data);
        System.out.println(mytree.root.right.left.data);
    }

    public class Node{
        Integer data;
        Node left;
        Node right;

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

    /*트리에 노드추가*/
    public boolean Insert(Integer data) {
        //1. 아무 데이터도 없는 경우
        if (this.root == null) {
            this.root = new Node(data);
            return true;
        }
            //2. 데이터가 있는 경우
        else {
            Node CurrentNode = this.root;
            while(true){
                //왼쪽으로 이동
                if(data<CurrentNode.data){
                    if(CurrentNode.left==null){
                        CurrentNode.left=new Node(data);
                        break;
                    }
                    else
                        CurrentNode=CurrentNode.left;
                }
                //오른쪽으로 이동
                else{
                    if(CurrentNode.right==null){
                        CurrentNode.right=new Node(data);
                        break;
                    }
                    else
                        CurrentNode=CurrentNode.right;
                }
            }
            return true;
        }
    }

    public Integer BinarySearch(Integer data){
        if(root==null)
            return -1;
        else{
            Node CurrentNode=this.root;
            while(CurrentNode!=null) {
                //left로 가는 경우
                if(data<CurrentNode.data){
                    if(CurrentNode.left.data==data)
                        return CurrentNode.left.data;
                    else
                        CurrentNode=CurrentNode.left;
                }
                else{
                    if(CurrentNode.right.data==data)
                        return CurrentNode.right.data;
                    else
                        CurrentNode=CurrentNode.right;
                }
            }
            return -1;
        }
    }
}