Category : Files from Magazines
Archive : TREE_DDJ.ZIP
Filename : TREE.C
Output of file : TREE.C contained in archive : TREE_DDJ.ZIP
------------------------------------------------------------------------------
1 #include
2
3 /* TREE.C: Various binary tree routines:
4 *
5 * (C) 1986, Allen I. Holub. All rights reserved.
6 */
7
8 typedef struct _n
9 {
10 struct _n *left;
11 struct _n *right;
12 char *key;
13 }
14 LEAF;
15
16 char *Map;
17 extern char *makebitmap();
18
19 /*----------------------------------------------------------------------
20 * These defines are used by the lr_trav() routine:
21 */
22
23 #define mark(p) ( *( (p)->key ) |= 0x80 )
24 #define marked(p) ( *( (p)->key ) & 0x80 )
25 #define unmark(p) ( *( (p)->key ) &= ~0x80 )
26 #define visit(root) printf("%s ", root->key );
27
28 /*----------------------------------------------------------------------*/
29
30 tree( key, rootp )
31 char *key;
32 LEAF **rootp; /* POINTER to (not the contents of) the root */
33 {
34 /* Non-recursive binary tree search and insert function. If key
35 * is in the tree a message to that effect is printed, otherwise
36 * a node containing key is inserted into the tree at the
37 * proper place.
38 */
39
40 LEAF *root = *rootp ;
41 LEAF **insert_here = rootp ;
42 LEAF *malloc();
43 int rel;
44
45 while( root )
46 {
47 if( (rel = strcmp(key, root->key)) == 0 )
48 {
49 printf("key <%s> in tree\n", key );
50 return;
51 }
52 else
53 {
54 insert_here = (rel < 0) ? &root->left : &root->right ;
55 root = *insert_here ;
56 }
57 }
58
59 if( *insert_here = root = malloc(sizeof(LEAF)) )
60 {
61 root->right = root->left = NULL;
62 root->key = key;
63 }
64 else
65 printf("Out of memory.\n");
66 }
67
68 /*----------------------------------------------------------------------*/
69
70 sinorder( root )
71 LEAF *root;
72 {
73 /* A simple recursive in-order traversal, each node is printed
74 * with as many tabs to it's left as it is deep in the tree.
75 * (if a node is at depth 4 then 4 tabs are printed).
76 */
77
78 static int depth = -1;
79 register int i;
80
81 if( root )
82 {
83 depth++;
84
85 inorder( root->left );
86 for(i = depth; --i >= 0 ; putchar('\t') )
87 ;
88
89 printf( "%s\n", root->key );
90 inorder( root->right );
91
92 depth--;
93 }
94 }
95
96 /*----------------------------------------------------------------------
97 * inorder():
98 *
99 * Does an recursive in-order traversal of a binary tree, printing
100 * it in graphic form (showing the various pointers). Note that
101 * the traverse order is reversed (go right, print root, go left)
102 * so that a mirror image of the tree won't be printed (normal
103 * traversal would result in the leftmost node of the left subtree
104 * being printed first).
105 *
106 * | is associated with this depth in the bitmap:
107 * 1 2 3
108 * | | |
109 * V V |
110 * V
111 * +---1---+
112 * | | +---2
113 * | +---2---+
114 * 0---+ Node number == depth in tree.
115 * | +---2
116 * +---1---+
117 * +---2
118 */
119
120 inorder( root, amleft )
121 LEAF *root; /* Root of current subtree */
122 int amleft; /* Root is a left decendant of the parent */
123 {
124
125 static int depth = -1; /* Current depth in the tree */
126 int i;
127
128 if( root )
129 {
130 ++depth;
131
132 if( root->right )
133 inorder( root->right, 0 );
134 else
135 setbit( depth+1, Map, 1 );
136
137 for(i = 1; i <= depth ; i++ )
138 {
139 printf( i == depth ? " +---" :
140 testbit(i,Map) ? " | " :
141 " " );
142 }
143
144 printf( "%s%s\n", root->key,
145 root->left || root->right ? "---+" : "" );
146
147 setbit( depth, Map, amleft ? 0 : 1 );
148
149 if( root->left )
150 inorder( root->left, 1 );
151 else
152 setbit( depth+1, Map, 0 );
153
154 --depth;
155 }
156 }
157
158
159
160 /*----------------------------------------------------------------------*/
161
162
163 pline( depth )
164 {
165 int i;
166 for(i = 0; i < depth-1 ; i++ )
167 printf( testbit(i,Map) ? "| " : " " );
168 }
169
170 /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
171
172 preorder( root, amright )
173 LEAF *root;
174 {
175 /* Does a recursive pre-order traversal of a binary tree printing
176 * the tree in graphic form. Though this routine is interesting,
177 * it is more useful when adapted to multi-way tree traversal
178 * for use in such aplications a printing directory trees.
179 */
180
181 static int depth = -1;
182
183 if( root )
184 {
185 pline( ++depth );
186 printf( "%s%s\n", depth ? "+-------" : "" , root->key );
187
188 if( root->right )
189 setbit( depth, Map, 1 );
190
191 preorder( root->left, 0 );
192 setbit ( depth, Map, 0 );
193 preorder( root->right, 1 );
194
195 if( amright && !(root->right || root->left) )
196 {
197 pline( depth );
198 printf("\n");
199 }
200
201 depth--;
202 }
203 }
204
205 /*----------------------------------------------------------------------
206 * lr_trav() (below) does a non-recursive link-reversal traversal of a
207 * binary tree. The algorithm used is:
208 *
209 * do forever
210 * if( marked( pres ) )
211 * clear mark
212 * else
213 * while( there's a left child )
214 * preorder visit
215 * go left
216 *
217 * inorder & preorder visit
218 *
219 * postorder visit
220 *
221 * if( no previous node )
222 * break
223 *
224 * if( marked( prev ) )
225 * go up from a right child
226 * else
227 * go up from a left child
228 * inorder visit
229 * set mark
230 * go right
231 *
232 * "Go" means to decend one node in the tree, reversing the pointer
233 * to that node so that it points back up where we came from.
234 * If we "go left" then we reverse the the left pointer;
235 * if we "go right" then right pointer is reversed. "Go up" means
236 * return to the previous node and make the pointer point back to
237 * its original location. A node is marked after we have
238 * traversed its left sub-tree. The mark is cleared after we've
239 * traversed both the left and right sub-trees. The high bit of
240 * the "key" field is used to mark the node, you could also add
241 * another field to the structure if you have a numeric key. Only
242 * one bit is needed for the mark.
243 */
244
245 lr_trav( pres )
246 LEAF *pres;
247 {
248 LEAF *prev = NULL, *next;
249
250 while( 1 )
251 {
252 if( marked(pres) )
253 unmark( pres );
254 else
255 {
256 while( next = pres->left )
257 {
258 /* preorder visit */
259 /* goes here */
260
261 pres->left = prev; /* go left */
262 prev = pres;
263 pres = next;
264 }
265 visit( pres ); /* inorder & pre- */
266 /* order visit */
267 }
268
269 /* postorder visit goes here */
270
271 if( !prev )
272 break;
273
274 if( marked(prev) )
275 {
276 next = prev->right; /* go up from a */
277 prev->right = pres; /* right child */
278 pres = prev;
279 prev = next;
280 }
281 else
282 {
283 next = prev->left; /* go up from a */
284 prev->left = pres; /* left child */
285 pres = prev;
286 prev = next;
287
288 visit( pres ); /* inorder visit */
289
290 mark( pres ); /* mark the node */
291 if( next = pres->right ) /* go right */
292 {
293 pres->right = prev;
294 prev = pres;
295 pres = next;
296 }
297 }
298 }
299
300 printf("\n");
301 }
302
303 /*----------------------------------------------------------------------*/
304
305 main(argc, argv)
306 char **argv;
307 {
308 static LEAF *root = NULL ;
309 char buf[128];
310
311 Map = makebitmap( 128 );
312
313 #ifdef MODE1
314 for( printf("? "); gets(buf); printf("? ") )
315 {
316 tree( strsave(buf), &root );
317 lr_trav ( root );
318 inorder ( root , 0 );
319 preorder( root , 0 );
320 }
321 #endif
322
323 while( --argc > 0 )
324 tree( *++argv, &root );
325
326 inorder ( root , 0 );
327 }
.MDUL/
Very nice! Thank you for this wonderful archive. I wonder why I found it only now. Long live the BBS file archives!
This is so awesome! 😀 I’d be cool if you could download an entire archive of this at once, though.
But one thing that puzzles me is the “mtswslnkmcjklsdlsbdmMICROSOFT” string. There is an article about it here. It is definitely worth a read: http://www.os2museum.com/wp/mtswslnk/