트리

 트리란?

이차원의 자료구조이다. 앞서 배웠던 스택과 큐는 낮은 차원의 자료구조인 방면 트리는 이차원의 자료구조이다.

트리 자료구조

A-->루트 노드(root)

G,H,J,E,K-->리프 노드(leaf)

B,C,D,F--> 내부 노드(internal)

 

-부모 자식 관계

노드 D-->노드 G,J,H의 부모

부모 노드, 자식 노드로 표현

간선으로 연결된 관계임

 

조상: 부모의 부모의 부모...

후손: 자식의 자식의 ...

 

 

-노드의 수준

루트 노드-->level0

순차적으로 1씩 커짐

 

-트리의 높이

=최대 수준 level +1

-부분 트리(서브 트리)

어느 한 노드를 기준으로 잘라내어 따로 분리한 트리

나무에서 가지 부분과 의미가 같음

 

-노드의 차수(degree)

=자식(서브트리)의 수

 

-이진 트리(binary tree)

모든 노드의 차수가 2이하인 트리

재귀적으로 정의 가능

루트 노드 & 왼쪽 서브 트리 & 오른쪽 서브트리

 

-포화 이진 트리

모든 레벨에서 노드들이 모두 채워져 있는 이진트리

높이가 k이고 노드의 개수가 2^k-1개라면 포화 이진트리

 

-이진 트리 

size()-->현재 트리에 포함되어 있는 노드의 수

depth()--> 현재 트리의 깊이

 

-이진 트리의 구현(노드)

data & left child & right child