[알고리즘] 14. 이진 트리의 구현과 순회(Traversal) 방식

1. 이진트리(Binary Tree)
: 트리 자료구조를 활용한 대표적인 예시. 데이터의 탐색 속도 증진을 위해 사용하는 구조
기본적으로 가장 많이 사용되는 비선형 자료구조.
실제로 트리를 제대로 구현하기 위해서는 포인터(Pointer)를 사용해야 한다.
포인터를 이용하면 특정한 Root에서 자식Node로 접근할 수 있다.

* 포인터를 사용해서 왼쪽 자식과 오른쪽 자식을 가리킬 수 있도록 하는 이유
-> 완전 이진 트리가 아닌 이진 트리는 배열로 표현하기 어렵기 때문. 유동적으로 트리 자료구조를 활용할 수 있다.

2. 이진트리에서 데이터를 탐색하는 방법

 

1) 전위 순회 (Preorder Traversal) : 하나의 노드에 방문했을 때 다음의 순서를 따른다
- 먼저 자기 자신을 처리한다
- 왼쪽 자식을 방문한다
- 오른쪽 자식을 방문한다


2) 중위 순회 (Inorder Treaversal) : 하나의 노드에 방문했을 때 다음의 순서를 따른다
- 왼쪽 자식을 방문한다
- 먼저 자기 자신을 처리한다
- 오른쪽 자식을 방문한다

3) 후위 순회 (Postorder Traversal)
- 왼쪽 자식을 방문한다
- 오른쪽 자식을 방문한다
- 먼저 자기 자신을 처리한