[자료구조 트리] 이진 트리(Binary Tree)

  이진 트리(Binary Tree)는 각 노드의 자식 수가 2 이하인 트리를 의미합니다. 데이터의 구조적인 관계를 잘 반영하고, 효율적인 삽입과 탐색을 가능하게 하며, 이진 트리의 서브트리를 다른 이진 트리의 서브트리와 교환하기가 쉽습니다.

 

이미지  출처: 위키백과, 이진 트리 항목

 

  이진 트리에는 두 종류의 특별한 형태를 가진 트리가 존재합니다. 모든 이파리의 깊이가 같고 각 내부의 노드가 2개의 자식을 가지는 포화 이진 트리(Perfect Binary Tree)와 마지막 레벨을 제외한 각 레벨이 노드들로 꽉 차있고, 마지막 레벨에는 노드들이 왼쪽부터 빠짐없이 채워진 완전 이진 트리(Complete Binary Tree)입니다.

  완전 이진 트리를 저장하기 위해 배열을 사용하는 경우, 레퍼런스를 저장할 메모리 공간이 필요 없으므로 매우 효율적입니다. 하지만 편향(Skewed) 이진 트리를 배열에 저장하는 경우, 배열에 빈 공간이 생기고 트리의 높이가 커질 수록 빈 공간이 차지하는 자리가 점차 넓어지므로 메모리 낭비가 심해집니다.

 

이미지 출처: 위키백과, 이진 탐색 트리 항목

  이진 트리에서 수행되는 기본 연산들은 트리를 순회(Traversal)하며 이루어집니다. 이진 트리를 순회하는 방식은 다음 네 가지로 나뉩니다.

순회	방법	순서
전위 순회 (Preorder Traversal)	자신, 왼쪽 자손, 오른쪽 자손 순서로 방문	8, 3, 1, 6, 4, 7, 10, 14, 13
중위 순회 (Inorder Traversal)	왼쪽 자손, 자신, 오른쪽 자손 순서로 방문	1, 3, 4, 6, 7, 8, 10, 13, 14
후위 순회 (Postorder Traversal)	왼쪽 자손, 오른쪽 자손, 자신 순서로 방문	1, 4, 7, 6, 3, 13, 14, 10, 8
레벨 순회 (Levelorder Traversal)	레벨 순서로 방문, 너비 우선 순회(Breadth-First traversal)	8, 3, 10, 1, 6, 14, 4, 7, 13

 

  이진 트리 구현 코드(연결 리스트)

class BinaryTree {
	Node head;
    BinaryTree(int[] array) {
    	Node[] nodes = new Node[array.length];
    	for (int i = 0; i < array.lengthl i++) {
    		nodes[i] = new Node(array[i], null, null);
        }
        for (int i = 0; i < array.length; i++) {
        	int left = 2 * i + 1;
            int right = 2 * i + 2;
            if (left < array.length) {
            	nodes[i].left = nodes[left];
            }
            if (right < array.length) {
            	nodes[i].right = nodes[right];
            }
        }
        this.head = nodes[0];
    }
}

 

  전위 순회 구현 코드

public void preorder(Node node) {
	if (node != null) {
    	System.out.print(node.data + " ");
        preorder(node.left());
        preorder(node.right());
    }
}

 

  중위 순회 구현 코드

public void inorder(Node node) {
	if (node != null) {
    	inorder(node.left);
        System.out.print(node.data + " ");
        inorder(n.right);
    }
}

 

  후위 순회 구현 코드

public void postorder(Node node) {
	if (node != null) {
    	postorder(node.left);
        postorder(node.right);
        System.out.print(node.data + " ");
    }
}

 

  레벨 순회 구현 코드

public void levelorder(Node node) {
	Queue<Node> queue = new LinkedList<>();
    queue.add(node);
    while (!queue.isEmpty()) {
    	Node cur = queue.remove();
        System.out.print(cur.data + " ");
        if (cur.left != null) {
        	queue.add(cur.left);
        }
        if (cur.right != null) {
        	queue.add(cur.right);
        }
    }
}

 

  ※ "자바와 함께하는 자료구조의 이해"라는 책을 참고하여 쓴 게시글입니다. 책에는 없는 내용을 추가하여 작성된 부분이 있습니다. 문제가 되거나 부정확한 부분이 있다면 알려주시면 감사하겠습니다.

  ※ 책은 게시글보다 정확한 내용을 담고 있으며 코드, 그림, 예제를 이용하여 개념을 자세히 설명합니다.