자료구조 - 이진 트리(전위, 중위, 후위, 레벨 순회)
계산기를 구현하던 중 이진 탐색 트리 순회가 필요해져 내용을 정리해보려 한다.
용어 정리
내용에 대해 알아보기 전에 트리와 관련된 용어를 알아보자.
아래와 같은 모양을 가진 트리가 있다고 했을 때,
A, B, C, D, ... 각각을 노드(Node)라고 하며 최상위에 있는 A를 루트(Root)라고 한다.
각 노드는 간선(Edge)으로 이어져 있다.
루트 아래의 노드들은 A의 서브트리라고 하는데
예를 들어 노란 상자가 A의 서브트리이며 해당 서브트리의 루트는 B이다.
해당 서브노드에서 B는 D, E, F의 부모노드(Parent Node), D, E, F는 B의 자식노드(Children Node)이다.
층수가 내려갈수록 레벨(Level)이 1씩 증가하는데,
같은 레벨의 노드들을 형제노드 혹은 형제관계에 있다고 한다. B, C는 형제관계이다.
자식노드를 가지고 있지 않은 노드를 단말노드(Terminal Node) 혹은 리프(Leaf Node)라고 하며
단말노드가 아닌 노드는 비단말노드(Nonterminal Node)이다.
노드의 차수는 한 노드가 가지고 있는 자식 노드의 개수이다. C의 차수는 2(G, H)이다.
트리의 차수는 트리가 가지고 있는 가장 큰 차수 값이다. B의 자식 노드가 가장 많으므로 이 트리의 차수는 3이다.
이진트리
이진트리는 모든 노드가 2개의 서브트리를 가지고 있는 구조이다. 서브트리는 공집합일 수 있다.
위의 트리가 이진트리인데, 각 노드가 2개의 서브트리(공집합 포함)를 가지고 있는 모습이다.
이진트리의 특징은 아래와 같다.
- n개의 노드를 가진 이진트리는 n-1개의 간선을 가진다.
- 높이가 h인 이진트리는 최소 h개 ~ 최대 2h-1개의 노드를 가진다.
- 노드가 n개인 이진트리는 최소 ⌈log2(n+1)⌉ ~ 최대 n의 높이를 가진다. (⌈x⌉는 올림 기호)
이진트리도 형태에 따라 분류를 할 수 있는데, 구분은 아래와 같다.
포화 이진트리: 각 레벨에 모든 노드가 찬 이진트리
완전 이진트리: 노드가 왼쪽에서 오른쪽으로 순서대로 채워진 이진트리
기타 이진트리: 위 두 이진트리가 아닌 이진트리
포화 이진트리는 높이가 k일 때 2k -1개의 노드를 가진다. 포화 이진트리는 항상 완전 이진트리이다.
이진트리의 순회
이제 이 글의 주 목적인 순회에 대해 알아보자.
전위, 중위, 후위, 레벨 순회 중 먼저 전위(preorder), 중위(inorder), 후위(postorder)에 대해 알아보자.
다음과 같이 트리가 있다고 할 때
전위: A-L-R(루트 - 왼쪽 서브트리 - 오른쪽 서브트리)
중위: L-A-R(왼쪽 서브트리 - 루트 - 오른쪽 서브트리)
후위: L-R-A(왼쪽 서브트리 - 오른쪽 서브트리 - 루트) 순서이다.
아래 트리를 예로 들면
전위: A - B - D - E - C - F - G
중위: D - B - E - A - F - C - G
후위: D - E - B - F - G - C - A
이다.
레벨 순회는 레벨 순으로 노드를 순회하는 것이다.
동작이 어렵지 않다.
구현
이제 간단하게 순회를 구현해 보자.
먼저 전위, 중위, 후위 순회는 재귀를 활용하면 정말 간단하게 구현할 수 있다.
순회에 따른 출력 순서를 보는 것이 목적이기 때문에 트리의 여러 기능은 구현하지 않았다.
먼저 Node 클래스이다.
class Node {
Node left;
Node right;
int value;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}좌, 우 자식노드와의 연결을 위한 left, right 변수와 값을 담기 위한 value 변수를 생성했다.
다음은 이진트리를 만들었다.
public static void main(String[] args) {
Node node7 = new Node(7, null, null);
Node node6 = new Node(6, null, null);
Node node5 = new Node(5, null, null);
Node node4 = new Node(4, null, null);
Node node3 = new Node(3, node6, node7);
Node node2 = new Node(2, node4, node5);
Node node1 = new Node(1, node2, node3);
System.out.printf("전위 순회: ");
preorder(node1);
System.out.printf("\n\n중위 순회: ");
inorder(node1);
System.out.printf("\n\n후위 순회: ");
postorder(node1);
}트리의 모습은 아래와 같다.
이제 순회 부분을 확인해 보자.
static void preorder(Node root) {
if(root != null) {
System.out.print(root.value + " ");
preorder(root.left);
preorder(root.right);
}
}
static void inorder(Node root) {
if(root != null) {
inorder(root.left);
System.out.print(root.value + " ");
inorder(root.right);
}
}
static void postorder(Node root) {
if(root != null) {
postorder(root.left);
postorder(root.right);
System.out.print(root.value + " ");
}
}각각 전위, 중위, 후위 순회이다. 재귀를 활용해 간단히 구현할 수 있다.
출력 결과를 확인해 보면 다음과 같다.
올바르게 나오는 것을 확인할 수 있다.
아래는 전체 코드이다.
class Node {
Node left;
Node right;
int value;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
class BinaryTree {
public static void main(String[] args) {
Node node7 = new Node(7, null, null);
Node node6 = new Node(6, null, null);
Node node5 = new Node(5, null, null);
Node node4 = new Node(4, null, null);
Node node3 = new Node(3, node6, node7);
Node node2 = new Node(2, node4, node5);
Node node1 = new Node(1, node2, node3);
System.out.printf("전위 순회: ");
preorder(node1);
System.out.printf("\n\n중위 순회: ");
inorder(node1);
System.out.printf("\n\n후위 순회: ");
postorder(node1);
}
static void inorder(Node root) {
if(root != null) {
inorder(root.left);
System.out.print(root.value + " ");
inorder(root.right);
}
}
static void preorder(Node root) {
if(root != null) {
System.out.print(root.value + " ");
preorder(root.left);
preorder(root.right);
}
}
static void postorder(Node root) {
if(root != null) {
postorder(root.left);
postorder(root.right);
System.out.print(root.value + " ");
}
}
}
레벨 순회는 큐를 이용해 구현한다. 아래 그림을 보면 이해하기 쉽다.
먼저 1을 출력하면서 자식노드인 2, 3을 큐에 담는다.
큐에 담긴 2를 출력하면서 자식노드인 4, 5를 큐에 담는다.
큐에 담긴 3을 출력하면서 자식노드인 6, 7을 큐에 담는다.
큐에 담긴 4를 출력하는데 자식노드가 없으므로 그냥 진행한다.
이런 식으로 진행하면 레벨 순회가 가능하다. 코드는 아래와 같다.
static void level(Node root) {
Queue <Node> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()) {
Node node = queue.poll();
System.out.print(node.value + " ");
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
}queue를 하나 생성해 root를 먼저 넣고 자식 노드를 왼쪽 - 오른쪽 순으로 큐에 담았다.
출력 결과는 아래와 같다.
