C언어로 구현한 Threaded Binary Tree

목차

1. 과제 목표
2. 설계
3. 결과 보고
4. 자료구조 및 알고리즘 분석
5. 구현한 자료구조 및 알고리즘의 시간 및 공간 복잡도
6. 전체 코드

본문내용

1. 과제 목표
- Threaded binary tree가 주어졌을 때, 명시된 node의 오른쪽에 새로운 node를 삽입하는 함수를 구현하라. 노드의 삽입이 완료된 threaded binary tree는 inorder traversal를 사용하여 threaded binary tree가 잘 구성되어 있는지 확인한다.

2. 설계
- 이번 과제는 이진 트리의 종류 중 하나인 스레드 이진 트리 구조를 Linked Representation으로 구현하고, 주어진 대로 노드를 구성한 후, 미리 작성된 노드 추가 함수의 나머지 부분을 채워 코드를 작성하는 내용이었습니다. 원래 이진 트리의 노드 타입을 선언할 때 필요한 필드는 각각 왼쪽과 오른쪽 자식으로의 링크, 그리고 데이터 필드입니다. 하지만 한 가지 비효율적인 점은, 메모리 상에 존재하는 이진 트리의 노드들 중에서 리프 노드의 경우는 양쪽 자식 링크를 전혀 사용하지 못한 채로 존재한다는 점입니다. 따라서 이러한 리프 노드의 비 할당 링크를 각각 해당 노드의 중위 순회의 선행자, 후속자로 연결하면 활용도를 높일 수 있지 않을까 하는 것이 스레드 이진 트리의 개념입니다.
- 본 과제에서는 강의 및 강의 교재에서 스레드 이진 트리에 대해 정의한 형태대로 구현을 따라갔으며, 강의 내용에는 나오지 않았지만 프로그램 종료 직전 사용한 메모리를 순회하며 해제하는 함수까지 구현하였습니다.

3. 결과 보고
- 과제 요구사항에 나온 노드들을 구현하였는데 디버깅 중에 construct_tree() 함수가 끝난 직후와 모든 노드의 추가가 끝난 직후 두 시점에서 tinorder() 함수의 출력값을 캡쳐하였습니다.

4. 자료구조 및 알고리즘 분석
가장 먼저 정의한 스레드 이진 트리를 구성할 노드 타입의 선업입니다. 각각 왼쪽 자식 링크와 오른쪽 자식 링크 외에 스레드 여부를 가리키는 Boolean 형태의 값을 더 가지고 있는데, 스레드 기능으로 링크가 작동할 시 해당 방향의 링크는 자식 링크의 포인터를 그대로 사용

참고자료

· 없음