Java 이진탐색트리(Binary Search Tree)

우리는 자바로 이진트리를 작성해보도록 하겠다.

이진트리는 이 블로그 목록 알고리즘-> 완전이진탐색트리를 C로 정의를 해둔 내용있다.
(http://itqomcom.blogspot.com/2016/05/blog-post_31.html)

해당 내용들을 참고하면서 이해하면 될 것이다.

1. BST_Func 인터페이스 구현 (역할 : 트리의 필요기능 정의)

1. package org.java.project.binaryTree;
3. public interface BST_Func {
4.    
5.     //1) 루트의 자식인 객체하나를 생성하고 BST_Insert를 호출하여 저장시킴.
6.     public void BST_Create(BST_Head Tree, int Data);
7.     //2) 이진트리 전체를 탐색하여 출력함.
8.     public void BST_Search(BST_Head Tree);
9.     public void BST_Insert(BST_Head First, BSTNode Child, int Data); // 삽입
11.     public int BST_Delete(BST_Head TreeNode); // 객체 지우기
12.    
13.     public void BST_Destroy(BST_Head Tree); // 전체제거
14.    
15. }

2. BinaryTree 클래스 구현 (역할 : 트리의 필요기능 메소드 정의) 

1. package org.java.project.binaryTree;
3. public class BinaryTree implements BST_Func{
4.     public void BST_Create(BST_Head Tree, int Data) { // 처음생성
5.             BSTNode ChildNode = new BSTNode(Data);
6.             System.out.println("InsertChildNode : " + Data);
7.             BST_Insert(Tree, ChildNode, Data);
8.     }
9.     public void BST_Search(BST_Head Tree) {
10.         if(Tree.count < 1) {
11.             System.out.println("생성된 트리가 없습니다!");
12.             System.exit(0);
13.         }
14.         if(Tree.left != null) {
15.             BST_Search(Tree.left);
16.         }
17.        
18.         System.out.print(Tree.data + " ");
19.        
20.         if(Tree.right != null) {
21.             BST_Search(Tree.right);
22.         }
23.     }
24.     public void BST_Insert(BST_Head First, BSTNode Child, int Data) {
25.         if(First.data < Data) { // 현재 노드보다 큰경우
26.             if(First.right != null)
27.                 BST_Insert(First.right, Child, Data);
28.             else
29.                 First.right = Child;
30.         }
31.         else { // 현재 노드보다 작은경우
32.             if(First.left != null)
33.                 BST_Insert(First.left, Child, Data);
34.             else
35.                 First.left = Child;
36.         }
37.     }
38.    
39.     public void BST_Destroy(BST_Head Tree) { //이진트리 전체제거
40.         if(Tree.left != null) {
41.             BST_Destroy(Tree.left);
42.         }
43.         if(Tree.right != null) {
44.             BST_Destroy(Tree.right);
45.         }
46.         int removed = BST_Delete(Tree); //객체를 NULL값으로 만들어버림
47.         System.out.println(removed + "제거완료!");
48.     }
49.    
50.     public int BST_Delete(BST_Head TreeNode) { //객체하나 제거
51.         int Removed = TreeNode.data;
52.         TreeNode.left = null;
53.         TreeNode.right = null;
54.         TreeNode= null;
55.         return Removed;
56.     }
57. }

3. BST_Head 클래스 구현 (역할 : 루트에 해당하는 트리의 노드)

1. package org.java.project.binaryTree;
3. public class BST_Head extends BinaryTree{
4.     public BSTNode left; // 상속시키는 BSTNode클래스 타입 지정 1
5.     public BSTNode right; // 상속시키는 BSTNode클래스 타입 지정 2
6.     public int data;
7.    
8.     public static BST_Head Tree;
9.     public static int count = 0;
10.    
11.     public BST_Head(int data) {
12.         this.count++;
13.         this.data = data;
14.         this.left = null;
15.         this.right = null;
16.     }
17.    
18. }

4. BSTNode 클래스 구현 (역할 : 루트노드의 자식에 해당하는 노드)

1. package org.java.project.binaryTree;
3. public class BSTNode extends BST_Head{
4.    
5.     public BSTNode(int data) {     
6.         super(data);
7.     }
8. }

5. 메인함수 실행 (역할 : 이진트리를 실행시킴)

package org.java.project.binaryTree;

public class BinaryTreeExecute {

public static void main(String[] args) {

System.out.println("BinarySearchTree\n");

BST_Head Tree = new BST_Head(5);

System.out.println("Tree Root : 5");

Tree.BST_Create(Tree, 4);

Tree.BST_Create(Tree, 6);

Tree.BST_Create(Tree, 10);

Tree.BST_Create(Tree, 2);

Tree.BST_Create(Tree, 7);

Tree.BST_Create(Tree, 3);

System.out.println("\nBST Count : " + Tree.count);

Tree.BST_Search(Tree);

System.out.print("\n\n\n");

System.out.println("Destroy BinaryTree!");

Tree.BST_Destroy(Tree);

}

}

▶ 실행결과

: 루트노드는 BST_Head클래스에서 인스턴스화 하여 구현되고, 트리의 자식 노드들은 BST_Head클래스를 상속받는 BSTNode에서 인스턴스화 되어진다.