4.3BSD - /usr/src/new/spms/src/lib/libtree/src/treerm.c

   1: /* $Header$ */
   2: 
   3: /*
   4:  * Author: Peter J. Nicklin
   5:  */
   6: 
   7: /*
   8:  * treerm() removes a node from a binary tree. If key is null, the entire
   9:  * tree is removed.
  10:  */
  11: #include "tree.h"
  12: #include "null.h"
  13: 
  14: static TREE *q;             /* node to be deleted */
  15: 
  16: TREE *
  17: treerm(p, key)
  18:     TREE *p;            /* current node pointer */
  19:     char *key;          /* pointer to key */
  20: {
  21:     int comp;           /* compare key values */
  22:     int strcmp();           /* string comparison */
  23:     TREE *rmtl();           /* delete left subtree rightmost node */
  24: 
  25:     if (p != NULL)
  26:         if (key == NULL)
  27:             {
  28:             /* remove entire tree */
  29:             p->left = treerm(p->left, key);
  30:             p->right = treerm(p->right, key);
  31:             free(p->key);
  32:             free((char *) p);
  33:             p = NULL;
  34:             }
  35:         else if ((comp = strcmp(key, p->key)) < 0)
  36:             {
  37:             if (p->left != NULL)
  38:                 p->left = treerm(p->left, key);
  39:             }
  40:         else if (comp > 0)
  41:             {
  42:             if (p->right != NULL)
  43:                 p->right = treerm(p->right, key);
  44:             }
  45:         else    {
  46:             q = p;
  47:             if (q->right == NULL)
  48:                 p = q->left;
  49:             else if (q->left == NULL)
  50:                 p = q->right;
  51:             else
  52:                 p->left = rmtl(q->left);
  53:             free(q->key);
  54:             free((char *) q);
  55:             }
  56:     return(p);
  57: }
  58: 
  59: 
  60: 
  61: /*
  62:  * rmtl() descends along the rightmost branch of the left subtree of the
  63:  * element q to be deleted, and then it replaces the relevant information
  64:  * (key and count) in q by the corresponding values of the rightmost
  65:  * component r of that left subtree, after which r may be removed.
  66:  */
  67: TREE *
  68: rmtl(r)
  69:     TREE *r;            /* leaf to be removed */
  70: {
  71:     if (r->right != NULL)
  72:         {
  73:         r->right = rmtl(r->right);
  74:         }
  75:     else    {
  76:         q->key = r->key;
  77:         q->count = r->count;
  78:         q = r;
  79:         r = r->left;
  80:         }
  81:     return(r);
  82: }

Defined functions