source: trunk/src/helpers/tree.c@ 8

Last change on this file since 8 was 8, checked in by umoeller, 25 years ago

Initial checkin of helpers code which used to be in WarpIN.
  • Property svn:eol-style set to CRLF
  • Property svn:keywords set to Author Date Id Revision
File size: 26.4 KB
Line 
1
2/*
3 *@@sourcefile tree.c:
4 * contains helper functions for maintaining 'Red-Black' balanced
5 * binary trees.
6 * See explanations below.
7 *
8 * This file is all new with V0.9.5 (2000-09-29) [umoeller].
9 *
10 * Usage: All C programs; not OS/2-specific.
11 *
12 * Function prefixes (new with V0.81):
13 * -- tree* tree helper functions
14 *
15 * This has been taken from the Standard Function Library (SFL)
16 * by iMatix Corporation and changed to user the "id" member for
17 * tree sorting/comparison.
18 *
19 * <B>Using binary trees</B>
20 *
21 * Each TREE node does not only contain data, but also an
22 * "id" field. The order of nodes in the tree is determined
23 * by calling a node comparison function provided by the caller
24 * (which you must write). This takes two "id" values and must
25 * return:
26 *
27 + 0: id1 == id2
28 + -1: id1 < id2
29 + +1: id1 > id2
30 *
31 * Initialize the root of the tree with treeInit(). Then
32 * add nodes to the tree with treeInsertID() and remove nodes
33 * with treeDelete().
34 *
35 * You can test whether a tree is empty by comparing its
36 * root with TREE_NULL.
37 *
38 * Compared to linked lists (as implemented by linklist.c),
39 * trees allow for much faster searching.
40 *
41 * Assuming a linked list contains N items, then searching the
42 * list for an item will take an average of N/2 comparisons
43 * and even N comparisons if the item cannot be found (unless
44 * you keep the list sorted, but linklist.c doesn't do this).
45 *
46 * According to "Algorithms in C", a search in a balanced
47 * "red-black" binary tree takes about lg N comparisons on
48 * average, and insertions take less than one rotation on
49 * average.
50 *
51 * Example: You need to build a list of files, and you
52 * will search the list frequently according to the file
53 * handles. This would make the handle an ideal "id" field.
54 *
55 * Differences compared to linklist.c:
56 *
57 * -- As opposed to a LISTNODE, the TREE structure (which
58 * represents a tree node) does not contain a data pointer.
59 * Instead, all tree nodes are assumed to contain the
60 * data themselves. As a result, you must define your
61 * own structures which start with a TREE structure.
62 *
63 * See treeInsertID() for samples.
64 *
65 * -- You must supply a comparison function to allow the
66 * tree functions to sort the tree.
67 *
68 *@@added V0.9.5 (2000-09-29) [umoeller]
69 *@@header "helpers\tree.h"
70 */
71
72/*
73 * Written: 97/11/18 Jonathan Schultz <jonathan@imatix.com>
74 * Revised: 98/12/08 Jonathan Schultz <jonathan@imatix.com>
75 *
76 * Copyright (C) 1991-99 iMatix Corporation.
77 * Copyright (C) 2000 Ulrich M”ller.
78 * This file is part of the XWorkplace source package.
79 * XWorkplace is free software; you can redistribute it and/or modify
80 * it under the terms of the GNU General Public License as published
81 * by the Free Software Foundation, in version 2 as it comes in the
82 * "COPYING" file of the XWorkplace main distribution.
83 * This program is distributed in the hope that it will be useful,
84 * but WITHOUT ANY WARRANTY; without even the implied warranty of
85 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
86 * GNU General Public License for more details.
87 */
88
89/*
90 *@@category: Helpers\C helpers\Red-black balanced binary trees
91 */
92
93#include "setup.h"
94#include "helpers\tree.h"
95
96// Constants
97TREE TREE_EMPTY = {TREE_NULL, TREE_NULL, NULL, BLACK};
98
99// Internal function prototypes
100static void insert_fixup(TREE **root, TREE *tree);
101static void rotate_left(TREE **root, TREE *tree);
102static void rotate_right(TREE **root, TREE *tree);
103static void delete_fixup(TREE **root, TREE *tree);
104
105/*
106 *@@ treeInit:
107 * initializes an empty tree. The data on the
108 * tree will be invalid, and no memory will be
109 * freed.
110 *
111 * Usage:
112 + TREE *TreeRoot;
113 + treeInit(&TreeRoot);
114 */
115
116void treeInit(TREE **root)
117{
118 *root = TREE_NULL;
119}
120
121/*
122 *@@ treeInsertID:
123 * inserts a node into an existing tree.
124 *
125 * Note: A tree node MUST contain a TREE structure
126 * at the beginning for the tree functions to work.
127 * So to create a tree node with usable data, do this:
128 *
129 + typedef _MYTREENODE
130 + {
131 + // TREE must be at beginning
132 + TREE Tree;
133 + // now use whatever you want
134 + CHAR szMyExtraData[100];
135 + } MYTREENODE, *PMYTREENODE;
136 *
137 * When calling the tree functions, manually cast your
138 * MYTREENODE pointers to (TREE*).
139 *
140 * This function initialises the node pointers and colour
141 * in the TREE structure to correct values, so the caller
142 * does not have to worry about those.
143 *
144 * However you must initialize the TREE.id member correctly
145 * so that your comparison function can compare on that
146 * to find the correct place in the tree to insert the node.
147 *
148 * Usage:
149 + TREE *TreeRoot;
150 + treeInit(&TreeRoot);
151 +
152 + PMYTREENODE pTreeItem = malloc(sizeof(MYTREENODE));
153 + pTreeItem->Tree.id = 1;
154 +
155 + treeInsertID(&TreeRoot,
156 + (TREE*)pTreeItem,
157 + fnCompare, // your comparison function
158 + FALSE);
159 *
160 * Returns:
161 *
162 * -- TREE_OK: OK, item inserted.
163 *
164 * -- TREE_DUPLICATE: if (fAllowDuplicates == FALSE), this is
165 * returned if a tree item with the specified ID already
166 * exists.
167 */
168
169int treeInsertID(TREE **root, // in: root of tree
170 TREE *tree, // in: new tree node
171 FNTREE_COMPARE_IDS *comp, // in: comparison function
172 BOOL fAllowDuplicates) // in: whether duplicates with the same ID are allowed
173{
174 TREE
175 *current,
176 *parent;
177 int
178 last_comp = 0;
179
180 // find where node belongs
181 current = *root;
182 parent = NULL;
183 while (current != TREE_NULL)
184 {
185 parent = current;
186 last_comp = comp(tree->id, current->id);
187 switch (last_comp)
188 {
189 case -1: current = current->left; break;
190 case 1: current = current->right; break;
191 default: if (fAllowDuplicates)
192 current = current->left;
193 else
194 return TREE_DUPLICATE;
195
196 }
197 }
198
199 // setup new node
200 ((TREE *) tree)->parent = parent;
201 ((TREE *) tree)->left = TREE_NULL;
202 ((TREE *) tree)->right = TREE_NULL;
203 ((TREE *) tree)->colour = RED;
204
205 // insert node in tree
206 if (parent)
207 switch (last_comp)
208 {
209 case 1: parent->right = tree; break;
210 default: parent->left = tree;
211 }
212 else
213 *root = tree;
214
215 insert_fixup(root, tree);
216 return(TREE_OK);
217}
218
219/*
220 *@@ treeInsertNode:
221 * similar to treeInsertID, but this uses
222 * a comparision function which compares
223 * nodes.
224 */
225
226int treeInsertNode(TREE **root, // in: root of tree
227 TREE *tree, // in: new tree node
228 FNTREE_COMPARE_NODES *comp, // in: comparison function
229 BOOL fAllowDuplicates) // in: whether duplicates with the same ID are allowed
230{
231 TREE
232 *current,
233 *parent;
234 int
235 last_comp = 0;
236
237 // find where node belongs
238 current = *root;
239 parent = NULL;
240 while (current != TREE_NULL)
241 {
242 parent = current;
243 last_comp = comp(tree, current);
244 switch (last_comp)
245 {
246 case -1: current = current->left; break;
247 case 1: current = current->right; break;
248 default: if (fAllowDuplicates)
249 current = current->left;
250 else
251 return TREE_DUPLICATE;
252
253 }
254 }
255
256 // setup new node
257 ((TREE *) tree)->parent = parent;
258 ((TREE *) tree)->left = TREE_NULL;
259 ((TREE *) tree)->right = TREE_NULL;
260 ((TREE *) tree)->colour = RED;
261
262 // insert node in tree
263 if (parent)
264 switch (last_comp)
265 {
266 case 1: parent->right = tree; break;
267 default: parent->left = tree;
268 }
269 else
270 *root = tree;
271
272 insert_fixup(root, tree);
273 return(TREE_OK);
274}
275
276/*
277 * insert_fixup:
278 * maintains the Red-Black tree balance after a node has been inserted.
279 *
280 * Private function.
281 */
282
283static void insert_fixup(TREE **root,
284 TREE *tree)
285{
286 TREE *uncle;
287
288 // check red-black properties
289 while ((tree != *root)
290 && (tree->parent->colour == RED))
291 {
292 // we have a violation
293 if (tree->parent == tree->parent->parent->left)
294 {
295 uncle = tree->parent->parent->right;
296 if (uncle->colour == RED)
297 {
298 // uncle is RED
299 tree ->parent->colour = BLACK;
300 uncle->colour = BLACK;
301 tree ->parent->parent->colour = RED;
302
303 tree = tree->parent->parent;
304 }
305 else
306 {
307 // uncle is BLACK
308 if (tree == tree->parent->right)
309 {
310 // make tree a left child
311 tree = tree->parent;
312 rotate_left (root, tree);
313 }
314
315 // recolor and rotate
316 tree->parent->colour = BLACK;
317 tree->parent->parent->colour = RED;
318 rotate_right (root, tree->parent->parent);
319 }
320 }
321 else
322 {
323 // mirror image of above code
324 uncle = tree->parent->parent->left;
325 if (uncle->colour == RED)
326 {
327 // uncle is RED
328 tree ->parent->colour = BLACK;
329 uncle->colour = BLACK;
330 tree ->parent->parent->colour = RED;
331
332 tree = tree->parent->parent;
333 }
334 else
335 {
336 // uncle is BLACK
337 if (tree == tree->parent->left)
338 {
339 tree = tree->parent;
340 rotate_right (root, tree);
341 }
342 tree->parent->colour = BLACK;
343 tree->parent->parent->colour = RED;
344 rotate_left (root, tree->parent->parent);
345 }
346 }
347 }
348 (*root)->colour = BLACK;
349}
350
351/*
352 * rotate_left:
353 * rotates tree to left.
354 *
355 * Private function.
356 */
357
358static void rotate_left(TREE **root,
359 TREE *tree)
360{
361 TREE *other = tree->right;
362
363 // establish tree->right link
364 tree->right = other->left;
365 if (other->left != TREE_NULL)
366 other->left->parent = tree;
367
368 // establish other->parent link
369 if (other != TREE_NULL)
370 other->parent = tree->parent;
371
372 if (tree->parent)
373 {
374 if (tree == tree->parent->left)
375 tree->parent->left = other;
376 else
377 tree->parent->right = other;
378 }
379 else
380 *root = other;
381
382 // link tree and other
383 other->left = tree;
384 if (tree != TREE_NULL)
385 tree->parent = other;
386}
387
388/*
389 * rotate_right:
390 * rotates tree to right.
391 *
392 * Private function.
393 */
394
395static void rotate_right(TREE **root,
396 TREE *tree)
397{
398 TREE *other;
399
400 other = tree->left;
401
402 // establish tree->left link
403 tree->left = other->right;
404 if (other->right != TREE_NULL)
405 other->right->parent = tree;
406
407 // establish other->parent link
408 if (other != TREE_NULL)
409 other->parent = tree->parent;
410
411 if (tree->parent)
412 {
413 if (tree == tree->parent->right)
414 tree->parent->right = other;
415 else
416 tree->parent->left = other;
417 }
418 else
419 *root = other;
420
421 // link tree and other
422 other->right = tree;
423 if (tree != TREE_NULL)
424 tree->parent = other;
425}
426
427/*
428 *@@ treeDelete:
429 * deletes a node from a tree. Does not deallocate any memory.
430 *
431 * Returns:
432 *
433 * -- TREE_OK: node deleted.
434 * -- TREE_INVALID_NODE: tree node not found.
435 */
436
437int treeDelete(TREE **root, // in: root of tree
438 TREE *tree) // in: tree node to delete
439{
440 int irc = TREE_OK;
441
442 TREE
443 *youngest, *descendent;
444 TREE_COLOUR
445 colour;
446
447 if ( (!tree)
448 || (tree == TREE_NULL)
449 )
450 return TREE_INVALID_NODE;
451
452 if ( (((TREE *) tree)->left == TREE_NULL)
453 || (((TREE *) tree)->right == TREE_NULL)
454 )
455 // descendent has a TREE_NULL node as a child
456 descendent = tree;
457 else
458 {
459 // find tree successor with a TREE_NULL node as a child
460 descendent = ((TREE *) tree)->right;
461 while (descendent->left != TREE_NULL)
462 descendent = descendent->left;
463 }
464
465 // youngest is descendent's only child, if there is one, else TREE_NULL
466 if (descendent->left != TREE_NULL)
467 youngest = descendent->left;
468 else
469 youngest = descendent->right;
470
471 // remove descendent from the parent chain
472 if (youngest != TREE_NULL)
473 youngest->parent = descendent->parent;
474 if (descendent->parent)
475 if (descendent == descendent->parent->left)
476 descendent->parent->left = youngest;
477 else
478 descendent->parent->right = youngest;
479 else
480 *root = youngest;
481
482 colour = descendent->colour;
483
484 if (descendent != (TREE *) tree)
485 {
486 // Conceptually what we are doing here is moving the data from
487 // descendent to tree. In fact we do this by linking descendent
488 // into the structure in the place of tree.
489 descendent->left = ((TREE *) tree)->left;
490 descendent->right = ((TREE *) tree)->right;
491 descendent->parent = ((TREE *) tree)->parent;
492 descendent->colour = ((TREE *) tree)->colour;
493
494 if (descendent->parent)
495 {
496 if (tree == descendent->parent->left)
497 descendent->parent->left = descendent;
498 else
499 descendent->parent->right = descendent;
500 }
501 else
502 *root = descendent;
503
504 if (descendent->left != TREE_NULL)
505 descendent->left->parent = descendent;
506
507 if (descendent->right != TREE_NULL)
508 descendent->right->parent = descendent;
509 }
510
511 if ( (youngest != TREE_NULL)
512 && (colour == BLACK))
513 delete_fixup (root, youngest);
514
515 return (irc);
516}
517
518/*
519 *@@ delete_fixup:
520 * maintains Red-Black tree balance after deleting a node.
521 *
522 * Private function.
523 */
524
525static void delete_fixup(TREE **root,
526 TREE *tree)
527{
528 TREE
529 *sibling;
530
531 while (tree != *root && tree->colour == BLACK)
532 {
533 if (tree == tree->parent->left)
534 {
535 sibling = tree->parent->right;
536 if (sibling->colour == RED)
537 {
538 sibling->colour = BLACK;
539 tree->parent->colour = RED;
540 rotate_left (root, tree->parent);
541 sibling = tree->parent->right;
542 }
543 if ((sibling->left->colour == BLACK)
544 && (sibling->right->colour == BLACK))
545 {
546 sibling->colour = RED;
547 tree = tree->parent;
548 }
549 else
550 {
551 if (sibling->right->colour == BLACK)
552 {
553 sibling->left->colour = BLACK;
554 sibling->colour = RED;
555 rotate_right (root, sibling);
556 sibling = tree->parent->right;
557 }
558 sibling->colour = tree->parent->colour;
559 tree->parent->colour = BLACK;
560 sibling->right->colour = BLACK;
561 rotate_left (root, tree->parent);
562 tree = *root;
563 }
564 }
565 else
566 {
567 sibling = tree->parent->left;
568 if (sibling->colour == RED)
569 {
570 sibling->colour = BLACK;
571 tree->parent->colour = RED;
572 rotate_right (root, tree->parent);
573 sibling = tree->parent->left;
574 }
575 if ((sibling->right->colour == BLACK)
576 && (sibling->left->colour == BLACK))
577 {
578 sibling->colour = RED;
579 tree = tree->parent;
580 }
581 else
582 {
583 if (sibling->left->colour == BLACK)
584 {
585 sibling->right->colour = BLACK;
586 sibling->colour = RED;
587 rotate_left (root, sibling);
588 sibling = tree->parent->left;
589 }
590 sibling->colour = tree->parent->colour;
591 tree->parent->colour = BLACK;
592 sibling->left->colour = BLACK;
593 rotate_right (root, tree->parent);
594 tree = *root;
595 }
596 }
597 }
598 tree->colour = BLACK;
599}
600
601/*
602 *@@ treeFindEQID:
603 * finds a node with ID exactly matching that provided.
604 * To find a tree node, your comparison function must
605 * compare the tree node IDs.
606 */
607
608void* treeFindEQID(TREE **root,
609 unsigned long id,
610 FNTREE_COMPARE_IDS *comp)
611{
612 TREE
613 *current = *root,
614 *found;
615
616 found = NULL;
617 while (current != TREE_NULL)
618 switch (comp(current->id, id))
619 {
620 case -1: current = current->right; break;
621 case 1: current = current->left; break;
622 default: found = current; // In case of duplicates,
623 current = current->left; // get the first one.
624 }
625
626 return found;
627}
628
629/*
630 *@@ treeFindGEID:
631 * finds a node with ID greater than or equal to provided.
632 * To find a tree node, your comparison function must
633 * compare the tree node IDs.
634 */
635
636void* treeFindGEID(TREE **root,
637 unsigned long idFind,
638 FNTREE_COMPARE_IDS *comp)
639{
640 TREE
641 *current = *root,
642 *found;
643
644 found = NULL;
645 while (current != TREE_NULL)
646 switch (comp(current->id, idFind))
647 {
648 case -1: current = current->right; break;
649 default: found = current;
650 current = current->left;
651 }
652
653 return found;
654}
655
656/*
657 *@@ treeFindEQNode:
658 * finds a node with ID exactly matching that provided.
659 * To find a tree node, your comparison function must
660 * compare the tree nodes.
661 */
662
663void* treeFindEQNode(TREE **root,
664 TREE *nodeFind,
665 FNTREE_COMPARE_NODES *comp)
666{
667 TREE
668 *current = *root,
669 *found;
670
671 found = NULL;
672 while (current != TREE_NULL)
673 switch (comp(current, nodeFind))
674 {
675 case -1: current = current->right; break;
676 case 1: current = current->left; break;
677 default: found = current; // In case of duplicates,
678 current = current->left; // get the first one.
679 }
680
681 return found;
682}
683
684/*
685 *@@ treeFindGENode:
686 * finds a node with ID greater than or equal to provided.
687 * To find a tree node, your comparison function must
688 * compare the tree nodes.
689 */
690
691void* treeFindGENode(TREE **root,
692 TREE *nodeFind,
693 FNTREE_COMPARE_NODES *comp)
694{
695 TREE
696 *current = *root,
697 *found;
698
699 found = NULL;
700 while (current != TREE_NULL)
701 switch (comp(current, nodeFind))
702 {
703 case -1: current = current->right; break;
704 default: found = current;
705 current = current->left;
706 }
707
708 return found;
709}
710
711/*
712 *@@ treeFindLTNode:
713 * finds a node with Node less than provided.
714 * To find a tree node, your comparison function must
715 * compare the tree nodes.
716 */
717
718void* treeFindLTNode(TREE **root,
719 TREE *nodeFind,
720 FNTREE_COMPARE_NODES *comp)
721{
722 TREE
723 *current = *root,
724 *found;
725
726 found = NULL;
727 while (current != TREE_NULL)
728 switch (comp(current, nodeFind))
729 {
730 case -1: found = current;
731 current = current->right; break;
732 default: current = current->left;
733 }
734
735 return found;
736}
737
738/*
739 *@@ treeFindLENode:
740 * finds a node with Node less than or equal to provided.
741 * To find a tree node, your comparison function must
742 * compare the tree nodes.
743 */
744
745void* treeFindLENode(TREE **root,
746 TREE *nodeFind,
747 FNTREE_COMPARE_NODES *comp)
748{
749 TREE
750 *current = *root,
751 *found;
752
753 found = NULL;
754 while (current != TREE_NULL)
755 switch (comp(current, nodeFind))
756 {
757 case 1 : current = current->left; break;
758 default: found = current;
759 current = current->right;
760 }
761
762 return found;
763}
764
765/*
766 *@@ treeFindGTNode:
767 * finds a node with Node greater than provided.
768 * To find a tree node, your comparison function must
769 * compare the tree nodes.
770 */
771
772void* treeFindGTNode(TREE **root,
773 TREE *nodeFind,
774 FNTREE_COMPARE_NODES *comp)
775{
776 TREE
777 *current = *root,
778 *found;
779
780 found = NULL;
781 while (current != TREE_NULL)
782 switch (comp(current, nodeFind))
783 {
784 case 1 : found = current;
785 current = current->left; break;
786 default: current = current->right;
787 }
788
789 return found;
790}
791
792/*
793 *@@ treeFindEQID:
794 * finds a node with data exactly matching that provided.
795 * To find a tree node, your comparison function must
796 * compare a tree member with external data.
797 *
798 * This is useful for finding a tree item from a string ID.
799 *
800 * Make sure to use treeInsertNode and compare according
801 * to a string member, and then write a second compare
802 * function for this function which compares the string
803 * member to an external string.
804 */
805
806void* treeFindEQData(TREE **root,
807 void *pData,
808 FNTREE_COMPARE_DATA *comp)
809{
810 TREE *current = *root,
811 *found = NULL;
812
813 while (current != TREE_NULL)
814 switch (comp(current, pData))
815 {
816 case -1: current = current->right; break;
817 case 1: current = current->left; break;
818 default: found = current; // In case of duplicates,
819 current = current->left; // get the first one.
820 }
821
822 return found;
823}
824
825/*
826 *@@ treeTraverse:
827 * traverses the specified tree, calling a processing function
828 * for each tree node.
829 *
830 * The processing function ("process") must be declared as
831 * follows:
832 *
833 + void fnProcess(TREE *t, // current tree node
834 + void *pUser); // user data
835 *
836 * and will receive the "pUser" parameter, which you can use
837 * as a data pointer to some structure for whatever you like.
838 */
839
840void treeTraverse(TREE *tree,
841 TREE_PROCESS *process,
842 void *pUser,
843 int method)
844{
845 if ((!tree)
846 || (tree == TREE_NULL))
847 return;
848
849 if (method == 1)
850 {
851 process(tree, pUser);
852 treeTraverse (((TREE *) tree)->left, process, pUser, method);
853 treeTraverse (((TREE *) tree)->right, process, pUser, method);
854 }
855 else if (method == 2)
856 {
857 treeTraverse (((TREE *) tree)->left, process, pUser, method);
858 treeTraverse (((TREE *) tree)->right, process, pUser, method);
859 process(tree, pUser);
860 }
861 else
862 {
863 treeTraverse (((TREE *) tree)->left, process, pUser, method);
864 process(tree, pUser);
865 treeTraverse (((TREE *) tree)->right, process, pUser, method);
866 }
867}
868
869/*
870 *@@ treeFirst:
871 * finds and returns the first node in a (sub-)tree.
872 */
873
874void* treeFirst(TREE *tree)
875{
876 TREE
877 *current;
878
879 if ((!tree)
880 || (tree == TREE_NULL))
881 return NULL;
882
883 current = tree;
884 while (current->left != TREE_NULL)
885 current = current->left;
886
887 return current;
888}
889
890/*
891 *@@ treeLast:
892 * finds and returns the last node in a (sub-)tree.
893 */
894
895void* treeLast(TREE *tree)
896{
897 TREE
898 *current;
899
900 if ((!tree)
901 || (tree == TREE_NULL))
902 return NULL;
903
904 current = tree;
905 while (current->right != TREE_NULL)
906 current = current->right;
907
908 return current;
909}
910
911/*
912 *@@ treeNext:
913 * finds and returns the next node in a tree.
914 */
915
916void* treeNext(TREE *tree)
917{
918 TREE
919 *current,
920 *child;
921
922 if ((!tree)
923 || (tree == TREE_NULL))
924 return NULL;
925
926 current = tree;
927 if (current->right != TREE_NULL)
928 return treeFirst (current->right);
929 else
930 {
931 current = tree;
932 child = TREE_NULL;
933 while ((current->parent)
934 && (current->right == child))
935 {
936 child = current;
937 current = current->parent;
938 }
939 if (current->right != child)
940 return current;
941 else
942 return NULL;
943 }
944}
945
946/*
947 *@@ treePrev:
948 * finds and returns the previous node in a tree.
949 */
950
951void* treePrev(TREE *tree)
952{
953 TREE
954 *current,
955 *child;
956
957 if ((!tree)
958 || (tree == TREE_NULL))
959 return NULL;
960
961 current = tree;
962 if (current->left != TREE_NULL)
963 return treeLast (current->left);
964 else
965 {
966 current = tree;
967 child = TREE_NULL;
968 while ((current->parent)
969 && (current->left == child))
970 {
971 child = current;
972 current = current->parent;
973 }
974 if (current->left != child)
975 return current;
976 else
977 return NULL;
978 }
979}
980
981
Note: See TracBrowser for help on using the repository browser.