[Data Structure2] Binary Tree (Linked List)

링크드리스트를 이용한 이진트리.
재귀호출 : 노드 추가시, 전/중/후 위 순회시.
속도 : 1만번 add() 함수 호출 결과 평균 47m/s.
        1만개의 노드 전/중/후 방문. 모두 1m/s 이하.(출력 시간 제외)
단점 : 노드의 갯수가 한정량 이상(본 시스템 환경 상 1000만개) 발생시 Heap Space Overflow Exception 발생.
Heap Space를 증가시켜주면 되지만, 적당한 해결책 아닌 듯 함.


//######################################################//
//----------------------< 테스트 클래스 >------------------------//
//######################################################//
class TreeTest{
   public TreeTest(){
       Tree tree=    new Tree();

       tree.add("Pig");
       tree.add("Octopus");
       tree.add("Bear");
       tree.add("Dolphin");
       tree.add("Elephant");
       tree.add("Bull");
       tree.add("Chicken");
       tree.add("Snake");
       tree.add("Lion");
       tree.add("Dog");
       tree.add("Tiger");

       tree.postorder(tree.rootNode);
   }

   public static void main(String args[]){
       TreeTest    tt=    new TreeTest();
   }
};

//######################################################//
//-----------------------< 트리 클래스 >-------------------------//
//######################################################//
class Tree{
   TreeNode    rootNode; //루트 노드(제일 처음 누가 되는 노드)

   public void add(Object data){
       if(rootNode==null){
           //노드가 하나도 없을 경우 루트노드를 생성한다.
           rootNode=    new TreeNode(data);
       }else{
           //노드가 하나라도 존재 할 경우
           add(rootNode, data);
       }
   }

   public void add(TreeNode sNode, Object data){
       if(compare(sNode.getData(), data)>0){
       //새로 추가되는 값이 작을 경우, 좌측에 추가시키게 된다.
           if(sNode.getLeft()==null){
               sNode.setLeft(new TreeNode(data));
           }else{
               add(sNode.getLeft(), data);
           }
       }else if(compare(sNode.getData(), data)<0){
       //새로 추가되는 값이 클 경우, 우측에 추가시키게 된다.
           if(sNode.getRight()==null){
               sNode.setRight(new TreeNode(data));
           }else{
               add(sNode.getRight(), data);
           }
       }
   }

   //######################################################//
   //-------------------------< 순회 부분 >-------------------------//
   //#####################################################//

   //전위순회
   public void preorder(TreeNode sNode){
       if(sNode!=null){
           System.out.println(sNode.getData());
           preorder(sNode.getLeft());
           preorder(sNode.getRight());
       }
   }

   //중위순회
   public void inorder(TreeNode sNode){
       if(sNode!=null){
           inorder(sNode.getLeft());
           System.out.println(sNode.getData());
           inorder(sNode.getRight());
       }
   }

   //후위순회
   public void postorder(TreeNode sNode){
       if(sNode!=null){
           postorder(sNode.getLeft());
           postorder(sNode.getRight());
           System.out.println(sNode.getData());
       }
   }

   //두 데이터 값을 비교하여, 좌측이 클 경우 양수, 우측이 클 경우 음수 리턴.
   private int compare(Object obj1, Object obj2){
       return ((String)obj1.toString()).compareTo(obj2.toString());
   }
};

//######################################################//
//-----------------------< 노드 클래스 >------------------------//
//#####################################################//
public class TreeNode{
    private Object  data; //노드의 데이터
    private TreeNode left; //좌측 자식 노드를 가리킨다.
    private TreeNode right; //우측 자식 노드를 가리킨다.

    //######################################################//
    //--------------------------< 생성자 >---------------------------//
    //#####################################################//
    public TreeNode(Object data){
         this.data= data;
    }

    //######################################################//
    //--------------------------< 수정자 >---------------------------//
    //#####################################################//
    public void setData(Object data){  this.data= data;}
    public void setLeft(TreeNode left){  this.left= left;}
    public void setRight(TreeNode right){ this.right= right;}

    //######################################################//
    //--------------------------< 반환자 >---------------------------//
    //######################################################//
    public Object getData(){ return data;}
    public TreeNode getLeft(){ return left;}
    public TreeNode getRight(){ return right;}
};