13. 선형자료구조와 비선형자료구조
선형자료구조는 말 그대로 data가 선형으로 구성되어있는 형태를 일컫는다.
대표적인 형태로 배열, stack, queue 등이 존재한다.
비선형자료구조 역시 말 그대로 data가 비선형으로 구성되어있는 형태를 말하는데, 쉽게 말하면 data들이 얽히고 설킨 구조를 의미한다.
대표적인 형태로 graph(계층적이지않고 노드 연결이 비규칙적), tree(계층적이고 노드 연결이 규칙적, 자식노드가 최대 2개)가 존재한다.
13-1. 이진트리
이진트리는 비선형자료구조의 일종으로, 부모노드의 자식노드가 최대 2개인 계층적 자료형태를 만족하는 구조를 일컫는다.
tree는 기본적으로 수행속도가 빠른데, data 탐색속도를 증진하기위해 사용하는 구조이다.
완전이진트리와는 달리 이진트리는 불필요한 데이터 공간 및 배열의 낭비를 방지하기위해, 포인터를 통해 특정 root(node) 및 자식노드로 접근한다(C언어의 경우, python은 포인터를 이용하지 않기 때문에 다른 방법으로 접근).
13-2. 이진트리탐색
이진트리탐색은 순회라고도 하며, 재귀적으로 수행한다.
전위순회(preorder Traversal)
한 노드에 방문했을때
- 자기 자신을 먼저 처리한다.
- 그 후 왼쪽 자식노드를 처리한다.
- 마지막으로 오른쪽 자식노드를 처리한다.
중위순회(Inorder Traversal)
한 노드에 방문했을때
- 왼쪽 자식노드를 먼저 처리한다.
- 그 후 자기자신을 처리한다.
- 마지막으로 오른쪽 자식노드를 처리한다.
후위순회
- 왼쪽 자식노드를 먼저 처리한다.
- 그 후 오른쪽 자식노드를 처리한다.
- 마지막으로 자기 자신을 처리한다.
13-3. 순회방법 별 데이터 정렬
위 (완전)이진트리를 순회하였을때 얻는 결과는 아래와 같다.
- 전위순회 : 1 2 4 8 9 5 10 11 3 6 12 13 ..
- 중위순회 : 8 4 9 2 10 5 11 1 12 6 13 3 14 ....
- 후위순회 : 8 9 4 10 11 5 2 12 13 6 ...
