[Trees]25. Binary Trees Traversal(이진 트리 탐색)

목차

1. Inorder Traversal(중위 순회)

2. Print Arithmetic Expressions

3. Evaluate Arithmetic Expressions

2. Euler Tour Traversal(오일러 탐색)

 

1. Inorder Traversal(중위 순회)

 Inorder Traversal(중위 순회)는 해당 node가 external이 아니라면,

1) 왼쪽 자식의 node를 방문한 후

2) 현재 node를 print

3) 그 후 오른쪽 자식의 node를 방문함

 위의 과정을 거치는 방법을 말합니다.

 

이는 실제로 이진 탐색 트리를 그리는 경우, 활용될 수 있습니다.

- x(v) = inorder traversal 순위

- y(v) = node v의 높이

 

2. Print Arithmetic Expressions

 

 이전 게시물에서, 이진 트리를 사용하여 수식을 표현할 수 있다는 게시물을 작성한 적이 있습니다. 이는 이진 트리 형식으로 저장되어있는 수식을, 일반적인 방법으로 다시 출력할 수 있게 만드는 방법입니다. 이는 1번의 중위 순회에서, 중간에 괄호를 추가한 방식으로 생각하면 됩니다.

 

3. Evaluate Arithmetic Expressions

 

 Evaluate Arithmetic Expressions는 2번과 다르게, 이진 트리에 저장되어 있는 수식을 나열하는 것이 아닌, 실제로 계산하여 결과 값을 출력하기 위한 방법입니다. 이는 external node에는 피연산자, internal node에는 연산자만 포함되어 있다는 성질을 이용하여 계산을 하는 방식입니다.

 

4. Euler Tour Traversal(오일러 탐색)

 Euler Tour Traversal(오일러 탐색)은 많이 사용하는 방법은 아니지만, 위의 그림과 같이 왼쪽부터 태두리를 따라서 쭉 돌아보는 것을 말합니다.