트리 구조 : 데이터 사이의 계층 관계를 표현한다
트리의 구조와 관련 용어
tree - node와 edge로 구성됨.
root - 가장 상위에 있는 노드
leaf - terminal node = external node
non-terminal node = internal node 비단말 노드
자식 - 아래쪽 노드 <-> 부모 parent 위쪽에 있는 노드
형제 - sibling 부모가 같은 노드
조상 - ancestor 가지를 따라가면 만나는 노드
자손 - descendant 아래로 내려가면서 만나는 모든 노드
레벨 - 루트에서 얼마나 떨어져 있는지 나타냄
차수 - degree 노드의 자식 수
높이 - height 리프 레벨의 최댓값
서브트리 - subtree - 자손으로 구성된 트리
빈 트리 - null tree
순서 트리와 무순서 트리 ordered tree / unordered tree
순서 트리의 검색
1) 너비 우선 검색 breadth-first search
폭 우선 검색, 가로 검색, 수평 검색
2) 깊이 우선 검색 depth-first search
세로 검색, 수직 검색
- 전위 순회 preorder : 노드 > 왼쪽 자식 > 오른쪽 자식
- 중위 순회 inorder : 왼쪽 자식 > 노드 > 오른쪽 자식
- 후위 순회 postorder : 왼쪽 자식 > 오른쪽 자식 > 노드 방문
'Computer Science > 자료구조' 카테고리의 다른 글
| [6.5] 프로그래머스 코딩테스트 연습 - 두개 뽑아서 더하기(1/100) (0) | 2021.06.05 |
|---|---|
| [6.3] 09-2 이진 트리와 이진 검색 트리 (0) | 2021.06.03 |
| [5.31] 08-2 포인터를 이용한 연결 리스트 (0) | 2021.05.31 |
| [5.30] 08-2 포인터를 이용한 연결 리스트 (0) | 2021.05.30 |
| [5.30] 08-1 연결 리스트 (0) | 2021.05.30 |