링크드리스트를 이용한 이진트리.
재귀호출 : 노드 추가시, 전/중/후 위 순회시.
속도 : 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;}
};
'Computer > Java' 카테고리의 다른 글
[Data Structure2] Graph Matrix (0) | 2006.10.22 |
---|---|
Static on Java- Speed Test (0) | 2006.10.09 |
[Data Structure2] Max Heap (for int array) (0) | 2006.10.09 |
[tip] 화면 크기 구하기. (0) | 2006.08.04 |
Omok Server For Flash Client Ver1.0 (0) | 2006.07.23 |