이진 트리와 순회 방법

 이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조입니다. 이진 트리는 많은 알고리즘에서 사용되며, 특히 검색 알고리즘에서 자주 사용됩니다.

 

이진 트리는 각 노드(Node)가 데이터와 두 개의 포인터(left, right)를 가지며, 이 포인터를 통해 자식 노드를 가리킵니다. 트리의 가장 위쪽에 위치한 노드를 루트 노드(Root Node)라고 하며, 가장 아래쪽에 있는 노드를 리프 노드(Leaf Node)라고 합니다.

 

이진 트리는 여러 가지 방법으로 순회할 수 있습니다. 대표적인 순회 방법으로는 전위 순회(Preorder Traversal), 중위 순회(Inorder Traversal), 후위 순회(Postorder Traversal)가 있습니다.다음은 이진 트리의 한 예시입니다.

 

 

이진 트리의 노드를 다음과 같이 정의합니다.

 

 

 

1. 전위 순회

 

 전위 순회는 루트 노드를 먼저 방문하고, 왼쪽 자식 노드를 방문한 후에 오른쪽 자식 노드를 방문하는 순서로 순회합니다. 즉, 루트-왼쪽-오른쪽 순서로 방문합니다. 

위의 예시 이진 트리를 전위 순회하면 다음과 같은 순서로 노드를 방문합니다.

 

아래는 전위 순회를 구현한 자바 코드입니다.

 

 

 

2. 중위 순회

 

 중위 순회는 왼쪽 자식 노드를 방문 한 후에 루트 노드를 방문하고, 오른쪽 자식 노드를 방문하는 순서로 순회합니다. 즉, 왼쪽-루트-오른쪽 순서로 방문합니다.

 

위의 예시 이진 트리를 중위 순회하면 다음과 같은 순서로 노드를 방문합니다.

 

위는 중위 순회를 구현한 자바 코드입니다.

 

 

3. 후위 순회

 

 후위 순회는 왼쪽 자식 노드를 방문한 후에 오른쪽 자식 노드를 방문하고, 마지막으로 루트 노드를 방문하는 순서로 순회합니다. 즉, 왼쪽-오른쪽-루트 순서로 방문합니다.

 

위의 예시 이진 트리를 후위 순회하면 다음과 같은 순서로 노드를 방문합니다.

 

위는 후위 순회를 구현한 자바 코드입니다.

 

 

 

따라서 순회의 방법에 따른 순서는 아래 그림처럼 나타나게 됩니다.