树

  1 #include <stdio.h>
  2 #include <malloc.h>
  3 #include "GTree.h"
  4 #include "LinkList.h"
  5 
  6 
  7 typedef struct _tag_GTreeNode GTreeNode;
  8 struct _tag_GTreeNode
  9 {
 10     GTreeData* data;
 11     GTreeNode* parent;
 12     LinkList* child;
 13 };
 14 
 15 
 16 typedef struct _tag_TLNode TLNode;
 17 struct _tag_TLNode
 18 {
 19     LinkListNode header;
 20     GTreeNode* node;
 21 };
 22 
 23 
 24 static void recursive_display(GTreeNode* node, GTree_Printf* pFunc, int format, int gap, char div)
 25 {
 26     int i = 0;
 27     
 28     if( (node != NULL) && (pFunc != NULL) )
 29     {
 30         for(i=0; i<format; i++)
 31         {
 32             printf("%c", div);
 33         }
 34     
 35         pFunc(node->data);
 36     
 37         printf("
");
 38     
 39         for(i=0; i<LinkList_Length(node->child); i++)
 40         {
 41             TLNode* trNode = (TLNode*)LinkList_Get(node->child, i);
 42             
 43             recursive_display(trNode->node, pFunc, format + gap, gap, div);
 44         }
 45     }
 46 }
 47 
 48 static void recursive_delete(LinkList* list, GTreeNode* node)
 49 {
 50     if( (list != NULL) && (node != NULL) )
 51     {
 52         GTreeNode* parent = node->parent;
 53         int index = -1;
 54         int i = 0;
 55         
 56         for(i=0; i<LinkList_Length(list); i++)
 57         {
 58             TLNode* trNode = (TLNode*)LinkList_Get(list, i);
 59              
 60             if( trNode->node == node )
 61             {
 62                 LinkList_Delete(list, i);
 63                 
 64                 free(trNode);
 65                 
 66                 index = i;
 67                 
 68                 break;
 69             }
 70         }
 71           
 72         if( index >= 0 )
 73         {  
 74             if( parent != NULL )
 75             {
 76                  for(i=0; i<LinkList_Length(parent->child); i++)
 77                  {
 78                      TLNode* trNode = (TLNode*)LinkList_Get(parent->child, i);
 79                      
 80                      if( trNode->node == node )
 81                      {
 82                          LinkList_Delete(parent->child, i);
 83                          
 84                          free(trNode);
 85                          
 86                          break;
 87                      }
 88                  }               
 89             }
 90             
 91             while( LinkList_Length(node->child) > 0 )
 92             {
 93                 TLNode* trNode = (TLNode*)LinkList_Get(node->child, 0);
 94                 
 95                 recursive_delete(list, trNode->node);
 96             }
 97             
 98             LinkList_Destroy(node->child);
 99         
100             free(node);
101         }
102     }
103 }
104 
105 static int recursive_height(GTreeNode* node)
106 {
107     int ret = 0;
108     
109     if( node != NULL )
110     {
111         int subHeight = 0;
112         int i = 0;
113         
114         for(i=0; i<LinkList_Length(node->child); i++)
115         {
116             TLNode* trNode = (TLNode*)LinkList_Get(node->child, i);
117             
118             subHeight = recursive_height(trNode->node);
119             
120             if( ret < subHeight )
121             {
122                 ret = subHeight;
123             }
124         }
125         
126         ret = ret + 1;
127     }
128     
129     return ret;
130 }
131 
132 static int recursive_degree(GTreeNode* node)
133 {
134 int ret = -1;
135     
136     if( node != NULL )
137     {
138         int subDegree = 0;
139         int i = 0;
140         
141         ret = LinkList_Length(node->child);
142         
143         for(i=0; i<LinkList_Length(node->child); i++)
144         {
145             TLNode* trNode = (TLNode*)LinkList_Get(node->child, i);
146             
147             subDegree = recursive_degree(trNode->node);
148             
149             if( ret < subDegree )
150             {
151                 ret = subDegree;
152             }
153         }
154     }
155     
156     return ret;
157 }
158 
159 GTree* GTree_Create()
160 {
161     return LinkList_Create();
162 }
163 
164 void GTree_Destroy(GTree* tree)
165 {
166     GTree_Clear(tree);
167     LinkList_Destroy(tree);
168 }
169 
170 void GTree_Clear(GTree* tree)
171 {
172      GTree_Delete(tree, 0);
173 }
174 
175 int GTree_Insert(GTree* tree, GTreeData* data, int pPos)
176 {
177     LinkList* list = (LinkList*)tree;
178     int ret = (list != NULL) && (data != NULL) && (pPos < LinkList_Length(list));
179     
180     if( ret )
181     {
182         TLNode* trNode = (TLNode*)malloc(sizeof(TLNode));
183         TLNode* cldNode = (TLNode*)malloc(sizeof(TLNode));
184         TLNode* pNode = (TLNode*)LinkList_Get(list, pPos);
185         GTreeNode* cNode = (GTreeNode*)malloc(sizeof(GTreeNode));
186         
187         ret = (trNode != NULL) && (cldNode != NULL) && (cNode != NULL);
188         
189         if( ret )
190         {
191             cNode->data = data;
192             cNode->parent = NULL;
193             cNode->child = LinkList_Create();
194             
195             trNode->node = cNode;
196             cldNode->node = cNode;
197             
198             LinkList_Insert(list, (LinkListNode*)trNode, LinkList_Length(list));
199             
200             if( pNode != NULL )
201             {
202                 cNode->parent = pNode->node;
203                 
204                 LinkList_Insert(pNode->node->child, (LinkListNode*)cldNode, LinkList_Length(pNode->node->child));
205             }
206         }
207         else
208         {
209             free(trNode);
210             free(cldNode);
211             free(cNode);
212         }
213     }
214     
215     return ret;
216 }
217 
218 GTreeData* GTree_Delete(GTree* tree, int pos)
219 {
220     TLNode* trNode = (TLNode*)LinkList_Get(tree, pos);
221     GTreeData* ret = NULL;
222     
223     if( trNode != NULL )
224     {
225         ret = trNode->node->data;
226         
227         recursive_delete(tree, trNode->node);
228     }
229     
230     return ret;
231 }
232 
233 GTreeData* GTree_Get(GTree* tree, int pos)
234 {
235     TLNode* trNode = (TLNode*)LinkList_Get(tree, pos);
236     GTreeData* ret = NULL;
237     
238     if( trNode != NULL )
239     {
240         ret = trNode->node->data;
241     }
242     
243     return ret;
244 }
245 
246 GTreeData* GTree_Root(GTree* tree)
247 {
248     return GTree_Get(tree, 0);
249 }
250 
251 int GTree_Height(GTree* tree)
252 {
253     TLNode* trNode = (TLNode*)LinkList_Get(tree, 0);
254     int ret = 0;
255     
256     if( trNode != NULL )
257     {
258         ret = recursive_height(trNode->node);
259     }
260     
261     return ret;
262 }
263 
264 int GTree_Count(GTree* tree)
265 {
266     return LinkList_Length(tree);
267 }
268 
269 int GTree_Degree(GTree* tree)
270 {
271     TLNode* trNode = (TLNode*)LinkList_Get(tree, 0);
272     int ret = -1;
273     
274     if( trNode != NULL )
275     {
276         ret = recursive_degree(trNode->node);
277     }
278     
279     return ret;
280 }
281 
282 void GTree_Display(GTree* tree, GTree_Printf* pFunc, int gap, char div)
283 {
284     TLNode* trNode = (TLNode*)LinkList_Get(tree, 0);
285     
286     if( (trNode != NULL) && (pFunc != NULL) )
287     {  
288         recursive_display(trNode->node, pFunc, 0, gap, div);
289     }
290 }

 1 #ifndef _GTREE_H_
 2 #define _GTREE_H_
 3 
 4 typedef void GTree;
 5 typedef void GTreeData;
 6 typedef void (GTree_Printf)(GTreeData*);
 7 
 8 GTree* GTree_Create();
 9 
10 void GTree_Destroy(GTree* tree);
11 
12 void GTree_Clear(GTree* tree);
13 
14 int GTree_Insert(GTree* tree, GTreeData* data, int pPos);
15 
16 GTreeData* GTree_Delete(GTree* tree, int pos);
17 
18 GTreeData* GTree_Get(GTree* tree, int pos);
19 
20 GTreeData* GTree_Root(GTree* tree);
21 
22 int GTree_Height(GTree* tree);
23 
24 int GTree_Count(GTree* tree);
25 
26 int GTree_Degree(GTree* tree);
27 
28 void GTree_Display(GTree* tree, GTree_Printf* pFunc, int gap, char div);
29 
30 #endif

  1 #include <stdio.h>
  2 #include <malloc.h>
  3 #include "LinkList.h"
  4 
  5 typedef struct _tag_LinkList
  6 {
  7     LinkListNode header;
  8     int length;
  9 } TLinkList;
 10 
 11 LinkList* LinkList_Create() // O(1)
 12 {
 13     TLinkList* ret = (TLinkList*)malloc(sizeof(TLinkList));
 14     
 15     if( ret != NULL )
 16     {
 17         ret->length = 0;
 18         ret->header.next = NULL;
 19     }
 20     
 21     return ret;
 22 }
 23 
 24 void LinkList_Destroy(LinkList* list) // O(1)
 25 {
 26     free(list);
 27 }
 28 
 29 void LinkList_Clear(LinkList* list) // O(1)
 30 {
 31     TLinkList* sList = (TLinkList*)list;
 32     
 33     if( sList != NULL )
 34     {
 35         sList->length = 0;
 36         sList->header.next = NULL;
 37     }
 38 }
 39 
 40 int LinkList_Length(LinkList* list) // O(1)
 41 {
 42     TLinkList* sList = (TLinkList*)list;
 43     int ret = -1;
 44     
 45     if( sList != NULL )
 46     {
 47         ret = sList->length;
 48     }
 49     
 50     return ret;
 51 }
 52 
 53 int LinkList_Insert(LinkList* list, LinkListNode* node, int pos) // O(n)
 54 { 
 55     TLinkList* sList = (TLinkList*)list;
 56     int ret = (sList != NULL) && (pos >= 0) && (node != NULL);
 57     int i = 0;
 58     
 59     if( ret )
 60     {
 61         LinkListNode* current = (LinkListNode*)sList;
 62         
 63         for(i=0; (i<pos) && (current->next != NULL); i++)
 64         {
 65             current = current->next;
 66         }
 67         
 68         node->next = current->next;
 69         current->next = node;
 70         
 71         sList->length++;
 72     }
 73     
 74     return ret;
 75 }
 76 
 77 LinkListNode* LinkList_Get(LinkList* list, int pos) // O(n)
 78 {
 79     TLinkList* sList = (TLinkList*)list;
 80     LinkListNode* ret = NULL;
 81     int i = 0;
 82     
 83     if( (sList != NULL) && (0 <= pos) && (pos < sList->length) )
 84     {
 85         LinkListNode* current = (LinkListNode*)sList;
 86         
 87         for(i=0; i<pos; i++)
 88         {
 89             current = current->next;
 90         }
 91         
 92         ret = current->next;
 93     }
 94     
 95     return ret;
 96 }
 97 
 98 LinkListNode* LinkList_Delete(LinkList* list, int pos) // O(n)
 99 {
100     TLinkList* sList = (TLinkList*)list;
101     LinkListNode* ret = NULL;
102     int i = 0;
103     
104     if( (sList != NULL) && (0 <= pos) && (pos < sList->length) )
105     {
106         LinkListNode* current = (LinkListNode*)sList;
107         
108         for(i=0; i<pos; i++)
109         {
110             current = current->next;
111         }
112         
113         ret = current->next;
114         current->next = ret->next;
115         
116         sList->length--;
117     }
118     
119     return ret;
120 }

 1 #ifndef _LINKLIST_H_
 2 #define _LINKLIST_H_
 3 
 4 typedef void LinkList;
 5 typedef struct _tag_LinkListNode LinkListNode;
 6 struct _tag_LinkListNode
 7 {
 8     LinkListNode* next;
 9 };
10 
11 LinkList* LinkList_Create();
12 
13 void LinkList_Destroy(LinkList* list);
14 
15 void LinkList_Clear(LinkList* list);
16 
17 int LinkList_Length(LinkList* list);
18 
19 int LinkList_Insert(LinkList* list, LinkListNode* node, int pos);
20 
21 LinkListNode* LinkList_Get(LinkList* list, int pos);
22 
23 LinkListNode* LinkList_Delete(LinkList* list, int pos);
24 
25 #endif

 1 #include <stdio.h>
 2 #include "GTree.h"
 3 /* run this program using the console pauser or add your own getch, system("pause") or input loop */
 4 
 5 void printf_data(GTreeData* data)
 6 {
 7     printf("%c", (int)data);
 8 }
 9 
10 int main(int argc, char *argv[])
11 {
12     GTree* tree = GTree_Create();
13     int i = 0;
14     
15     GTree_Insert(tree, (GTreeData*)'A', -1);
16     GTree_Insert(tree, (GTreeData*)'B', 0);
17     GTree_Insert(tree, (GTreeData*)'C', 0);
18     GTree_Insert(tree, (GTreeData*)'D', 0);
19     GTree_Insert(tree, (GTreeData*)'E', 1);
20     GTree_Insert(tree, (GTreeData*)'F', 1);
21     GTree_Insert(tree, (GTreeData*)'H', 3);
22     GTree_Insert(tree, (GTreeData*)'I', 3);
23     GTree_Insert(tree, (GTreeData*)'J', 3);
24     
25     printf("Tree Height: %d
", GTree_Height(tree));
26     printf("Tree Degree: %d
", GTree_Degree(tree));
27     printf("Full Tree:
");
28     
29     GTree_Display(tree, printf_data, 2, ' ');
30     
31     printf("Get Tree Data:
");
32     
33     for(i=0; i<GTree_Count(tree); i++)
34     {
35         printf_data(GTree_Get(tree, i));
36         printf("
");
37     }
38     
39     printf("Get Root Data:
");
40     
41     printf_data(GTree_Root(tree));
42     
43     printf("
");
44     
45     GTree_Delete(tree, 3);
46      
47     printf("After Deleting D:
");
48     
49     GTree_Display(tree, printf_data, 2, '-');
50     
51     GTree_Clear(tree);
52     
53     printf("After Clearing Tree:
");
54     
55     GTree_Display(tree, printf_data, 2, '.');
56         
57     GTree_Destroy(tree);
58     
59     return 0;
60 }