C언어 응용 제10주 실습 해보기 제8장 트리.

Presentation on theme: "C언어 응용 제10주 실습 해보기 제8장 트리."— Presentation transcript:

1 C언어 응용 제10주 실습 해보기 제8장 트리

2 실습 내용 예제 8-1 이진트리 순회 프로그램 예제 8-2 가상폴더의 용량 계산 프로그램
예제 8-3 이진탐색트리의 연산 프로그램 예제 8-4 순차자료구조를 이용한 최대히프 프로 그램

3 예제 8-1 실습하기 연결자료구조를 이용한 이진트리 구현 이진트리 노드 생성 함수 작성 이진트리의 순회 함수 작성
이진트리를 구현한 소스파일과 헤더파일을 따로 작성한다. 구현한 함수 목록 makeBinaryTree : 이진트리 노드를 생성하는 함수 preorder : 전위 순회 함수 inorder : 전위 순회 함수 postorder : 전위 순회 함수 removeBinaryTree : 이진트리 삭제

4 소스 목록 및 내용 binarytree.h : 이진트리구현에 필요한 자료형과 함수의 원형을 선언하는 헤더 파일
binarytree.c : 이진트리구현에 필요한 함수의 내 용을 작성한 소스 ex0801.c : 이진트리를 테스트하는 main 소스 파 일

5 실습하는 순서 Eclipse 를 실행한다. Workspace와 Perspective가 맞는지 확인 하고 맞지 않으면 수정한다. Workspace 는 D:\Lec_hwlee\Capp\y2014 이고 Perspective 는 C/C++ 이어야 한다. 프로젝트 생성 binarytree.h 파일 작성 binarytree.c 파일 작성 ex0801.c 작성 빌드 및 실행 결과 확인

6 소스들 사이의 연관 관계 binarytree.h ex0801.c
이진트리 구현에 필요한 구조체와 필요한 함수의 원형을 선언한다. ex0801.c 구현된 연결리스트를 테스트 해보는 main 소스 포함한다. 포함한다. 실제 함수를 호출하여 사용한다. binarytree.c 이진트리 구현에 필요한 함수의 내용을 작성한다.

7 main 소스 코드 이진트리를 만들고 각 순회 방법으로 출력한다.

8 Eclipse 실행 D:\Lec_hwl\CApp\y2014

9 Eclipse 실행

10 Workspace 확인 D:\Lec_hwl\CApp\y2014

11 CDT Perspective 확인 이 버튼을 클릭해서 수정 Java EE 로 되어 있음

12 CDT Perspective 확인 C/C++ 선택

13 CDT Perspective 확인 C/C++ 로 되어 있음

14 새 프로젝트 생성 File->New->C Project 반드시 C Project를 택할 것

15 프로젝트 명 설정 Ch0801 Empty Project Cygwin GCC D:\Lec_hwl\capp\y2014\Ch0801

16 프로젝트 구성 설정 Debug 버전과 Release 버전 모두 사용

17 생성된 빈 프로젝트 본인 컴퓨터의 사양에 따라 내용은 약간씩 다를 수 있음

18 binarytree.h 추가 및 작성 Header File 선택

19 binarytree.h 추가 및 작성 Ch0801 프로젝트명 설정(자동설정) binarytree.h 헤더 파일 명 설정

20 binarytree.h 추가 및 작성 자동 생성된 빈 헤더 파일
헤더가 여러 소스에서 포함되었을 때 이중으로 포함되지 않도록 하는 매크로 실제 헤더의 내용이 들어갈 위치

21 binarytree.h 추가 및 작성 노드 구조체 및 함수 원형 선언

22 binarytree.c 추가 및 작성 Source File 선택

23 binarytree.c 추가 및 작성 Ch0801 프로젝트명 확인 binarytree.c 소스 파일명 설정

24 binarytree.c 추가 및 작성 자동 생성된 빈 소스 파일

25 binarytree.c 추가 및 작성 필요한 코드 작성(빈 함수 작성)
표준 입출력 함수 헤더 메모리 할당 함수 헤더 이진트리관련 함수 헤더 필요한 각 함수의 원형에 맞게 함수의 몸체를 작성하되, 내용은 모두 빈 것으로 작성한다. 차후에 한 함수씩 코드의 내용을 작성한다.

26 makeTreeNode() 함수 노드에 저장할 자료와 왼쪽, 오른쪽 연결 노드를 이용하여 새로운 이진트리를 구성한다.

27 preorder() 함수 이진 트리를 전위 순회 한다.

28 inorder() 함수 이진 트리를 중위 순회 한다.

29 postorder() 함수 이진 트리를 후위 순회 한다.

30 removeBinaryTree() 함수
이진 트리가 사용하는 메모리를 반환한다.

31 ex0801.c 추가 및 작성 Source File 선택

32 ex0801.c 추가 및 작성 Ch0801 프로젝트명 확인 ex0801.c 소스 파일명 설정

33 추가된 빈 소스 파일 프로젝트에 3 개의 파일 ex0801.c, binarytree.c, binarytree.h
가 추가된 것을 확인할 수 있다.

34 main 함수 작성 빈 main 함수 작성 표준 입출력 함수 헤더 메모리 관련 함수 헤더 이진트리 관련 함수 헤더

35 main 함수 아래 그림과 같은 이진 트리를 만들고 전위, 중위, 후위 순회 출력을 한다.

36 main 함수 작성

37 main 함수 작성

38 빌드 및 실행 결과

39 도전 문제 트리의 자료를 정수로 하는 이진트리를 만들고 앞 예제의 A=5, B=-3, C=7, D=2 로 한 수식의 결 과를 계산하는 프로그램을 완성하시오.

40

41 예제 8-2 실습하기 이진트리 형태로 구성된 폴더 구조를 구현하고 폴 더의 총 크기를 계산한다.
이진트리를 구현한 소스파일과 헤더파일을 따로 작성한다. 구현한 함수 목록 makeFolderTree : 이진트리 폴더 구조를 생성한다. removeFolderTree : 이진트리가 사용하는 메모리를 반 환한다. postorderSize : 후위 순회로 폴더의 크기를 계산한다.

42 소스 목록 및 내용 foldertree.h : 필요한 자료형과 함수의 원형을 선 언하는 헤더 파일
foldertree.c : 필요한 자료형과 함수의 내용을 작 성한 소스 ex0802.c : 테스트하는 main 소스 파일

43 예제 폴더 구조

44 실습하는 순서 Eclipse 를 실행한다. Workspace와 Perspective가 맞는지 확인 하고 맞지 않으면 수정한다. Workspace 는 D:\Lec_hwlee\Capp\y2014 이고 Perspective 는 C/C++ 이어야 한다. 프로젝트 생성 foldertree.h 파일 작성 foldertree.c 파일 작성 ex0802.c 작성 빌드 및 실행 결과 확인

45 소스들 사이의 연관 관계 foldertree.h ex0802.c
이진트리 구현에 필요한 구조체와 필요한 함수의 원형을 선언한다. ex0802.c 구현된 연결리스트를 테스트 해보는 main 소스 포함한다. 포함한다. 실제 함수를 호출하여 사용한다. foldertree.c 이진트리 구현에 필요한 함수의 내용을 작성한다.

46 함수 가상 코드 makeFolderTree(data, left, right) s ← memory allocate for FolderTree; if ( s = NULL) then memory full error; return NULL; else { s-> data ← data; s-> left ← left; s-> right ← right; return s; } End makeFolderTree

47 함수 가상 코드 removeFolderTree(FolderTree * root) if ( root = NULL) then return; else { removeFolderTree(root->left); removeFolderTree(root->right); free root; } End removeFolderTree

48 함수 가상 코드 postorderSize(FolderTree * root) if( root = NULL) then return 0; else { size ← 0; size ← size + postorderSize(root->left); size ← size + postorderSize(root->right); size ← size + root->size; return size; } End postorderSize

49 main 소스 코드 앞의 그림과 같은 구조를 갖는 이진 트리를 만든다. 전체 폴더의 크기를 구하여 출력한다.

50 Eclipse 실행 D:\Lec_hwl\CApp\y2014

51 Eclipse 실행

52 Workspace 확인 D:\Lec_hwl\CApp\y2014

53 CDT Perspective 확인 이 버튼을 클릭해서 수정 Java EE 로 되어 있음

54 CDT Perspective 확인 C/C++ 선택

55 CDT Perspective 확인 C/C++ 로 되어 있음

56 새 프로젝트 생성 File->New->C Project 반드시 C Project를 택할 것

57 프로젝트 명 설정 Ch0802 Empty Project Cygwin GCC D:\Lec_hwl\capp\y2014\Ch0802

58 프로젝트 구성 설정 Debug 버전과 Release 버전 모두 사용

59 생성된 빈 프로젝트 본인 컴퓨터의 사양에 따라 내용은 약간씩 다를 수 있음

60 foldertree.h 추가 및 작성 Header File 선택

61 foldertree.h 추가 및 작성 Ch0802 프로젝트명 설정(자동설정) foldertree.h 헤더 파일 명 설정

62 foldertree.h 추가 및 작성 자동 생성된 빈 헤더 파일
헤더가 여러 소스에서 포함되었을 때 이중으로 포함되지 않도록 하는 매크로 실제 헤더의 내용이 들어갈 위치

63 foldertree.h 추가 및 작성 노드 구조체 및 함수 원형 선언

64 foldertree.c 추가 및 작성 Source File 선택

65 foldertree.c 추가 및 작성 Ch0802 프로젝트명 확인 foldertree.c 소스 파일명 설정

66 foldertree.c 추가 및 작성 자동 생성된 빈 소스 파일

67 foldertree.c 추가 및 작성 필요한 코드 작성(빈 함수 작성)
표준 입출력 함수 헤더 메모리 할당 함수 헤더 이진트리관련 함수 헤더 필요한 각 함수의 원형에 맞게 함수의 몸체를 작성하되, 내용은 모두 빈 것으로 작성한다. 차후에 한 함수씩 코드의 내용을 작성한다.

68 makeFolderTree() 함수 노드에 저장할 자료와 왼쪽, 오른쪽 연결 노드를 이용하여 새로운 이진트리를 구성한다.

69 removeFolderTree() 함수
이진 트리가 사용하는 메모리를 반환한다.

70 preorderSize() 함수 이진 트리를 전위 순회하면서 크기를 계산한다.

71 ex0802.c 추가 및 작성 Source File 선택

72 ex0802.c 추가 및 작성 Ch0802 프로젝트명 확인 ex0802.c 소스 파일명 설정

73 추가된 빈 소스 파일 프로젝트에 3 개의 파일 ex0802.c, foldertree.c, foldertree.h
가 추가된 것을 확인할 수 있다.

74 main 함수 작성 빈 main 함수 작성 표준 입출력 함수 헤더 메모리 관련 함수 헤더 이진트리 관련 함수 헤더

75 main 함수 아래 그림과 같은 이진 트리를 만들고 후위순회를 사용하여 전체 크기를 계산하여 출력한다.

76 main 함수 작성

77 빌드 및 실행 결과

78 도전 문제 위 예제에서 노드의 자료에 폴더의 이름을 저장할 수 있도록 수정하고 출력할 때 노드에 저장된 이름 을 사용하도록 하시오.

79

80 예제 8-3 실습하기 이진탐색트리를 구현한다. 이진탐색트리를 사용하여 자료를 입력하고 검색하 는 프로그램을 구현한다.
구현한 함수 목록 insertNode : 이진탐색트리에 자료를 삽입한다. removeNode : 이진탐색트리로 부터 주어진 원소를 찾아 서 삭제한다. searchNode : 이진탐색트리에서 주어진 원소를 갖는 노 드를 찾는다. clearTree : 트리가 사용한 메모리를 반환한다. displayInorder : 이진탐색트리를 출력한다. menu : 메뉴를 출력하는 함수

81 소스 목록 및 내용 bst.h : 필요한 자료형과 함수의 원형을 선언하는 헤더 파일
bst.c : 필요한 자료형과 함수의 내용을 작성한 소 스 ex0803.c : 테스트하는 main 소스 파일

82 실습하는 순서 Eclipse 를 실행한다. Workspace와 Perspective가 맞는지 확인 하고 맞지 않으면 수정한다. Workspace 는 D:\Lec_hwlee\Capp\y2014 이고 Perspective 는 C/C++ 이어야 한다. 프로젝트 생성 bst.h 파일 작성 bst.c 파일 작성 ex0803.c 작성 빌드 및 실행 결과 확인

83 소스들 사이의 연관 관계 bst.h ex0803.c 이진탐색트리 구현에 필요한 구조체와 필요한 함수의 원형을 선언한다.
구현된 연결리스트를 테스트 해보는 main 소스 포함한다. 포함한다. 실제 함수를 호출하여 사용한다. bst.c 이진탐색트리 구현에 필요한 함수의 내용을 작성한다.

84 함수 가상 코드 insertNode(BSTNode *root, char data) p ← root; while ( p ≠ NULL) do { if( data = p.key) then return; q ← p; if( data < p.key) then p ← p.left; else p ← p.right; } node ← allocate memory for a new node; node.key ← data; node.left ← NULL; node.right ← NULL; if( root = NULL) root ← node; else if ( data < q.key) then q.left ← node; else q.right ← node; return root; End insertNode

85 함수 가상 코드 removeNode(BSTNode * root, char data) search node with the same key value; if not exist write message and return; remove that node and modify tree End removeNode

86 함수 가상 코드 searchNode(BSTNode * root, char data, BSTNode **parent) p ← root; if( p = NULL) then return NULL; if (p.key = data) then return p; if( data < p.key) then *parent ← p; return searchNode(p.left, data, parent); else return searchNode(p.right, data, parent); End searchNode

87 함수 가상 코드 clearTree(BSTNode * root) if( root ≠ NULL) then clearTree(root->left); clearTree(root->right); free(root); End clearTree

88 함수 가상 코드 displayInorder(BSTNode * root) if( root ≠ NULL) then displayInorder(root->left); printf(“%c_”, root->key); displayInorder(root->right); End displayInorder

89 main 소스 코드 이진탐색트리를 만들고 메뉴를 이용하여 삽입/삭 제/출력를 한다.

90 Eclipse 실행 D:\Lec_hwl\CApp\y2014

91 Eclipse 실행

92 Workspace 확인 D:\Lec_hwl\CApp\y2014

93 CDT Perspective 확인 이 버튼을 클릭해서 수정 Java EE 로 되어 있음

94 CDT Perspective 확인 C/C++ 선택

95 CDT Perspective 확인 C/C++ 로 되어 있음

96 새 프로젝트 생성 File->New->C Project 반드시 C Project를 택할 것

97 프로젝트 명 설정 Ch0803 Empty Project Cygwin GCC D:\Lec_hwl\capp\y2014\Ch0803

98 프로젝트 구성 설정 Debug 버전과 Release 버전 모두 사용

99 생성된 빈 프로젝트 본인 컴퓨터의 사양에 따라 내용은 약간씩 다를 수 있음

100 bst.h 추가 및 작성 Header File 선택

101 bst.h 추가 및 작성 Ch0803 프로젝트명 설정(자동설정) bst.h 헤더 파일 명 설정

102 bst.h 추가 및 작성 자동 생성된 빈 헤더 파일 헤더가 여러 소스에서 포함되었을 때 이중으로 포함되지 않도록 하는 매크로
헤더가 여러 소스에서 포함되었을 때 이중으로 포함되지 않도록 하는 매크로 실제 헤더의 내용이 들어갈 위치

103 bst.h 추가 및 작성 노드 구조체 및 함수 원형 선언

104 bst.c 추가 및 작성 Source File 선택

105 foldertree.c 추가 및 작성 Ch0803 프로젝트명 확인(자동설정) bst.c 소스 파일명 설정

106 bst.c 추가 및 작성 자동 생성된 빈 소스 파일

107 bst.c 추가 및 작성 필요한 코드 작성(빈 함수 작성)
표준 입출력 함수 헤더 메모리 할당 함수 헤더 이진트리관련 함수 헤더 필요한 각 함수의 원형에 맞게 함수의 몸체를 작성하되, 내용은 모두 빈 것으로 작성한다. 차후에 한 함수씩 코드의 내용을 작성한다.

108 insertNode() 함수 노드에 저장할 자료를 올바른 위치에 추가한다.

109 insertNode() 함수 노드에 저장할 자료를 올바른 위치에 추가한다.

110 removeNode() 함수 주어진 자료를 갖는 노드를 찾아서 삭제하고 트리 를 변형한다.

111 removeNode() 함수

112 removeNode() 함수

113 removeNode() 함수

114 searchNode() 함수

115 searchNode() 함수

116 clearTree() 함수

117 displayInorder() 함수

118 ex0803.c 추가 및 작성 Source File 선택

119 ex0803.c 추가 및 작성 Ch0803 프로젝트명 확인(자동설정) ex0803.c 소스 파일명 설정

120 추가된 빈 소스 파일 프로젝트에 3 개의 파일 ex0803.c, bst.c, bst.h 가 추가된 것을 확인할 수 있다.

121 main 함수 작성 빈 main 함수 작성 표준 입출력 함수 헤더 메모리 관련 함수 헤더 이진탐색트리 관련 함수 헤더

122 main 함수 작성

123 main 함수 작성

124 main 함수 작성

125 빌드 및 실행 결과

126 도전 문제 위 예제에서 노드의 자료를 정수형으로 하여 다시 작성하시오.

127 도전문제 예제 8-4를 위의 풀이 방법과 유사하게 작성하시 오.