이진 트리 (1)

이진 트리의 개념및 데이터 삽입 

public class NodeMgmt {
//	트리(Tree)의 구조
//	트리 : Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 
//	Branch : 노드와 노드를 연결 
//	실제 사용 처 :  
//		트리 중 이진 트리(Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용된다.
//		
//	용어 : 
//		Node : 트리에서 데이터를 저장하는 기본요소(데이터와 다른 연결된 노드에 대한 Branch 정보도 포함한다)
//		Root Node : 트리 맨 위에 있는 노드 (최상위 노드)
//		Level : 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타낸다.
//		Parent Node : 어떤 노드의 다음 레벨에 연결된 노드
//		Child Node : 어떤 노드의 상위 레벨에 연결된 노드
//		Leaf Node (Terminal Node) : Child Node가 하나도 없는 노드
//		Sibling (Brother Node) : 동일한 Parent Node를 가진 노드
//		Depth : 트리에서 Node가 가질 수 있는 최대 Level
		
//	이진 트리와 이진 탐색 트리(Binary Search Tree)
//	이진 트리 : 노드의 최대 Branch가 2인 트리
//	이진 탐색 트리(Binary Search Tree, BST) : 이진 트리에 다음과 같은 추가적인 조건이 있는 트리
//	-> 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음

//	이진 탐색 트리의 주요 용도 : 데이터 검색(탐색)
//	이진 탐색 트리의 장점 : 탐색 속도를 개선할 수 있다.
	
//	헤드 초기화
	Node head = null;
//	노드 클래스 만들기 
	public class Node{
		Node left;
		Node right;
		int value;
		public Node(int data){
			this.value = value;
			this.left = null;
			this.right= null;
		}
	}

//	이진 탐색 트리에 데이터 넣기
	public boolean insertNode(int data){
		//Case 1 : Node가 하나도 없을 때
		if(this.head == null){
			this.head = new Node(data);
		}else{ //Case 2 : Node가 하나 이상 존재할 때
			Node findNode =this.head;
			while(true){ //Case2-1 : 현재 Node의 왼쪽에 Node가 들어가야 할 떄
				if(data < findNode.value){ 
					if(findNode.left != null){ //왼쪽 노드가 비어있지 않으면 
						findNode = findNode.left; //왼쪽 노드로 find를 바꿔서 다시 탐색 (level down)
					}else{ //왼쪽 노드가 비어있으면
						findNode.left =new Node(data); //왼쪽에 데이터를 삽입
						break;
					}
					//Case 2-2 : 현재 Node의 오른쪽에 Node가 들어가야 할때
				} else{ // data > findNode.value
					if(findNode.right != null){ //오른쪽 노드가 비어있지 않으면
						findNode = findNode.right;  //오른쪽 노드로 findNode로 바꿔서 다시 탐색(level down)
					} else{ //오른쪽 노드가 비어있으면
						findNode.right = new Node(data);
						break;
					}
				}
			}
		}
		return true;
	}
	
	
	
	public static void main(String[] args) {
		NodeMgmt myTree =new NodeMgmt();
		System.out.println(myTree.insertNode(2));
		System.out.println(myTree.insertNode(3));
		System.out.println(myTree.insertNode(4));
		System.out.println(myTree.insertNode(6));

		

	}

}