02/10(1) - 트리

자료구조에는 크게 선형 / 비선형 구조가 있다 .

선형구조는 그동안 배워왔던 리스트나 배열 즉, 1 대 1 의 관계를 가지는 것들이 있다. 

비선형구조는 '트리'나 '그래프' 처럼, 1 대 多 의 데이터 구조를 가지는 것들이 있다.

---

[ 트리 ] : 여러개의 노드로 이루어진 계층형 구조의 자료구조 ( 루프가 없음 )  

트리는 하나의 ' 루트노드' 를 기준으로 가지를 뻗어나간다.

상위노드와 하위노드로 이루어지며, 일반적으로 하나의 상위노드에 여러개의 하위노드가 따라온다 .

- 노드 (Node) : 트리의 구성요소로 ( 루트노드 : 최상위 / 단말노드 (leaf) : 최하위 )

- 형제노드 : 같은 부모노드를 가진 노드들 

- 조상노드 : 하나의 노드를 기준으로 간선을 따라 올라가면서 루트노드까지 있는 모든 노드들 

- 자손노드 : 하나의 노드를 기준으로 간선을 따라 내려가면서 있는 모든 노드들 

- 자식노드 : 간선으로 연결되어있는 하위노드 하나 

 

- 차수 : 노드에 연결되어있는 자식 노드의 수 ( 즉, 자식노드와 연결되어있는 간선의 수 ) 

- 트리의 차수 : 트리의 모든 노드들의 차수 중, 가장 큰 값 

( + 트리의 모든 차수가 2 이하의 값을 가지는 것 : 이진트리  - 자식을 0~2 개 가지는 것 ) 

vs 

- 높이 : 루트노드에서 자식노드까지의 간선의 수 

- 트리의 높이 : 트리의 모든 높이 중 가장 최댓값