c언어로 쉽게 풀어쓴 자료구조 개정 3판 8장(트리) 연습문제 (해설 포함)

1. 트리의 기본 개념

트리는 계층적 구조를 표현하는 자료구조로서, 노드와 간선으로 이루어진 비선형 자료구조이다. 트리는 실제 세계에서도 일상생활과 자연현상에서 쉽게 찾을 수 있는데, 예를 들어 가족 관계, 회사 조직도, 파일 시스템이 대표적이다. 가령, 컴퓨터 운영체제의 디렉터리 구조는 트리 구조를 통해 폴더와 파일의 계층 관계를 명확히 표현한다. 이러한 구조는 복잡한 데이터를 계층적으로 표현함으로써 효율적인 검색과 정렬이 가능하게 한다. 트리의 가장 낮은 단계에 있는 노드를 말하는 말단 노드(리프 노드)는 서버의 최상위 폴더 아래에 있는 개별 파일과 같다. 트리의 루트 노드(뿌리 노드)는 전체 구조의 시작점이며, 예를 들어 디렉터리 구조에서 C:\ 드라이브가 루트에 해당한다. 또한, 각각의 노드는 데이터와 그 데이터를 가리키는 포인터 역할을 하며, 노드 간 연결은 부모-자식 관계를 형성한다. 트리의 노드 수는 최대 2의 높이 승수만큼 늘어날 수 있는데, 예를 들어 높이 4인 이진 트리의 경우 최대 노드 수는 2^4 - 1인 15개에 달한다. 트리의 높이와 노드 수는 자료를 얼마나 깊이 있게 저장하고 있는지, 즉 구조의 복잡도를 반영하며…