트리] 용어, 이진 탐색 트리,순회
용어 정리
ㆍ 루트 노드(root node) : 부모가 없는 최상위 노드
ㆍ 단말 노드(leaf node) : 자식이 없는 노드
ㆍ 크기(size) : 트리에 포함된 모든 노드의 개수
ㆍ 깊이(depth) : 루트 노드로부터의 거리
ㆍ 높이(height) : 깊이 중 최댓값
ㆍ 차수(degree) : 각 노드의 (자식 방향) 간선 개수
기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 ( N-1 )개
이진 탐색 트리(Binary Search Tree)
왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
순회(Tree Traversal)
ㆍ 전위 순회(pre-order tranverse) : 루드를 먼저 방문
1 → 2 → 4 → 5 → 3 → 6 → 7
ㆍ 중위 순회(in-order traverse) : 왼쪽 자식을 방문한 뒤에 루트를 방문
4 → 2 → 5 → 1 → 6 → 3 → 7
ㆍ 후위 순회(post-order traverse) : 오른쪽 자식을 방문한 뒤에 루트를 방
4 → 5 → 2 → 6 → 7 → 3 → 1
