이진 트리(binary tree)의 정의

자료구조를 오랜만에 공부하다 보니까 개념이 많이 헷갈려서 간단하게 이진 트리에 대해서 정리하면서 JAVA로 구현해 보려고 한다. 

 

아래 블로그의 그림만 가져다 쓰려고 합니다. 이 공간은 제가 공부한 것을 정리하는 공간입니다. 

http://logonluv.blogspot.com/2015/02/datastructure-tree.html

트리와 이진트리(Binaty Tree)의 설명과 구현 - [형강좌 자료구조 4편]

 

 

이진 트리(binary tree)의 정의

트리 중에서 가장 많이 쓰이는 트리가 이진트리이다. 모든 노드가 2개의 서브 트리를 가지고 있는 트리를 이진 트리(binary tree) 라고 한다. 서브트리는 공집합일 수 있다. 따라서 이진트리의 노드에는 최대 2개까지의 자식 노드가 존재할 수 있고 모든 노드의 차수가 2 이하가 된다. (차수(degree)는 어떤 노드가 가지고 있는 자식 노드의 개수)

 

 

이진트리 

• 공집합이거나
• 루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합으로 정의된다. 이진트리의 서브트리들은 모두 이진트리여야 한다.

 

이진트리의 성질

• n개의 노드를 가진 이진트리는 정확하게 n-1개의 간선을 가진다. 그 이유는 이진트리에서의 노드는 루트를 제외하면 정확하게 하나의 부모노드를 가진다. 그리고 부모와 자식 간에는 정확하게 하나의 간선만이 존재한다.
• 높이가 h인 이진트리의 경우, 최소 h개의 노드를 가지며 최대 2의h제곱 -1개의 노드를 가진다.

 

 

위와 같은 사진의 트리는 이진트리의 종류 중에 하나이다. 

 

이런식으로 편향된 트리도 이진트리 중에 하나라는 것을 기억하자. 

 

이진트리의 분류

• 포화 이진 트리
• 완전 이진 트리
• 기타 이진 트리

 

1. 포화 이진트리 

트리의 각 레벨에 노드가 꽉 차있는 이진트리를 의미한다. 

 

위와 노드가 비어있는 곳이 없고 꽉 차있는 상태를 말한다.

 

 

2. 완전 이진트리 

높이가 k일 때 레벨 1부터 k-1까지는 노드가 모두 채워져 있고 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리이다.

 

위와 같이 왼쪽에서 부터 차례대로 노드가 배치되는 형태이다.

 

 

3. 기타 이진트리

기타 이진트리는 위의 두개의 특성을 제외하고 이진트리의 속성을 만족 시킨다면 다 기타 이진트리라고 할 수 있다.

 

 

 

그리고 이제 JAVA를 이용해서 이진트리를 구현을 해보겠다. ( 순회는 다음 글에서 정리해서 구현하려 한다 )

  
package Data_Structure;
 
public class TreeNode {
    Object data;
    TreeNode left;
    TreeNode right;
 
    public TreeNode(Object data){
        this.data = data;
        this.left = null;
        this.right = null;
    }
 
    public Object getData(){
        return this.data;
    }
}

 

public class LinkedTree {
    private TreeNode root;
 
    public TreeNode makeBT(TreeNode bt1, Object data, TreeNode bt2){
        TreeNode root = new TreeNode(data);
        root.left = bt1;
        root.right = bt2;
        return root;
    }
}

 

public class TreeTest {
    public static void main(String[] args){
        LinkedTree tree = new LinkedTree();
 
        TreeNode n7 = tree.makeBT(null,'D',null);
        TreeNode n6 = tree.makeBT(null,'C',null);
        TreeNode n5 = tree.makeBT(null,'B',null);
        TreeNode n4 = tree.makeBT(null,'A',null);
        TreeNode n3 = tree.makeBT(n6,'/',n7);
        TreeNode n2 = tree.makeBT(n4,'*',n5);
        TreeNode n1 = tree.makeBT(n2,'-',n3);
 
        System.out.println("preorder");
        tree.preorder(n1);
        System.out.println();
        System.out.println("inroder");
        tree.inorder(n1);
        System.out.println();
        System.out.println("postorder");
        tree.postorder(n1);
    }
}