이진트리의 순회

Summary

트리는 어렵지만 알고리즘 문제에서 자주 등장하는 자료구조입니다. 그 중 이진 트리는 직접 구현할 일은 자주 없지만, 시간복잡도를 줄이기위해 라이브러리에서 내부적으로 많이 사용하는 트리입니다. 대표적으로 이진 탐색 트리는 자료의 효율적인 검색에 쓰이며, 완전 이진 트리는 힙(heap)에 사용합니다. 복잡한 사용방법보다 이진 트리에 대한 이해가 필요하다고 생각했습니다. 이진트리에 대한 간단한 정의에 대해서 알아보고, 순회 알고리즘을 살펴봤습니다. 그리고 알고리즘 문제를 통해 트리의 순회에 대해서 잘 이해하고 있는지 확인했습니다.

Introduction

트리에서 탐색하는 것은 배열이나 연결리스트처럼 선형으로 구성된 자료구조에서 탐색하는 것보다 훨씬 까다롭다. 또한, 최악의 수행 시간과 평균적 수행시간이 매우 크게 바뀔 수 있어서, 알고리즘을 살펴볼 때에는 두 가지 측면 모두를 반드시 따져봐야 한다.

여러가지 트리 중에서 이진 트리(Binary tree)는 각 노드가 최대 두 개의 자식을 갖는 트리를 말합니다. 이진트리를 순회하는 방법은 세가지가 있습니다.

• Pre-order traversal, 전위순회
• In-order traversal, 중위순회
• Post-order traversal, 후위순회

실제 구현은 구현하는 언어에 따라 다릅니다. 하지만 대부분 클래스틑 이용하여 노드와 트리를 구현합니다. 그리고 재귀적으로 순회 알고리즘을 구현합니다.

재귀는 어떤 문제를 해결하는 과정에서 자신과 똑같지만 크기가 다른 문제를 발견하고 이들의 관계를 파악함으로써 문제 해결에 간명하명하게 접근하는 방식이다.

순회하는 방식이 모든 노드에서 같고, 노드를 지날수록 문제의 크기가 작아지므로, 재귀로 구현하기 적합합니다. 각 순회방법을 잘 이해하고 있는지 알고리즘 문제를 통해 살펴보도록 하겠습니다.

Background

트리의 개념

트리는 노드로 이루어진 자료구조입니다.

1. 트리는 하나의 루트 노드를 갖는다.
2. 루트 노드는 0개 이상의 자식 노드르를 갖는다.
3. 자식 노드 또한 0개 이상의 자식 노드를 가지고 있고, 이를 반복적으로 정의한다.

• 노드와 노드를 연결하는 간선이 있다.
• 트리에는 사이클이 없다.

What is traversal

##

Conclusion

Reference