비선형 데이터구조, 트리(Tree) #4 이진 트리의 순회 및 표현식

이전글

https://yonghwankim-dev.tistory.com/116?category=974118 

비선형 데이터구조, 트리(Tree) #3 이진 트리의 종류

 

개요

이전글에서는 이진트리의 종류에 대해서 알아보았습니다. 이번글에서는 이진 트리를 순회하는 방법 3가지와 이진 트리의 순회를 활용하여 예시로 복잡한 수식을 트리 형태로 표현해보겠습니다.

 

1. 이진 트리의 순회(Traversal)

이진 트리의 순회란 이진 트리의 노드들을 방문하는 것을 의미합니다. 순회에는 3가지 방법이 아래와 같이 존재합니다.

• 전위순회(Preorder Traversal)
• 중위순회(Inorder Traversal)
• 후위순회(Postorder Traversal)

전위순회(Preorder Traversal)

전위 순회란 루트 노드에서 시작하여 왼쪽 자식 노드에 갔다가 오른쪽 자식 노드로 가는 순회 방법입니다. 다른 모든 노드를 지나기 전에 루트 노드를 방문하기 때문에 이름이 전(pre)이 들어갑니다.

1. 루트 노드(root node) 방문
2. 왼쪽 자식 노드(left child node) 방문
3. 오른쪽 자식 노드(right child node) 방문

중위 순회(Inorder Traversal)

중위 순회는 왼쪽 자식 노드에서 시작하여 루트 노드에 방문했다가 오른쪽 자식 노드로 가는 순회방법입니다.

1. 왼쪽 자식 노드(left child node) 방문
2. 루트 노드(root node) 방문
3. 오른쪽 자식 노드(right child node) 방문

후위 순회(Postorder Traversal)

후위 순회는 왼쪽 자식 노드에서 시작하여 오른쪽 자식 노드에 방문했다가 루트 노드로 가는 순회방법입니다.

1. 왼쪽 자식 노드(left child node) 방문
2. 오른쪽 자식 노드(right child node) 방문
3. 루트 노드(root node) 방문

 

순회(Traversal)의 예시

아래 그림은 전위, 중위, 후위 순회의 예시로 사용될 이진 트리입니다.

전위 순회(Preorder Traversal) : 1->2->4->5->3->6->7

중위 순회(Inorder Traversal) : 4->2->5->1->6->3->7

후위 순회(Postorder Traversal) : 4->5->2->6->7->3->1

 

2. 이진 트리의 표현

표현식 트리를 활용하여 굉장히 복잡한 식도 트리 형식으로 표현할 수 있습니다.

 

예를 들어 아래의 그림처럼 "2*3"이라는 수식을 트리 형태로 표현할 수 있습니다.

중위 표기식 : 2 * 3

후위 표기식 : 2 3 *

 

중위 표기식 : (((22 / 11) + 3) * (6 + 5)) - 50

후위 표기식 : 22 11 / 3 + 6 5 + * 50 -

 

복잡한 식을 후위 표기식으로 표현하였을 때의 장점

중위 표기식은 괄호와 연산자 우선순위를 고려해야 하므로, 수식을 왼쪽부터 차례대로 계산할 수 없습니다. 반면에 후위 표기식은 괄호가 필요 없어서 수식을 읽으면서 바로 연산이 가능하기 때문에 컴퓨터가 연산하기 더 편합니다.

 

References

source code : https://github.com/yonghwankim-dev/DataStruct/tree/main/Tree/BT/Implement
[부스트코스] 자바로 구현하고 배우는 자료구조