지금까지 배운 배열 ,연결리스트, 스택과 큐는 모두 선형 자료구조였다. 앞으로 배울 트리와 그래프는 그렇지 않다.

트리는 연결 리스트와 유사한 데이터구조이지만 하나의 노드가 여러개의 노드를 가리킨다. 그렇게 트리는 계층적 속성을 표현할 수 있게 된다. (연결리스트나 다른 선형 자료구조의 경우 계층대신 순서가 잘 표현)

용어

루트 : 부모가 없는 노드 (레벨이 0인 노드) 리프 leaf : 자식이 없는 노드 조상 ancestor : 루트부터 해당 노드까지의 경로에 위치한 노드 자손 descendant : 해당 노드 와 간선으로 이루어진 하위 노드들 형제 sibling : 같은 부모를 가진 노드들

노드의 크기 size : 자기와 모든 자손노드의 수 부속 트리 sub tree : 경사 트리 skew tree : 트리의 모든 노드가 오직 한개의 자식만을 가질 때

이진 트리

트리중에서 가장 많이 사용되는 트리 형태. 모든 노드가 자식이 최대 두 개의 자식을 가질 때 이진 트리라고 한다.

엄격한 strict 이진 트리 : 모든 노드가 두 개의 자식을 가지거나 아예 가지지 않고있는 경우

포화 full 이진 트리 : 모든 노드가 두 개의 자식을 가지고, 리프 노드들이 모두 같은 레벨에 있는 경우

완전 complete 이진 트리 : 마지막 레벨을 제외한 모든 레벨의 노드가 채워져 있고, 마지막 레벨의 노드들은 왼쪽부터 채워져 있는 경우

이진 트리의 속성

구조

노드는 총 세 부분으로 이루어져야 한다. 데이터를 담는 변수와, 다음 레벨의 노드들을 가리키는 포인터 왼쪽과 오른쪽 총 두 개.

연산

삽입, 삭제 : 검색 : 특정 데이터가 있는지 확인하기 탐색 : 모든 데이터 출력하기 높이 구하기 최소 공통 부모 찾기

적용 사례

컴파일러에서 사용하는 수식 트리 데이터 압축 알고리즘에서 사용되는 허프만 코딩 트리 이진 검색 트리 Binary Search Tree BST 우선순위 큐 Priority Queue PQ

탐색 Tree Traversal

트리를 처리하기 위해서는 트리를 탐색하는 방법이 필요하다. 지금까지 배운 선형 자료구조에서 탐색이란 앞에서부터 진행하든 뒤에서부터 진행하든 배치된 순서를 따르면 됐었지만 트리에서는 순서가 존재하지 않기에 개발자가 탐색할 순서를 지정해줘야한다.

전위 Preorder 탐색 DLR : 부모 노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리 중위 Inorder 탐색 LDR : 왼쪽 서브트리 -> 부모 노드 -> 오른쪽 서브트리 후위 Postorder 탐색 LRD : 왼쪽 서브트리 -> 오른쪽 서브트리 -> 부모 노드

보니까 전위, 중위, 후위를 구분하는건 루트를 언제 처리할껀지를 의미하는것이고 서브트리들 끼리는 무조건 왼쪽을 먼저 처리하고 오른쪽을 나중에 처리한다. (?) -> 왼 -> (?) -> 오 -> (?) 대충 이런 모양세.

그리고 재귀적이라는 특징이 있다고 한다. 노드를 옮겨가며 같은 DLR(혹은 LDR이나 LRD)을 반복한다는 의미.