[JAVA] 재귀 - 이진 탐색 트리(Binary Search Tree)의 삽입 - (2)

앞에 글에 이어서.. 

앞 글  - http://marobiana.tistory.com/81

문제 : 트리에 넣을 숫자들을 입력 받아 이진탐색트리를 만들어라.

3. 예제

C++로 하면 포인터 써서 눈에 보기 더 좋을 것을ㅠㅠ Java로 포인터처럼 짜봤음 ㅋㅋ

아래와 같이 3개의 클래스로 구성할 수 있음.

트리 삽입

참고로, Tree에 넣는 숫자 순서가 트리모양을 결정한다

public class BinarySearchTree {          public static void main(String[] args) { Tree tree = new Tree(); tree.addNode(24); tree.addNode(15); tree.addNode(19); tree.addNode(2); tree.addNode(28); tree.addNode(27); tree.addNode(30); } }

Node

각각의 노드에 대한 속성이 담긴 클래스

public class Node { private int value;  private Node left; private Node right; // Setter and Getter         ...... }

Tree

위에서 만든 노드들을 이어서 하나의 트리를 만드는 클래스

public class Tree { public Node root; public void addNode(int value) { if (root == null) { Node node = new Node(); node.setValue(value); root = node; // root에 값이 없으면, root에 값을 넣는다. } else {                         // root가 존재할 경우, root 변경하기 위한 메소드 호출 addNode(value, root);  } } public void addNode(int value, Node root) { if (value <= root.getValue()) { if (root.getLeft() == null) { Node node = new Node(); node.setValue(value); root.setLeft(node); } else { addNode(value, root.getLeft()); } } else { if (root.getRight() == null) { Node node = new Node(); node.setValue(value); root.setRight(node); } else { addNode(value, root.getRight()); } } } }

Tree 클래스가 핵심이다!

Tree객체에서 Root Node를 갖고있고, 

그 노드는 자식노드를 갖고있고, 

자식노드는 자식노드를 갖고 있는 식으로 된 구조이다.

삽입부분에서는 오버로딩과 재귀함수를 사용했음.

1) Root에 값이 없으면 Root에 값을 넣는다. 2) Root에 값이 있으면,     입력된 값이 Root보다 크면 오른쪽에 넣고, 작으면 왼쪽에 넣는다. 3) 오른쪽 혹은 왼쪽에 값이 이미 들어있으면,     입력된 값과 비교해서 크면 오른쪽에 넣고, 작으면 왼쪽에 넣는다. 4) 오른쪽 혹은 왼쪽에 값이 이미 들어있으면,     입력된 값과 비교해서 크면 오른쪽에 넣고, 작으면 왼쪽에 넣는다. ....

addNode(int value) 메소드에서 1)을 실행한다.

Root에 값이 없었으면 값을 넣고,

값이 이미 존재하면, 인자가 두개인 addNode(int value, Node root) 메소드를 호출한다.

소스를 보면 알겠지만, 이미 값이 있을 경우 오른쪽 혹은 왼쪽노드를 Root로 교체한다.

1번과 2번을 반복해 나가며, 

Root에 값이 없어서 세팅할 수 있을 때까지 재귀가 호출되는 것이다.