📖트리(Tree)
트리는 하나 이상의 노드(node)로 이루어진 자료구조이다. 각 노드는 데이터를 저장하며, 다른 노드와 간선(edge)로 연결되어있다. 간선은 노드와 노드를 연결해주는 역할을 한다.
📁주요 단어
- root : 트리 구조에서 가장 위에 놓인 노드 (위 그림 기준 A)
- parent node : 한 노드가 하위 노드를 가지고 있는 경우, 그 노드가 하위 노드의 부모 노드임 (위 그림 기준 D, E의 부모 노드는 B)
- child node : 한 노드가 하위 노드를 가지고 있는 경우, 하위 노드가 그 노드의 자식 노드임 (위 그림 기준 B의 자식 노드는 D, E)
- sibling : 부모 노드가 동일한 자식 노드들 (위 그림 기준 D, E)
- leaf node(terminal node) : 자식 노드가 없는, 트리 구조에서 가장 아래에 놓인 노드 (위 그림 기준 K, L, M, N, O, P)
- nonterminal node : leaf node 외의 노드
- subtree : 특정 노드를 루트 노드로 하는 트리 속 작은 트리 구조
- 노드의 차수(degree) : 노드의 자식 노드 수 (위 그림 기준 A의 degree는 2)
- 트리의 차수 : max(노드의 차수)
- level : 루트 노드부터 특정 노드까지의 거리
- 트리의 높이 : max(노드의 레벨)
📁트리 순회(Tree traversal)
트리에 있는 모든 노드를 한 번씩만 방문하는 순회에는 4가지 방식이 있다. 각각을 전위 순회, 중위 순회, 후위 순회, 레벨 순서 순회라고 한다.
- 전위 순회(preorder traversal) : 현재 노드 방문 -> 왼쪽 자식 노드 방문 -> 오른쪽 자식 노드 방문
=> 1 - 2 - 4 - 8 - 9 - 5 - 10 - 11 - 3 - 6 - 13 - 7 - 14- 중위 순회(inorder traversal) : 왼쪽 자식 노드 방문 -> 현재 노드 방문 -> 오른쪽 자식 노드 방문
=> 8 - 4 - 9 - 2 - 10 - 5 - 11 - 1 - 6 - 13 - 3 - 14 - 7- 후위 순회(postorder traversal) : 왼쪽 자식 노드 방문 -> 오른쪽 자식 노드 방문 -> 현재 노드 방문
=> 8 - 9 - 4 - 10 - 11 - 5 - 2 - 13 - 6 - 14 - 7 - 3 - 1- 레벨 순서 순회(level order traversal) : 맨 위 레벨부터 차례대로 방문
=> 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11 - 13 - 14
