트리자료구조

트리자료구조

트리

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

<용어>

루트노드: 부모가 없는 최상위 노드

단말노드: 자식이 없는 노드

크기: 트리에 포함된 모든 노드의 개수

깊이: 루트 노드부터의 거리

높이: 깊이 중 최댓값

차수: 각 노드의 간선 개수(기본적으로 트리 크기가 N일 때, N-1개)

이진탐색트리

: 왼쪽자식노드 < 부모노드 < 오른쪽 자식노드

: 부모 노드보다 왼쪽 자식노드가 작다

: 부모 노드보다 오른쪽 자식노드가 크다

트리의 순회

: 트리 자료구조에 포함된 노드를 특정한 방법으로 한 번씩 방문하는 방법

1) 전위순회: 루트를 먼저 방문

2) 중위순회: 왼쪽 자식을 방문한 뒤에 루트를 방문

3) 후위순회: 오른쪽 자식을 방문한 뒤에 루트를 방문

전위순회: A - B - D - E - C - F - G

중위순회: D - B - E - A - F - C - G

후위순회: D - E - B - F - G - C - A

from http://404canfind.tistory.com/31 by ccl(A) rewrite - 2021-10-11 15:26:40