230315

비선형 자료구조

트리

계층적 관계를 표현하는 비선형 자료구조

• 노드와 간선으로 이루어진 자료구조
• 루트 노드가 존재
• 부모 - 자식으로 표현되는 계층 구조를 가짐
• 방향성이 존재하는 방향 그래프이며 사이클 불가능

1. 이진트리

각 노드가 왼쪽 자식과 오른쪽 자식 둘을 갖는 트리, 이 때 두 자식 가운데 한쪽이 없거나 둘 다 없는 노드가 포함되어도 된다.

2. 완전 이진 트리

루트 아래쪽 레벨로 내려가는 노드가 빠짐없이 채워져 있고, 또 같은 레벨에서도 빠짐없이 채워져 있는 이진트리 (단, 마지막은 제외)