트리란?

<aside> ➡️ 트리는 계층형 트리 구조를 시뮬레이션 하는 추상 자료형 (ADT)으로, 루트 값과 부모-자식 관계의 서브트리로 구성되며, 서로 연결된 노드의 집합이다.

</aside>

<aside> ➡️ 중요한 트리의 속성 중 하나로 재귀로 정의된 자기 참조 구조라는 점.

→ 자식도 트리고 또 그 자식도 트리. 여러개의 트리가 쌓아져 큰 트리가 된다.

</aside>

트리의 각 명칭

<aside> ➡️ Node : 트리에서 데이터를 저장하는 기본 요소 → 동그라미라고 생각

Root Node : 트리 맨 위에 있는 뿌리

Level : 루트 노드로부터 연결되어있는 노드의 깊이

Parent Node : 어떤 노드의 상위 레밸에 연결된 노드

Child Node : 어떤 노드의 하위 레밸에 연결된 노드

Leaf Node : Child 노드가 하나도 없는 마지막 노드

Sibling : 동일한 부모 노드를 가진 노드

Depth : 트리에서 노드가 가질 수 있는 최대 Level

차수 : 자식의 수 (서브트리)

</aside>

그래프 vs 트리

<aside> ➡️ 트리는 그래프와 달리 순환 구조를 갖지 않는 그래프를 말한다.

따라서 위 사진처럼 간선의 화살표를 생략할 수 있다. 단방향이며 방향은 위에서 아래를 향한다.

즉, 부모노드에서 자식노드로만 연결되어있는 그래프라고 생각.

</aside>

트리가 아닌 예

이진 트리란?

<aside> ➡️ 각 노드에서 자식 노드가 2개까지만 있는 트리 무조건 0 1 2 개만 있어야함

</aside>

이진 트리의 종류