树2

  1 #include <stdio.h>
  2 #include <malloc.h>
  3 #include "BTree.h"
  4 
  5 typedef struct _tag_BTree TBTree;//BTree.c
  6 struct _tag_BTree
  7 {
  8     int count;
  9     BTreeNode* root;
 10 };
 11 
 12 static void recursive_display(BTreeNode* node, BTree_Printf* pFunc, int format, int gap, char div) // O(n)
 13 {
 14     int i = 0;
 15     
 16     if( (node != NULL) && (pFunc != NULL) )
 17     {
 18         for(i=0; i<format; i++)
 19         {
 20             printf("%c", div);
 21         }
 22         
 23         pFunc(node);
 24         
 25         printf("
");
 26         
 27         if( (node->left != NULL) || (node->right != NULL) )
 28         {
 29             recursive_display(node->left, pFunc, format + gap, gap, div);
 30             recursive_display(node->right, pFunc, format + gap, gap, div);
 31         }
 32     }
 33     else
 34     {
 35         for(i=0; i<format; i++)
 36         {
 37             printf("%c", div);
 38         }
 39         printf("
");
 40     }
 41 }
 42 
 43 static int recursive_count(BTreeNode* root) // O(n)
 44 {
 45     int ret = 0;
 46     
 47     if( root != NULL )
 48     {
 49         ret = recursive_count(root->left) + 1 + recursive_count(root->right);
 50     }
 51     
 52     return ret;
 53 }
 54 
 55 static int recursive_height(BTreeNode* root) // O(n)
 56 {
 57     int ret = 0;
 58     
 59     if( root != NULL )
 60     {
 61         int lh = recursive_height(root->left);
 62         int rh = recursive_height(root->right);
 63         
 64         ret = ((lh > rh) ? lh : rh) + 1;
 65     }
 66     
 67     return ret;
 68 }
 69 
 70 static int recursive_degree(BTreeNode* root) // O(n)
 71 {
 72     int ret = 0;
 73     
 74     if( root != NULL )
 75     {
 76         if( root->left != NULL )
 77         {
 78             ret++;
 79         }
 80         
 81         if( root->right != NULL )
 82         {
 83             ret++;
 84         }
 85         
 86         if( ret == 1 )
 87         {
 88             int ld = recursive_degree(root->left);
 89             int rd = recursive_degree(root->right);
 90             
 91             if( ret < ld )
 92             {
 93                 ret = ld;
 94             }
 95             
 96             if( ret < rd )
 97             {
 98                 ret = rd;
 99             }
100         }
101     }
102     
103     return ret;
104 }
105 
106 BTree* BTree_Create() // O(1)
107 {
108     TBTree* ret = (TBTree*)malloc(sizeof(TBTree));
109     
110     if( ret != NULL )
111     {
112         ret->count = 0;
113         ret->root = NULL;
114     }
115     
116     return ret;
117 }
118 
119 void BTree_Destroy(BTree* tree) // O(1)
120 {
121     free(tree);
122 }
123 
124 void BTree_Clear(BTree* tree) // O(1)
125 {
126     TBTree* btree = (TBTree*)tree;
127     
128     if( btree != NULL )
129     {
130         btree->count = 0;
131         btree->root = NULL;
132     }
133 }
134 
135 int BTree_Insert(BTree* tree, BTreeNode* node, BTPos pos, int count, int flag) // O(n) 
136 {
137     TBTree* btree = (TBTree*)tree;
138     int ret = (btree != NULL) && (node != NULL) && ((flag == BT_LEFT) || (flag == BT_RIGHT));
139     int bit = 0;
140     
141     if( ret )
142     {
143         BTreeNode* parent = NULL;
144         BTreeNode* current = btree->root;
145         
146         node->left = NULL;
147         node->right = NULL;
148         
149         while( (count > 0) && (current != NULL) )
150         {
151             bit = pos & 1;
152             pos = pos >> 1;
153             
154             parent = current;
155             
156             if( bit == BT_LEFT )
157             {
158                 current = current->left;
159             }
160             else if( bit == BT_RIGHT )
161             {
162                 current = current->right;
163             }
164             
165             count--;
166         }
167         
168         if( flag == BT_LEFT )
169         {
170             node->left = current;
171         }
172         else if( flag == BT_RIGHT )
173         {
174             node->right = current;
175         }
176         
177         if( parent != NULL )
178         {
179             if( bit == BT_LEFT )
180             {
181                 parent->left = node;
182             }
183             else if( bit == BT_RIGHT )
184             {
185                 parent->right = node;
186             }
187         }
188         else
189         {
190             btree->root = node;
191         }
192         
193         btree->count++;
194     }
195     
196     return ret;
197 }
198 
199 BTreeNode* BTree_Delete(BTree* tree, BTPos pos, int count) // O(n)
200 {
201     TBTree* btree = (TBTree*)tree;
202     BTreeNode* ret = NULL; 
203     int bit = 0;
204     
205     if( btree != NULL )
206     {
207         BTreeNode* parent = NULL;
208         BTreeNode* current = btree->root;
209         
210         while( (count > 0) && (current != NULL) )
211         {
212             bit = pos & 1;
213             pos = pos >> 1;
214             
215             parent = current;
216             
217             if( bit == BT_LEFT )
218             {
219                 current = current->left;
220             }
221             else if( bit == BT_RIGHT )
222             {
223                 current = current->right;
224             }
225             
226             count--;
227         }
228         
229         if( parent != NULL )
230         {
231             if( bit == BT_LEFT )
232             {
233                 parent->left = NULL;
234             }
235             else if( bit == BT_RIGHT )
236             {
237                 parent->right = NULL;
238             }
239         }
240         else
241         {
242             btree->root = NULL;
243         }
244         
245         ret = current;
246         
247         btree->count = btree->count - recursive_count(ret);
248     }
249     
250     return ret;
251 }
252 
253 BTreeNode* BTree_Get(BTree* tree, BTPos pos, int count) // O(n)
254 {
255     TBTree* btree = (TBTree*)tree;
256     BTreeNode* ret = NULL; 
257     int bit = 0;
258     
259     if( btree != NULL )
260     {
261         BTreeNode* current = btree->root;
262         
263         while( (count > 0) && (current != NULL) )
264         {
265             bit = pos & 1;
266             pos = pos >> 1;
267             
268             if( bit == BT_LEFT )
269             {
270                 current = current->left;
271             }
272             else if( bit == BT_RIGHT )
273             {
274                 current = current->right;
275             }
276             
277             count--;
278         }
279         
280         ret = current;
281     }
282     
283     return ret;
284 }
285 
286 BTreeNode* BTree_Root(BTree* tree) // O(1)
287 {
288     TBTree* btree = (TBTree*)tree;
289     BTreeNode* ret = NULL;
290     
291     if( btree != NULL )
292     {
293         ret = btree->root;
294     }
295     
296     return ret;
297 }
298 
299 int BTree_Height(BTree* tree) // O(n)
300 {
301     TBTree* btree = (TBTree*)tree;
302     int ret = 0;
303     
304     if( btree != NULL )
305     {
306         ret = recursive_height(btree->root);
307     }
308     
309     return ret;
310 }
311 
312 int BTree_Count(BTree* tree) // O(1)
313 {
314     TBTree* btree = (TBTree*)tree;
315     int ret = 0;
316     
317     if( btree != NULL )
318     {
319         ret = btree->count;
320     }
321     
322     return ret;
323 }
324 
325 int BTree_Degree(BTree* tree) // O(n)
326 {
327     TBTree* btree = (TBTree*)tree;
328     int ret = 0;
329     
330     if( btree != NULL )
331     {
332         ret = recursive_degree(btree->root);
333     }
334     
335     return ret;
336 }
337 
338 void BTree_Display(BTree* tree, BTree_Printf* pFunc, int gap, char div) // O(n)
339 {
340     TBTree* btree = (TBTree*)tree;
341     
342     if( btree != NULL )
343     {
344         recursive_display(btree->root, pFunc, 0, gap, div);
345     }
346 }

#ifndef _BTREE_H_  //BTree.h

#define BT_LEFT 0
#define BT_RIGHT 1

typedef void BTree;
typedef unsigned long long BTPos;

typedef struct _tag_BTreeNode BTreeNode;
struct _tag_BTreeNode
{
    BTreeNode* left;
    BTreeNode* right;
};

typedef void (BTree_Printf)(BTreeNode*);

BTree* BTree_Create();

void BTree_Destroy(BTree* tree);

void BTree_Clear(BTree* tree);

int BTree_Insert(BTree* tree, BTreeNode* node, BTPos pos, int count, int flag);

BTreeNode* BTree_Delete(BTree* tree, BTPos pos, int count);

BTreeNode* BTree_Get(BTree* tree, BTPos pos, int count);

BTreeNode* BTree_Root(BTree* tree);

int BTree_Height(BTree* tree);

int BTree_Count(BTree* tree);

int BTree_Degree(BTree* tree);

void BTree_Display(BTree* tree, BTree_Printf* pFunc, int gap, char div);

#endif

  1 #include <stdio.h>
  2 #include <malloc.h>
  3 #include "SeqList.h"
  4 
  5 typedef unsigned int TSeqListNode;
  6 
  7 typedef struct _tag_SeqList
  8 {
  9     int capacity;
 10     int length;
 11     TSeqListNode* node;
 12 } TSeqList;
 13 
 14 SeqList* SeqList_Create(int capacity) // O(1)
 15 {
 16     TSeqList* ret = NULL;
 17     
 18     if( capacity >= 0 )
 19     {
 20         ret = (TSeqList*)malloc(sizeof(TSeqList) + sizeof(TSeqListNode) * capacity);
 21     }
 22     
 23     if( ret != NULL )
 24     {
 25         ret->capacity = capacity;
 26         ret->length = 0;
 27         ret->node = (TSeqListNode*)(ret + 1);
 28     }
 29     
 30     return ret;
 31 }
 32 
 33 void SeqList_Destroy(SeqList* list) // O(1)
 34 {
 35     free(list);
 36 }
 37 
 38 void SeqList_Clear(SeqList* list) // O(1)
 39 {
 40     TSeqList* sList = (TSeqList*)list;
 41     
 42     if( sList != NULL )
 43     {
 44         sList->length = 0;
 45     }
 46 }
 47 
 48 int SeqList_Length(SeqList* list) // O(1)
 49 {
 50     TSeqList* sList = (TSeqList*)list;
 51     int ret = -1;
 52     
 53     if( sList != NULL )
 54     {
 55         ret = sList->length;
 56     }
 57     
 58     return ret;
 59 }
 60 
 61 int SeqList_Capacity(SeqList* list) // O(1)
 62 {
 63     TSeqList* sList = (TSeqList*)list;
 64     int ret = -1;
 65     
 66     if( sList != NULL )
 67     {
 68         ret = sList->capacity;
 69     }
 70     
 71     return ret;
 72 }
 73 
 74 int SeqList_Insert(SeqList* list, SeqListNode* node, int pos) // O(n) 
 75 {
 76     TSeqList* sList = (TSeqList*)list;
 77     int ret = (sList != NULL);
 78     int i = 0;
 79     
 80     ret = ret && (sList->length + 1 <= sList->capacity);
 81     ret = ret && (0 <= pos);
 82     
 83     if( ret )
 84     {
 85         if( pos >= sList->length )
 86         {
 87             pos = sList->length;
 88         }
 89         
 90         for(i=sList->length; i>pos; i--)
 91         {
 92             sList->node[i] = sList->node[i-1];
 93         }
 94         
 95         sList->node[i] = (TSeqListNode)node;
 96         
 97         sList->length++;
 98     }
 99     
100     return ret;
101 }
102 
103 SeqListNode* SeqList_Get(SeqList* list, int pos) // O(1) 
104 {
105     TSeqList* sList = (TSeqList*)list;
106     SeqListNode* ret = NULL;
107     
108     if( (sList != NULL) && (0 <= pos) && (pos <= sList->length) )
109     {
110         ret = (SeqListNode*)(sList->node[pos]);
111     }
112     
113     return ret;
114 }
115 
116 SeqListNode* SeqList_Delete(SeqList* list, int pos) // O(n)
117 {
118     TSeqList* sList = (TSeqList*)list;
119     SeqListNode* ret = SeqList_Get(list, pos);
120     int i = 0;
121     
122     if( ret != NULL )
123     {
124         for(i=pos+1; i<sList->length; i++)
125         {
126             sList->node[i-1] = sList->node[i];
127         }
128         
129         sList->length--;
130     }
131     
132     return ret;
133 }

 1 #ifndef _SEQLIST_H_
 2 #define _SEQLIST_H_
 3 
 4 typedef void SeqList;
 5 typedef void SeqListNode;
 6 
 7 SeqList* SeqList_Create(int capacity);
 8 
 9 void SeqList_Destroy(SeqList* list);
10 
11 void SeqList_Clear(SeqList* list);
12 
13 int SeqList_Length(SeqList* list);
14 
15 int SeqList_Capacity(SeqList* list);
16 
17 int SeqList_Insert(SeqList* list, SeqListNode* node, int pos);
18 
19 SeqListNode* SeqList_Get(SeqList* list, int pos);
20 
21 SeqListNode* SeqList_Delete(SeqList* list, int pos);
22 
23 #endif

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include "BTree.h"
  4 #include "SeqList.h"
  5 
  6 /* run this program using the console pauser or add your own getch, system("pause") or input loop */
  7 
  8 struct Node
  9 {
 10     BTreeNode header;
 11     char v;
 12 };
 13 
 14 void printf_data(BTreeNode* node)
 15 {
 16     if( node != NULL )
 17     {
 18         printf("%c", ((struct Node*)node)->v);
 19     }
 20 }
 21 
 22 void thread_via_left(BTreeNode* root, BTreeNode** pp)
 23 {
 24     if( (root != NULL) && (pp != NULL) )
 25     {
 26         if( *pp != NULL )
 27         {
 28             (*pp)->left = root;
 29             *pp = NULL;
 30         }
 31         
 32         if( root->left == NULL )
 33         {
 34             *pp = root;
 35         }
 36         
 37         thread_via_left(root->left, pp);
 38         thread_via_left(root->right, pp);
 39     }
 40 }
 41 
 42 void thread_via_list(BTreeNode* root, SeqList* list)
 43 {
 44     if( (root != NULL) && (list != NULL) )
 45     {
 46         SeqList_Insert(list, (SeqListNode*)root, SeqList_Length(list));
 47         
 48         thread_via_list(root->left, list);
 49         thread_via_list(root->right, list);
 50     }
 51 }
 52 
 53 int main(int argc, char *argv[])
 54 {
 55     BTree* tree = BTree_Create();
 56     BTreeNode* current = NULL;
 57     BTreeNode* p = NULL;
 58     SeqList* list = NULL;
 59     int i = 0;
 60     
 61     struct Node n1 = {{NULL, NULL}, 'A'};
 62     struct Node n2 = {{NULL, NULL}, 'B'};
 63     struct Node n3 = {{NULL, NULL}, 'C'};
 64     struct Node n4 = {{NULL, NULL}, 'D'};
 65     struct Node n5 = {{NULL, NULL}, 'E'};
 66     struct Node n6 = {{NULL, NULL}, 'F'};
 67     
 68     BTree_Insert(tree, (BTreeNode*)&n1, 0, 0, 0);
 69     BTree_Insert(tree, (BTreeNode*)&n2, 0x00, 1, 0);
 70     BTree_Insert(tree, (BTreeNode*)&n3, 0x01, 1, 0);
 71     BTree_Insert(tree, (BTreeNode*)&n4, 0x00, 2, 0);
 72     BTree_Insert(tree, (BTreeNode*)&n5, 0x02, 2, 0);
 73     BTree_Insert(tree, (BTreeNode*)&n6, 0x02, 3, 0);
 74     
 75     printf("Full Tree: 
");
 76     
 77     BTree_Display(tree, printf_data, 4, '-');
 78     
 79     printf("Thread via List:
");
 80     
 81     list = SeqList_Create(BTree_Count(tree));
 82     
 83     thread_via_list(BTree_Root(tree), list);
 84     
 85     for(i=0; i<SeqList_Length(list); i++)
 86     {
 87         printf("%c, ", ((struct Node*)SeqList_Get(list, i))->v);
 88     }
 89     
 90     printf("
");
 91     
 92     printf("Thread via Left:
");
 93     
 94     current = BTree_Root(tree);
 95     
 96     thread_via_left(current, &p);
 97     
 98     while( current != NULL )
 99     {
100         printf("%c, ", ((struct Node*)current)->v);
101         
102         current = current->left;
103     }
104     
105     printf("
");
106     
107     BTree_Destroy(tree);
108     
109     return 0;
110 }