트리(Tree)

• 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조.

트리 관련 용어

• 루트 노드(root node) : 부모가 없는 최상위 노드
• 단말 노드(leaf node) : 자식이 없는 노드
• 크기(size) : 트리에 포함된 모든 노드의 개수
• 깊이(depth) : 루트 노드부터의 거리
• 높이(heigh) : 깊이 중 최댓값
• 차수(degree) : 각 노드의 (자식 방향) 간선 개수
  • 트리의 크기가 N일 때, 전체 간선의 개수는 N-1 개 이다.

이진 탐색 트리(Binary Search Tree)

• 이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조의 일종
• 이진 탐색 트리의 특징 : 왼쪽 자식 노드< 부모 노드< 오른쪽 나식 노드
  • 부모 노드 보다 왼쪽 자식 노드가 작고 오른쪽 자식 노드가 크다.

트리의 순회(Tree Traversal)

• 트리 자료구조에 포함된 노드를 특정한 방법으로 한 번씩 방문하는 방법.
  • 트리의 정보를 시각적으로 확인 할 수 있다.
• 대표적인 트리 순회 방법
  • 전위 순회(preorder) : 루트를 먼저 방문 > 왼쪽 > 오른쪽
  • 중위 순회(inorder) : 왼쪽 자식을 방문한 뒤에 루트 방문 > 오른쪽
  • 후위 순회(postorder) : 왼쪽 자식 방문, 오른쪽 자식을 방문한 뒤 루트 방문