반응형
-이진트리란?
트리의 한 종류로써 대표적인 비선형 자료구조의 형태로 1개의 데이터에 대해 0, 1, 2개의 자식 노드를 가지는 트리를 말한다. 이진트리는 일반적으로 탐색을 할 때 많이 사용하는데 그 이유는 특정 데이터를 탐색하고자 할 때 좌, 우로 나뉘어서 탐색하기 때문에 한쪽을 일방적으로 제외할 수 있어 빠른 탐색속도를 가지게 된다. 이진트리의 구현은 일반적으로 배열과 노드를 이용해 구현이 가능하지만, 완전 이진트리를 제외하고는 배열을 사용할 때 많은 메모리 낭비가 발생하기 때문에 노드로 구현하는 것이 좋다.
-이진트리의 순회방식
이진트리의 순회방식으로는 3가지가 존재하는데 1)전위순회, 2)중위순회, 3)후위순회이다. 이는 탐색하는 순서에 따라 구분되며 D를 현재의 노드, L을 왼쪽 자식노드,R을 오른쪽 자식노드라 할 때 순서대로 각각 D-L-R, L-D-R, L-R-D의 형태로 트리를 순회하게 된다. 후위순회의 경우에는 컴퓨터에서 수식을 연산할 때 사용되므로 계산기와 같은 프로그램을 만들 때 유용하다.
class Doubly_List_Node{// 노드 클래스
private int data; //노드의 데이터 필드
public Doubly_List_Node Llink; // 노드의 왼쪽 링크 필드
public Doubly_List_Node Rlink; // 노드의 오른쪽 링크 필드
public Doubly_List_Node() { // 노드의 기본 생성자
this.data =0;
this.Llink = null;
this.Rlink = null;
}
public Doubly_List_Node(int data) {
this.data = data;
this.Llink = null;
this.Rlink = null;
}
public Doubly_List_Node(Boolean jud,Doubly_List_Node link) {
if(jud == true) {
this.data = 0;
this.Llink = link;
this.Rlink = null;
}else {
this.data = 0;
this.Llink = null;
this.Rlink = link;
}
}
public Doubly_List_Node(Boolean jud,Doubly_List_Node link,int data) {
if(jud == true) {
this.data = data;
this.Llink = link;
this.Rlink = null;
}else {
this.data = data;
this.Llink = null;
this.Rlink = link;
}
}
public Doubly_List_Node(Doubly_List_Node Llink,Doubly_List_Node Rlink) {
this.data = 0;
this.Llink = Llink;
this.Rlink = Rlink;
}
public Doubly_List_Node(int data, Doubly_List_Node Llink,Doubly_List_Node Rlink) {
this.data = data;
this.Llink = Llink;
this.Rlink = Rlink;
}
public int getData() { // 노드의 데이터를 반환하는 메소드
return this.data;
}
public void setData(int i) {
this.data = i;
}
}
public class Binary_tree {
public static void preOrder(Doubly_List_Node prenode) { // 이진트리를 전위순회 출력 방식
if(prenode !=null) { // 공백노드가 아니라면
System.out.print(prenode.getData() + " / ");
preOrder(prenode.Llink);
preOrder(prenode.Rlink);
}
}
public static void inOrder(Doubly_List_Node prenode) { // 이진트리를 중위순회 출력 방식
if(prenode !=null) { // 공백노드가 아니라면
inOrder(prenode.Llink);
System.out.print(prenode.getData() + " / ");
inOrder(prenode.Rlink);
}
}
public static void postOrder(Doubly_List_Node prenode) { // 이진트리를 후위순회 출력 방식
if(prenode !=null) { // 공백노드가 아니라면
postOrder(prenode.Llink);
postOrder(prenode.Rlink);
System.out.print(prenode.getData() + " / ");
}
}
public static void main(String[] args) {
Doubly_List_Node arr[] = new Doubly_List_Node[16]; //15개의 데이터
for(int i=0;i<arr.length;i++) {
arr[i] = new Doubly_List_Node(i);
}
for(int i=1;i<arr.length;i++) {
if(i %2 ==0) { // i가 2의 배수일 경우 즉, 짝수일 경우 왼쪽 자식노드에 위치하고
arr[i/2].Llink = arr[i];
}else { // 홀수일 경우 오른쪽 자식노드에 위치하게 된다.
arr[i/2].Rlink = arr[i];
}
}
preOrder(arr[1]);
}
}