이진트리는 컴퓨터 과학에서 아주 중요한 역할을 해 왔다.

많은 알고리즘이 이진트리를 이용하고 있으며, 이진트리의 또 다른 이용 역시 지금도 꾸준히 연구되고 있다.

이진트리를 순회하는 방법은 루트를 언제 출력하느냐에 따라 크게 세 가지로 나눌 수 있다.

첫 번째는 preorder 순회법으로,

트리의 루트를 먼저 출력한 뒤 재귀적으로 왼쪽 부트리와 오른쪽 부트리를 차례로 순회하는 방법이다.

두 번째는 inorder 순회법으로, 왼쪽 부트리를 순회한 뒤 루트를 출력하고, 그 다음에 오른쪽 부트리를 순회한다.

마지막 방법은 postorder 순회법으로, 왼쪽 부트리와 오른쪽 부트리를 먼저 순회하고 난 뒤 루트를 출력하는 것이다.

예를 들어, 아래의 이진트리를 위에서 설명한 세 가지 방법에 따라 순회하면 다음과 같은 결과를 얻을 수 있다.

트리를 preorder로 순회한 순서와 inorder로 순회한 순서가 주어지면,

그에 해당하는 이진트리를 만들어 내는 것이 가능하고, 조건을 만족하는 이진트리는 단 하나만 존재함이 알려져 있다. Preorder 순회 결과와 inorder 순회 결과를 바탕으로 postorder 순회 결과를 출력하자.

트리순회 timer 1s memory 1024MB

트리순회 1s 1024MB