Computer Science/자료구조
[6.2] 09-1 트리구조
토마토.
2021. 6. 2. 21:28
트리 구조 : 데이터 사이의 계층 관계를 표현한다
트리의 구조와 관련 용어
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 : 왼쪽 자식 > 오른쪽 자식 > 노드 방문