이진트리

1. Binary_tree.h

1. #ifndef _BINARY_TREE_
2. #define _BINARY_TREE_
3.  
4. typedef struct BTree
5. {
6.     int data;                           //정수형 Data
7.     struct BTree* pLeft_Child;  //좌측 자식
8.     struct BTree* pRight_Child; //우측 자식
9. }BTNode;
10.  
11. BTNode* Create_Binary_Tree(int root_Data);                              //루트 노드 생성
12. BTNode* Insert_Left_Child(BTNode* pParent, int child_Data);     //좌측 노드 생성
13. BTNode* Insert_Right_Child(BTNode* pParent, int child_Data);    //우측 노드 생성
14. void Print_Binary_Tree(BTNode* pNode, int level);                           //트리 출력
15. void Destroy_Node(BTNode* pNode);                                           //노드 삭제
16. void Destroy_Binary_Tree(BTNode* pRoot);                                    //이진트리 삭제
17. #endif _BINARY_TREE_

2. Binary_tree.c

1. #include<stdio.h>
2. #include<stdlib.h>
3. #include"Binary_tree.h"
4.  
5. //================================================
6. //Create_Binary_Tree
7. //입력 인자 : 최초 생성된 루트 노드의 데이터
8. //반환 인자 : 생성된 노드의 구조체 포인터
9. //-최초 루트노드 생성시 필요.
10. //================================================
11. BTNode* Create_Binary_Tree(int root_Data)
12. {
13.     BTNode *pTree = NULL;
14.    
15.     pTree = (BTNode*)malloc(sizeof(BTNode));        //노드 메모리 할당
16.  
17.     if(pTree != NULL)                           //메모리 할당 제대로 되었다면
18.     {
19.         //최초 루트 노드 생성시 자식 노드 없다.
20.         pTree->pLeft_Child=NULL;               
21.         pTree->pRight_Child=NULL;
22.         pTree->data=root_Data;
23.     }
24.     else
25.     {
26.         printf("메모리 할당 실패\n");
27.         free(pTree);
28.         return NULL;
29.     }
30.  
31.     //생성된 루트 노드 반환.
32.     return pTree;
33. }
34.  
35. //================================================
36. //Insert_Left_Child
37. //입력 인자 : 부모 노드와 자식노드의 Data
38. //반환 인자 : 생성된 노드의 구조체 포인터
39. //-좌측 노드 생성시 필요
40. //================================================
41. BTNode* Insert_Left_Child(BTNode* pParent, int child_Data)
42. {
43.     BTNode *pChild = NULL;
44.     pChild =  (BTNode*)malloc(sizeof(BTNode));
45.  
46.     if(pChild != NULL)      //메모리 할당 성공
47.     {
48.         if(pParent->pLeft_Child == NULL) // 부모의 좌측 자식 노드가 없다면
49.         {
50.             pParent->pLeft_Child = pChild;      //좌측 자식 노드에 노드 추가
51.             pChild->data = child_Data;          //자식 노드에 Data
52.             pChild->pLeft_Child=NULL;
53.             pChild->pRight_Child=NULL;
54.         }
55.         else
56.         {
57.             printf("현재 부모의 좌측에 노드가 존재합니다.\n");
58.             free(pChild);
59.             return NULL;
60.         }
61.     }
62.     else
63.     {
64.         printf("메모리 할당 실패\n");
65.         return NULL;
66.     }
67.  
68.     return pChild;  //생성된 자식 노드 반환.
69. }
70.  
71. //================================================
72. //Insert_Right_Child
73. //입력 인자 : 부모 노드와 자식노드의 Data
74. //반환 인자 : 생성된 노드의 구조체 포인터
75. //-우측 노드 생성시 필요
76. //================================================
77. BTNode* Insert_Right_Child(BTNode* pParent, int child_Data)
78. {
79.     BTNode *pChild = NULL;
80.     pChild =  (BTNode*)malloc(sizeof(BTNode));
81.  
82.     if(pChild != NULL)      //메모리 할당 성공
83.     {
84.         if(pParent->pRight_Child == NULL) // 부모의 우측 자식 노드가 없다면
85.         {
86.             pParent->pRight_Child = pChild;     //우측 자식 노드에 노드 추가
87.             pChild->data = child_Data;          //자식 노드에 Data
88.             pChild->pLeft_Child=NULL;
89.             pChild->pRight_Child=NULL;
90.         }
91.         else
92.         {
93.             printf("현재 부모의 우측에 노드가 존재합니다.\n");
94.             free(pChild);
95.             return NULL;
96.         }
97.     }
98.     else
99.     {
100.         printf("메모리 할당 실패\n");
101.         return NULL;
102.     }
103.  
104.     return pChild;  //생성된 자식 노드 반환.
105. }
106.  
107. //================================================
108. //Print_Binary_Tree
109. //입력 인자 : 루트노드와 레벨
110. //반환 인자 : 없음
111. //-트리 구조 전체 출력 // 재귀이용한 출력
112. //================================================
113. void Print_Binary_Tree(BTNode* pNode, int level)
114. {
115.     int i=0;
116.     for(i=0; i<level; i++)
117.         printf("\t");
118.     printf("%d\n", pNode->data);
119.  
120.     if(pNode->pLeft_Child != NULL)
121.         Print_Binary_Tree(pNode->pLeft_Child, level+1);
122.     if(pNode->pRight_Child != NULL)
123.         Print_Binary_Tree(pNode->pRight_Child, level+1);
124. }
125.  
126. //================================================
127. //Destroy_Binary_Tree
128. //입력 인자 : 루트노드
129. //반환 인자 : 없음
130. //-트리 구조 전체 삭제 // 재귀이용한 출력
131. //================================================
132. void Destroy_Binary_Tree(BTNode* pRoot)
133. {
134.     if(pRoot->pLeft_Child != NULL)
135.         Destroy_Binary_Tree(pRoot->pLeft_Child);
136.     if(pRoot->pRight_Child != NULL)
137.         Destroy_Binary_Tree(pRoot->pRight_Child);
138. }
139.  
140. void Destroy_Node(BTNode* pNode)
141. {
142.     if(pNode->pLeft_Child==NULL && pNode->pRight_Child==NULL)
143.         free(pNode);        //메모리 해제
144. }

3. 테스트 코드

1. #include<stdio.h>
2. #include<stdlib.h>
3. #include"Binary_tree.h"
4.  
5. int main()
6. {
7.     BTNode* pRoot;
8.     BTNode* A= NULL;
9.     BTNode* B= NULL;
10.     BTNode* C= NULL;
11.     BTNode* D= NULL;
12.     pRoot = (BTNode*)malloc(sizeof(BTNode));
13.    
14.     pRoot=Create_Binary_Tree(0);
15.     A=Insert_Left_Child(pRoot, 1);
16.     B=Insert_Right_Child(pRoot, 2);
17.     C=Insert_Left_Child(A, 3);
18.     D=Insert_Right_Child(A, 4);
19.     Destroy_Binary_Tree(pRoot);
20.  
21.     return 0;
22. }

Binary_tree.c

Binary_tree.h

BT_Test.c