07-9 트리 정렬

※ 트리 정렬(TreeSort)

 - 트리 정렬은 이진 탐색 트리를 이용하여 정렬하는 방법

 - 정렬할 원소들을 이진 탐색 트리로 구성하고 중위 순회 방법을 사용하여 이진 탐색 트리의 원소들을 순회하여 꺼내온다.

TreeSort

public class TreeSort {

       

       Node root =null;

       int[] result = null;

       int idx=0;

       

       public void treeSort(int[] a){

              

              result = new int[a.length];

              

              for(int i=0; i<a.length; i++){

                     insertBST(a[i]);

              }

              

              inorder(root);

              printTreeSort();

              

       }

       

       public void inorder(Node root){

              if(root != null){

                     inorder(root.left);

                     result[idx++]=root.getData();

                     inorder(root.right);

              }

       }

       

       public void insertBST(int data){

              

              Node newNode = new Node(data);

              Node temp;

              if(root ==null){

                     root = newNode;

              }else{

                     temp = root;

                     while(true){

                           if(temp.getData() > data){

                                  if(temp.left == null){

                                         temp.left= newNode;

                                         return;

                                  }else{

                                         temp = temp.left ;

                                  }

                           }else{

                                  if(temp.right == null){

                                         temp.right= newNode;

                                         return;

                                  }else{

                                         temp = temp.right;

                                  }

                           }

                     }

                     

              }

       }

       

       public void printTreeSort(){

              System.out.print("\n정렬된 원소 : ");

              for(int i=0; i <result.length; i++){

                     System.out.print(result[i]+" ");

              }

              System.out.println();

       }

}

Main

public class Main {

       public static void main(String args[]){

              int a[] = {69,10,30,2,16,8,31,22};

              int size = a.length;

              TreeSort ts = new TreeSort();

              System.out.println("정렬할 원소 : ");

              for(int i=0; i<a.length; i++){

                     System.out.print(" " + a[i]);

              }

              System.out.println();

              ts.treeSort(a);

       }

}