[자료구조] 트리

지금까지는 주로 순차적 자료구조를 살펴봤었음(비순차적 자료 구조는 해시 테이블이 유일함)

트리는 비순차적 자료구조

 

트리

• 계층적인 구조를 표현할 때 사용할 수 있는 자료구조

 

트리 용어

• 루트 노드(root node) : 부모가 없는 최상위 노드
• A
• 단말 노드(leaf node) : 자식이 없는 노드
• K, L, F, G, M, I, J
• 크기(size) : 트리에 포함된 모든 노드의 개수
• 13
• 깊이(depth) : 루트 노드부터의 거리
• A노드의 깊이: 0
• B,C,D 노드의 깊이 : 1
• E,F,G,H,I,J노드의 깊이 : 2
• K,L,M 노드의 깊이 : 3
• 높이(height) : 깊이 중 최댓값
• 3
• 차수(degree) : 각 노드의 (자식 방향) 간선 개수
• 12
• 기본적으로 트리의 크기가 N일 때 전체 간선의 개수는 N-1개

 

트리의 순회

• 트리 자료구조에 포함된 노드를 특정한 방법으로 한 번씩 방문하는 방법
• 트리의 정보를 시각적으로 확인할 수 있다
• 대표적인 트리 순회 방법 (루트를 기준으로 해서)
• 전위 순회(pre-order) : 루트를 먼저 방문 (루트 - 왼쪽 - 오른쪽)
• 중위 순회(in-order) : 왼쪽 자식을 방문한 뒤에 루트를 방문 (왼쪽 - 루트 - 오른쪽)
• 후위 순회(post-order) : 오른쪽 자식을 방문한 뒤에 루트를 방문 (왼쪽 - 오른쪽 - 루트)