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

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

Updates for new xwphelpers plus others.
  • 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 {
476 if (descendent == descendent->parent->left)
477 descendent->parent->left = youngest;
478 else
479 descendent->parent->right = youngest;
480 }
481 else
482 *root = youngest;
483
484 colour = descendent->colour;
485
486 if (descendent != (TREE *) tree)
487 {
488 // Conceptually what we are doing here is moving the data from
489 // descendent to tree. In fact we do this by linking descendent
490 // into the structure in the place of tree.
491 descendent->left = ((TREE *) tree)->left;
492 descendent->right = ((TREE *) tree)->right;
493 descendent->parent = ((TREE *) tree)->parent;
494 descendent->colour = ((TREE *) tree)->colour;
495
496 if (descendent->parent)
497 {
498 if (tree == descendent->parent->left)
499 descendent->parent->left = descendent;
500 else
501 descendent->parent->right = descendent;
502 }
503 else
504 *root = descendent;
505
506 if (descendent->left != TREE_NULL)
507 descendent->left->parent = descendent;
508
509 if (descendent->right != TREE_NULL)
510 descendent->right->parent = descendent;
511 }
512
513 if ( (youngest != TREE_NULL)
514 && (colour == BLACK))
515 delete_fixup (root, youngest);
516
517 return (irc);
518}
519
520/*
521 *@@ delete_fixup:
522 * maintains Red-Black tree balance after deleting a node.
523 *
524 * Private function.
525 */
526
527static void delete_fixup(TREE **root,
528 TREE *tree)
529{
530 TREE
531 *sibling;
532
533 while (tree != *root && tree->colour == BLACK)
534 {
535 if (tree == tree->parent->left)
536 {
537 sibling = tree->parent->right;
538 if (sibling->colour == RED)
539 {
540 sibling->colour = BLACK;
541 tree->parent->colour = RED;
542 rotate_left (root, tree->parent);
543 sibling = tree->parent->right;
544 }
545 if ((sibling->left->colour == BLACK)
546 && (sibling->right->colour == BLACK))
547 {
548 sibling->colour = RED;
549 tree = tree->parent;
550 }
551 else
552 {
553 if (sibling->right->colour == BLACK)
554 {
555 sibling->left->colour = BLACK;
556 sibling->colour = RED;
557 rotate_right (root, sibling);
558 sibling = tree->parent->right;
559 }
560 sibling->colour = tree->parent->colour;
561 tree->parent->colour = BLACK;
562 sibling->right->colour = BLACK;
563 rotate_left (root, tree->parent);
564 tree = *root;
565 }
566 }
567 else
568 {
569 sibling = tree->parent->left;
570 if (sibling->colour == RED)
571 {
572 sibling->colour = BLACK;
573 tree->parent->colour = RED;
574 rotate_right (root, tree->parent);
575 sibling = tree->parent->left;
576 }
577 if ((sibling->right->colour == BLACK)
578 && (sibling->left->colour == BLACK))
579 {
580 sibling->colour = RED;
581 tree = tree->parent;
582 }
583 else
584 {
585 if (sibling->left->colour == BLACK)
586 {
587 sibling->right->colour = BLACK;
588 sibling->colour = RED;
589 rotate_left (root, sibling);
590 sibling = tree->parent->left;
591 }
592 sibling->colour = tree->parent->colour;
593 tree->parent->colour = BLACK;
594 sibling->left->colour = BLACK;
595 rotate_right (root, tree->parent);
596 tree = *root;
597 }
598 }
599 }
600 tree->colour = BLACK;
601}
602
603/*
604 *@@ treeFindEQID:
605 * finds a node with ID exactly matching that provided.
606 * To find a tree node, your comparison function must
607 * compare the tree node IDs.
608 */
609
610void* treeFindEQID(TREE **root,
611 unsigned long id,
612 FNTREE_COMPARE_IDS *comp)
613{
614 TREE
615 *current = *root,
616 *found;
617
618 found = NULL;
619 while (current != TREE_NULL)
620 switch (comp(current->id, id))
621 {
622 case -1: current = current->right; break;
623 case 1: current = current->left; break;
624 default: found = current; // In case of duplicates,
625 current = current->left; // get the first one.
626 }
627
628 return found;
629}
630
631/*
632 *@@ treeFindGEID:
633 * finds a node with ID greater than or equal to provided.
634 * To find a tree node, your comparison function must
635 * compare the tree node IDs.
636 */
637
638void* treeFindGEID(TREE **root,
639 unsigned long idFind,
640 FNTREE_COMPARE_IDS *comp)
641{
642 TREE
643 *current = *root,
644 *found;
645
646 found = NULL;
647 while (current != TREE_NULL)
648 switch (comp(current->id, idFind))
649 {
650 case -1: current = current->right; break;
651 default: found = current;
652 current = current->left;
653 }
654
655 return found;
656}
657
658/*
659 *@@ treeFindEQNode:
660 * finds a node with ID exactly matching that provided.
661 * To find a tree node, your comparison function must
662 * compare the tree nodes.
663 */
664
665void* treeFindEQNode(TREE **root,
666 TREE *nodeFind,
667 FNTREE_COMPARE_NODES *comp)
668{
669 TREE
670 *current = *root,
671 *found;
672
673 found = NULL;
674 while (current != TREE_NULL)
675 switch (comp(current, nodeFind))
676 {
677 case -1: current = current->right; break;
678 case 1: current = current->left; break;
679 default: found = current; // In case of duplicates,
680 current = current->left; // get the first one.
681 }
682
683 return found;
684}
685
686/*
687 *@@ treeFindGENode:
688 * finds a node with ID greater than or equal to provided.
689 * To find a tree node, your comparison function must
690 * compare the tree nodes.
691 */
692
693void* treeFindGENode(TREE **root,
694 TREE *nodeFind,
695 FNTREE_COMPARE_NODES *comp)
696{
697 TREE
698 *current = *root,
699 *found;
700
701 found = NULL;
702 while (current != TREE_NULL)
703 switch (comp(current, nodeFind))
704 {
705 case -1: current = current->right; break;
706 default: found = current;
707 current = current->left;
708 }
709
710 return found;
711}
712
713/*
714 *@@ treeFindLTNode:
715 * finds a node with Node less than provided.
716 * To find a tree node, your comparison function must
717 * compare the tree nodes.
718 */
719
720void* treeFindLTNode(TREE **root,
721 TREE *nodeFind,
722 FNTREE_COMPARE_NODES *comp)
723{
724 TREE
725 *current = *root,
726 *found;
727
728 found = NULL;
729 while (current != TREE_NULL)
730 switch (comp(current, nodeFind))
731 {
732 case -1: found = current;
733 current = current->right; break;
734 default: current = current->left;
735 }
736
737 return found;
738}
739
740/*
741 *@@ treeFindLENode:
742 * finds a node with Node less than or equal to provided.
743 * To find a tree node, your comparison function must
744 * compare the tree nodes.
745 */
746
747void* treeFindLENode(TREE **root,
748 TREE *nodeFind,
749 FNTREE_COMPARE_NODES *comp)
750{
751 TREE
752 *current = *root,
753 *found;
754
755 found = NULL;
756 while (current != TREE_NULL)
757 switch (comp(current, nodeFind))
758 {
759 case 1 : current = current->left; break;
760 default: found = current;
761 current = current->right;
762 }
763
764 return found;
765}
766
767/*
768 *@@ treeFindGTNode:
769 * finds a node with Node greater than provided.
770 * To find a tree node, your comparison function must
771 * compare the tree nodes.
772 */
773
774void* treeFindGTNode(TREE **root,
775 TREE *nodeFind,
776 FNTREE_COMPARE_NODES *comp)
777{
778 TREE
779 *current = *root,
780 *found;
781
782 found = NULL;
783 while (current != TREE_NULL)
784 switch (comp(current, nodeFind))
785 {
786 case 1 : found = current;
787 current = current->left; break;
788 default: current = current->right;
789 }
790
791 return found;
792}
793
794/*
795 *@@ treeFindEQID:
796 * finds a node with data exactly matching that provided.
797 * To find a tree node, your comparison function must
798 * compare a tree member with external data.
799 *
800 * This is useful for finding a tree item from a string ID.
801 *
802 * Make sure to use treeInsertNode and compare according
803 * to a string member, and then write a second compare
804 * function for this function which compares the string
805 * member to an external string.
806 */
807
808void* treeFindEQData(TREE **root,
809 void *pData,
810 FNTREE_COMPARE_DATA *comp)
811{
812 TREE *current = *root,
813 *found = NULL;
814
815 while (current != TREE_NULL)
816 switch (comp(current, pData))
817 {
818 case -1: current = current->right; break;
819 case 1: current = current->left; break;
820 default: found = current; // In case of duplicates,
821 current = current->left; // get the first one.
822 }
823
824 return found;
825}
826
827/*
828 *@@ treeTraverse:
829 * traverses the specified tree, calling a processing function
830 * for each tree node.
831 *
832 * The processing function ("process") must be declared as
833 * follows:
834 *
835 + void fnProcess(TREE *t, // current tree node
836 + void *pUser); // user data
837 *
838 * and will receive the "pUser" parameter, which you can use
839 * as a data pointer to some structure for whatever you like.
840 */
841
842void treeTraverse(TREE *tree,
843 TREE_PROCESS *process,
844 void *pUser,
845 int method)
846{
847 if ((!tree)
848 || (tree == TREE_NULL))
849 return;
850
851 if (method == 1)
852 {
853 process(tree, pUser);
854 treeTraverse (((TREE *) tree)->left, process, pUser, method);
855 treeTraverse (((TREE *) tree)->right, process, pUser, method);
856 }
857 else if (method == 2)
858 {
859 treeTraverse (((TREE *) tree)->left, process, pUser, method);
860 treeTraverse (((TREE *) tree)->right, process, pUser, method);
861 process(tree, pUser);
862 }
863 else
864 {
865 treeTraverse (((TREE *) tree)->left, process, pUser, method);
866 process(tree, pUser);
867 treeTraverse (((TREE *) tree)->right, process, pUser, method);
868 }
869}
870
871/*
872 *@@ treeFirst:
873 * finds and returns the first node in a (sub-)tree.
874 */
875
876void* treeFirst(TREE *tree)
877{
878 TREE
879 *current;
880
881 if ((!tree)
882 || (tree == TREE_NULL))
883 return NULL;
884
885 current = tree;
886 while (current->left != TREE_NULL)
887 current = current->left;
888
889 return current;
890}
891
892/*
893 *@@ treeLast:
894 * finds and returns the last node in a (sub-)tree.
895 */
896
897void* treeLast(TREE *tree)
898{
899 TREE
900 *current;
901
902 if ((!tree)
903 || (tree == TREE_NULL))
904 return NULL;
905
906 current = tree;
907 while (current->right != TREE_NULL)
908 current = current->right;
909
910 return current;
911}
912
913/*
914 *@@ treeNext:
915 * finds and returns the next node in a tree.
916 */
917
918void* treeNext(TREE *tree)
919{
920 TREE
921 *current,
922 *child;
923
924 if ((!tree)
925 || (tree == TREE_NULL))
926 return NULL;
927
928 current = tree;
929 if (current->right != TREE_NULL)
930 return treeFirst (current->right);
931 else
932 {
933 current = tree;
934 child = TREE_NULL;
935 while ((current->parent)
936 && (current->right == child))
937 {
938 child = current;
939 current = current->parent;
940 }
941 if (current->right != child)
942 return current;
943 else
944 return NULL;
945 }
946}
947
948/*
949 *@@ treePrev:
950 * finds and returns the previous node in a tree.
951 */
952
953void* treePrev(TREE *tree)
954{
955 TREE
956 *current,
957 *child;
958
959 if ((!tree)
960 || (tree == TREE_NULL))
961 return NULL;
962
963 current = tree;
964 if (current->left != TREE_NULL)
965 return treeLast (current->left);
966 else
967 {
968 current = tree;
969 child = TREE_NULL;
970 while ((current->parent)
971 && (current->left == child))
972 {
973 child = current;
974 current = current->parent;
975 }
976 if (current->left != child)
977 return current;
978 else
979 return NULL;
980 }
981}
982
983
Note: See TracBrowser for help on using the repository browser.