데이터구조 과제_이진트리 탐색, 순회, 조사, 정렬, 허프만 코드

소개

데이터구조및응용 과목에서 진행한 과제입니다.

목차

1. 트리를 전위순회, 중위순회, 후위순회한 결과 구하기
2. 탐색 방법에 따른 탐색 과정 구하고 탐색 시에 필요한 비교 연산 횟수 구하기(순차 탐색, 이진 탐색, 보간 탐색)
3. ALV트리의 생성 과정 그리기
4. 삭제 연산시 이진탐색트리 조건을
5. 만족하도록 삭제된 노드의 부모노드와 자식노드들을 연결해 주어야 하는 3가지 경우(case)에
6. 대하여 설명하기
7. 주어진 해시함수와 입력키를 선형 조사법, 이차조사법, 이중 해시법, 체이닝법으로 해시테이블에 저장하는 과정 각각 구하기
8. 정렬 기법을 이용하여 정수 배열을 오름차순으로 정렬하기(퀵 정렬, 힙 정렬, 병합 정렬, 쉘 정렬, 삽입 정렬, 선택 정렬, 버블 정렬)
9. 그래프를 보고 최단거리 계산하기 (Dijkstra 알고리즘 사용)
10. 허프만 알고리즘을 이용해 각 문자의 허프만 코드 구하기
11. 주어진 코드에 대응하는 문자나열 작성하기
12. 주어진 문자열에 대해 허프만 코드 작성하기

본문내용

문제 1] 다음 트리를 전위순회, 중위순회, 후위순회한 결과를 구하시오.
전위순회 결과
[G]-[D]-[B]-[A]-[E]-[I]-[H]-[M]-[J]-[N]-[Q]

중위순회 결과
[A]-[B]-[D]-[E]-[G]-[H]-[I]-[J]-[M]-[N]-[Q]

후위순회 결과
[A]-[B]-[E]-[D]-[H]-[J]-[Q]-[N]-[M]-[I]-[G]

문제 2] 다음 그래프를 보고 질문에 답하시오
(1) 프림 알고리즘을 이용해 그래프 1의 최소 신장 트리를 구성하시오.

<중 략>

문제 9] 다음 그래프에서 정점 S부터 E까지의 최단 거리를 계산해보자. Dijkstra 알고리즘을 사용한다.
각 단계에서 dist 배열의 내용을 적어라.
S={A}

dist(A)=0
dist(B)= ∞
dist(C)= ∞
dist(D)= ∞
dist(E)=9
dist(S)=14

S={A, E}

dist(A)=0
dist(B)= ∞
dist(C)= ∞
dist(D)=15
dist(E)=9
dist(S)=14

참고자료

· 없음