[자료구조] 이진 트리(Binary Tree) 개념과 구현

1. 트리

트리(Tree)란 비선형 자료구조 중에서 자료들 간에 계층관계를 가진 계층형 자료구조(Hierarchical Data Structure)를 말합니다.

트리

· 노드(Node): 트리를 구성하는 원소(자료)

· 간선(Edge): 노드를 연결하는 선

· 차수(Dgree): 자식 노드의 수

· 높이(Height): 루트에서 해당 노드에 이르는 경로에 있는 간선의 수

· 루트 노드(Root Node): 트리의 시작 노드

· 형제 노드(Sibling Node): 같은 부모 노드의 자식노드들

· 조상 노드(Ancestor Node): 한 노드에서 간선을 따라 루트 노드까지 이르는 경로에 있는 노드들

· 자손 노드(Descendant Node): 한 노드의 서브 트리에 있는 노드들

· 단말 또는 리프 노드(Leaf Node): 자식이 없는 노드

2. 이진 트리

이진 트리(Binary Tree)란 모든 노드의 차수를 2 이하로 정하여 전체 트리의 차수가 2 이하가 되도록 만든 트리입니다.

이진 트리

· 이진 트리는 왼쪽 자식 노드와 오른쪽 자식 노드 2개만을 가질 수 있으며, 공백 노드도 이진 트리의 노드로 취급합니다.

 

· 이진 트리에 있는 모든 노드는 왼쪽 자식 노드를 루트로 하는 왼쪽 서브 트리와 오른쪽 자식 노드를 루트로 하는 오른쪽 서브 트리를 가집니다. 그리고 이진 트리의 서브 트리들 모두 이진 트리여야 합니다.

3. 이진 트리의 특징

① n개의 노드를 가진 이진 트리는 항상 (n-1)개의 간선을 갖습니다.

루트 노드 이외의 모든 노드는 한 개의 부모 노드를 가지고 있기 때문에 부모 노드와 연결하는 한 개의 간선을 갖습니다. 따라서 n개의 노드로 구성된 이진 트리에서 루트 노드를 제외한 나머지 노드의 개수가 (n-1)개이므로 (n-1)개의 간선을 갖습니다.

 

② 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 (h+1)개, 최대 개수는 (2^(h+1) -1)개입니다.

이진 트리의 높이가 h가 되려면 한 레벨에 최소한 한 개의 노드가 있어야 하므로 높이가 h인 이진 트리의 최소 노드의 개수는 (h+1)개가 됩니다.

 

하나의 노드는 최대 2개의 자식 노드를 가질 수 있기 때문에 레벨 i에서 노드의 최대 개수는 2^i가 됩니다. 따라서 높이가 h인 이진 트리에서 최대 노드의 개수는 (2^(h+1) -1)개가 됩니다.

4. 이진 트리의 종류

① 포화 이진 트리

모든 레벨에 노드가 꽉 차있는 포화 상태의 이진 트리입니다. 즉 이진 트리의 높이가 h일 때 (2^(h+1) -1)개의 노드를 갖는 이진 트리를 말합니다.

포화 이진 트리

② 완전 이진 트리

높이가 h, 노드의 개수가 n개일 때(단, n < 2^(h+1) -1), 노드의 위치가 포화 이진 트리의 노드 1번 부터 n번까지의 위치와 완전히 일치하는 이진 트리입니다. 따라서 (n+1)번 부터 (2^(h+1) -1)번까지는 공백 노드가 됩니다.

완전 이진 트리

③ 편향 이진 트리

이진 트리 중에서 최소 개수의 노드를 가지면서 왼쪽이나 오른쪽 서브 트리만 가지고 있는 트리입니다. 즉 이진 트리의 높이가 h일 때 (h+1)개의 노드를 가지면서 한 쪽으로 치우친 이진 트리를 말합니다.

왼쪽 편향 이진 트리와 오른쪽 편향 이진 트리

5. 이진 트리의 구현

· 순차 자료구조 방식

1차원 배열에서 인덱스 계산을 간단히 하기 위해서 인덱스 0번은 사용하지 않고 비워두고, 인덱스 1번에 루트를 저장합니다.

완전 이진 트리의 배열 표현

1차원 배열을 사용하여 이진 트리를 구현하면 각 노드의 부모 노드와 자식 노드가 저장된 배열 인덱스에 대하여 일정한 규칙을 찾을 수 있습니다.

노드	인덱스	조건
노드 i의 부모 노드	i / 2	i > 1
노드 i의 왼쪽 자식 노드	i * 2	(i * 2) <= n
노드 i의 오른쪽 자식 노드	(i * 2) + 1	(i * 2) + 1 <= n

 

· 연결 자료구조 방식

배열을 이용한 이진 트리의 구현은 인덱스 규칙에 따라 부모 노드와 자식 노드를 찾기 쉽다는 장점이 있습니다. 하지만 메모리 공간의 사용에 있어 완전 이진 트리의 경우에는 최적의 공간 사용이 되지만, 편향 이진 트리의 경우 많은 공간이 낭비됩니다. 따라서 메모리 낭비 문제와 삽입 · 삭제 연산이 비효율적인 순차 자료구조 방식 보다는 연결 자료구조 방식을 많이 사용합니다.

 

이진 트리의 노드는 왼쪽 자식 노드와 오른쪽 자식 노드를 연결해야 하므로 데이터를 저장하는 데이터 필드, 왼쪽 자식 노드를 연결하는 왼쪽 링크 필드와 오른쪽 자식 노드를 연결하는 오른쪽 링크 필드로 구성된 참조 변수를 사용해야 합니다.

 

public class TreeNode {
	private 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;
	}
}

6. 이진 트리의 순회

이진 트리에 있는 모든 노드를 한번씩 모두 방문하여 노드가 가지고 있는 데이터를 처리하는 것을 순회라고 합니다. 선형 자료구조는 순회하는 방법이 한 가지였지만, 트리는 계층적인 구조를 가지고 있기 때문에 여러 가지 순회 방법이 있습니다.

 

하나의 노드에서 순회를 위해 수행할 수 있는 작업은 (1) 현재 노드를 방문하여 데이터를 읽는 작업, (2) 현재 노드의 왼쪽 서브 트리로 이동하는 작업, (3) 현재 노드의 오른쪽 서브 트리로 이동하는 작업이 있습니다. 그리고 서브 트리를 순회하는 순서는 항상 왼쪽 서브 트리를 먼저 방문하고, 그 후에 오른쪽 서브 트리를 방문하는 것으로 합니다.

 

따라서 현재 노드를 방문하는 순서에 따라 전위 순회, 중위 순회, 후위 순회로 나눌 수 있습니다.

 

· 전위 순회(Preorder Traversal)

현재 노드를 방문 → 왼쪽 서브 트리 방문 → 오른쪽 서브 트리 방문

preorder(T)
    if(T != null) then{
    	visit T.data;
        preorder(T.left);
        preorder(T.right);
    }
end preorder()

 

· 중위 순회(Inorder Traversal)

왼쪽 서브 트리 방문 → 현재 노드를 방문 → 오른쪽 서브 트리 방문

inorder(T)
    if(T != null) then {
        inorder(T.left);
        visit T.data;
        inorder(T.right);
    }
end inorder()

 

· 후위 순회(Postorder Traversal)

왼쪽 서브 트리 방문 → 오른쪽 서브 트리 방문 → 현재 노드를 방문

postorder(T)
    if(T != null) then {
        postorder(T.left);
        postorder(T.right);
        visit T.data;
    }
end postorder(T)

7. 이진 트리 소스 코드

· TreeNode

public class TreeNode {
	private 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;
	}
}

 

· LinkedTree

public class LinkedTree {

	// 이진 트리 노드 생성
	public TreeNode makeBT(TreeNode left, Object data, TreeNode right) {
		TreeNode newNode = new TreeNode(data);
		newNode.left = left;
		newNode.right = right;
		return newNode;
	}

	// 전위 순회
	public void preorder(TreeNode node) {
		if (node != null) {
			System.out.printf("%c", node.getData());
			preorder(node.left);
			preorder(node.right);
		}
	}

	// 중위 순회
	public void inorder(TreeNode node) {
		if (node != null) {
			inorder(node.left);
			System.out.printf("%c", node.getData());
			inorder(node.right);
		}
	}

	// 후위 순회
	public void postorder(TreeNode node) {
		if (node != null) {
			postorder(node.left);
			postorder(node.right);
			System.out.printf("%c", node.getData());
		}
	}
}

 

· MainForLinkedTree

public class MainForLinkedTree {
	public static void main(String[] args) {
		LinkedTree t = new LinkedTree();

		TreeNode n7 = t.makeBT(null, 'D', null);
		TreeNode n6 = t.makeBT(null, 'C', null);
		TreeNode n5 = t.makeBT(null, 'B', null);
		TreeNode n4 = t.makeBT(null, 'A', null);
		TreeNode n3 = t.makeBT(n6, '-', n7);
		TreeNode n2 = t.makeBT(n4, '+', n5);
		TreeNode n1 = t.makeBT(n2, '*', n3);

		// 전위 순회
		System.out.printf("preorder: ");
		t.preorder(n1);

		// 중위 순회
		System.out.printf("\ninorder: ");
		t.inorder(n1);

		// 후위 순회
		System.out.printf("\npostorder: ");
		t.postorder(n1);
	}
}

 

· 실행 결과