---

bitree.cpp

Go to the documentation of this file.

#include <stdio.h>
#include "ianstd.h"
#include "bitree.h"

      



binary_tree::bi_tree_ptr binary_tree::bi_tree_init(unsigned int key,
                                                   unsigned int val)
{
  bi_tree_ptr tmp = (bi_tree_ptr)get_tree_mem();

  tmp->key = key;
  tmp->val = val;
  tmp->leftptr = NULL;
  tmp->rightptr = NULL;
  return tmp;
}


void binary_tree::bi_tree_insert(bi_tree_ptr &root, 
                                 unsigned int key,
                                 unsigned int val )
{
  if (root == NULL) { // the tree is empty
    root = bi_tree_init(key, val);
  }
  else {
    if (root->key > key)
      bi_tree_insert(root->leftptr, key, val);     // search down left branch
    else
      if (root->key < key)
        bi_tree_insert(root->rightptr, key, val);  // search down right branch
      else { // key == root->key
        printf("binary_tree::bi_tree_insert: key %d already found in tree\n",
               key );
      }
  }
} // bi_tree_insert




binary_tree::bi_tree_ptr binary_tree::unlink(bi_tree_ptr &root)
{
  bi_tree_ptr node;

  node = root;
  if (root != NULL) {
    if (root->leftptr != NULL) {
      node = unlink(root->leftptr);
    }
    else {
      if (root->rightptr != NULL) {  // if there is a right branch child
        root = root->rightptr;       // replace the node at the end of
      }                              // the left branch with this child.
      else
        root = NULL;  // no children
    }
  }
  return node;
}


unsigned int binary_tree::bi_tree_delete(bi_tree_ptr &root, 
                                         unsigned int key )
{
  unsigned int retval = 0;

  if (root != NULL) {
    if (root->key > key)
      retval = bi_tree_delete(root->leftptr, key);
    else
      if (root->key < key)
        retval = bi_tree_delete(root->rightptr, key);
      else { // the keys are equal
        bi_tree_ptr node = NULL;
        bi_tree_ptr new_child = NULL;
        int num_children = 0;
          
        node = root;
        retval = root->val;

        // Count the children of the node
        if (root->leftptr != NULL) {
          num_children++;
          new_child = root->leftptr;
        }
        if (root->rightptr != NULL) {
          num_children++;
          new_child = root->rightptr;
        }

        switch (num_children) {
        case 0: root = NULL;
          break;
        case 1: root = new_child;  // Replace the node with its child
          break;
        case 2: {
          bi_tree_ptr tmp1, tmp2;
            
          // find the next greater node in the tree and unlink it
          tmp1 = root->rightptr;
          tmp2 = unlink(tmp1);
          // Connect the new node to any children, but make sure that 
          // we don't point a node at itself.
          if (root->leftptr != tmp2)
            tmp2->leftptr = root->leftptr;
          if (root->rightptr != tmp2)
            tmp2->rightptr = root->rightptr;
          root = tmp2;
        }
          break;
        } // switch
        free_tree_mem( node );
      } // keys are equal
  }  // root != NULL
  return retval;
} // bi_tree_delete


/* ------------------- Class functions for debugging --------------- */


void binary_tree::print_spaces(unsigned int indent)
{
  const int BufSize = 80;
  char buf[BufSize+1];
  int i;
  
  if (indent > BufSize)
    indent = BufSize;
  for (i = 0; i < (int)indent; i++) {
    buf[i] = ' ';
  }
  buf[indent] = '\0';
  printf("%s", buf);
}


void binary_tree::bi_tree_print(bi_tree_ptr root, unsigned int indent)
{

  if (root != NULL) {
    print_spaces(indent);
    printf("%d\n", root->key );
    if (root->leftptr != NULL)
      bi_tree_print(root->leftptr, indent+4);
    else {
      print_spaces(indent+4);
      printf("null\n");
    }
    if (root->rightptr != NULL)
      bi_tree_print(root->rightptr, indent+4);
    else {
      print_spaces(indent+4);
      printf("null\n");
    }
  }
}


void binary_tree::bi_tree_print_sorted(bi_tree_ptr root)
{
  if (root != NULL) {
    bi_tree_print_sorted(root->leftptr);
    printf("%d ", root->key );
    bi_tree_print_sorted(root->rightptr);
  }
}



unsigned int binary_tree::bi_tree_max_branch(bi_tree_ptr root )
{
  unsigned int depth = 0;

  if (root != NULL) {
    unsigned int depth_left = 0;
    unsigned int depth_right = 0;

    if (root->leftptr != NULL)
      depth_left = bi_tree_max_branch(root->leftptr);
    if (root->rightptr != NULL)
      depth_right = bi_tree_max_branch(root->rightptr);

    // depth = max(depth_left, depth_right)
    if (depth_left > depth_right)
      depth = depth_left;
    else
      depth = depth_right;

    depth++;  // Add one for the current node
  }

  return depth;
} // binary_tree::bi_tree_max_branch


unsigned int binary_tree::bi_tree_cnt(bi_tree_ptr root)
{
  unsigned int cnt = 0;

  if (root != NULL) {
    cnt = bi_tree_cnt(root->leftptr) + bi_tree_cnt(root->rightptr) + 1;
  }

  return cnt;
} // binary_tree::bi_tree_cnt



/* ------------------- Defaults for virtual functions --------------- */

binary_tree::bi_tree_ptr binary_tree::get_tree_mem(void)
{
  printf("binary_tree::get_tree_mem: no memory alloc provided for class\n");
  return (bi_tree_ptr)NULL;
}

void binary_tree::free_tree_mem( bi_tree_ptr addr )
{
  printf("binary_tree::free_tree_mem: no memory dealloc provided for class\n");
}

---