binary_t.c

来自「开放源码的编译器open watcom 1.6.0版的源代码」· C语言 代码 · 共 367 行 · 第 1/2 页

//
// Copyright (C) 1991 Texas Instruments Incorporated.
//
// Permission is granted to any individual or institution to use, copy, modify,
// and distribute this software, provided that this complete copyright and
// permission notice is maintained, intact, in all copies and supporting
// documentation.
//
// Texas Instruments Incorporated provides this software "as is" without
// express or implied warranty.
//


#include <cool/Binary_Tree.h>

// CoolBinary_Tree -- Simple constructor to initialize a CoolBinary_Tree object
// Input:         None
// Output:        None

template <class Type>
CoolBinary_Tree<Type>::CoolBinary_Tree() {
  this->compare = &default_node_compare; // Pointer to compare function
}



// CoolBinary_Tree -- constructor to initialize a CoolBinary_Tree object to have the
//                same size and values as some other CoolBinary_Tree object
// Input:         Reference to CoolBinary_Tree
// Output:        None

template <class Type>
CoolBinary_Tree<Type>::CoolBinary_Tree(const CoolBinary_Tree<Type>& b)
{
  this->compare = b.compare;                    // Pointer to compare function
  this->number_nodes = b.number_nodes;
  this->root = this->copy_nodes (b.get_root());
  this->current_position () = b.current_position ();
}



// ~CoolBinary_Tree -- Destructor for the CoolBinary_Tree class
// Input:          None
// Output:         None

template <class Type>
CoolBinary_Tree<Type>::~CoolBinary_Tree() {
  delete this->root;                            // Virtual destructor called recurs.
}                                               // on all nodes 

// value -- Return value of node at current position
// Input:   None
// Output:  Reference to value of node at current position

template <class Type>
Type& CoolBinary_Tree<Type>::value () {
#if ERROR_CHECKING
 if (this->state.stack.is_empty() )             // If invalid current position
   this->curpos_error (#Type, "value()");       // Raise exception
#endif
  Stack_Entry stack_entry = this->state.stack.top(); // get top stack
  return (((CoolBinary_Node<Type>*)stack_entry.get_first())->get()); // Return value
}


template <class Type>
Boolean CoolBinary_Tree<Type>::put_internal
                            (const Type& value, Boolean avl) {

  if (this->root == NULL) {                     // If this is the first node
    this->root = new CoolBinary_Node<Type> (value);     // Add new node and value
    this->number_nodes++;                       // Update node count
    return TRUE;                                // Indicate success
  }
  CoolBinary_Node<Type>* ptr = (CoolBinary_Node<Type>*)this->root; // Start at root
  BT_Stack stack;                               // Stack for AVL balancing
  while (TRUE) {                                // Until we find location
    int pos = (*this->compare)(ptr->get(),value); // Compare data values
    if (pos == 0)                               // If data value exists in tree
      return FALSE;                             //    indicate node not added
    else if (pos > 0) {                         // Data down left subtree?
      if (avl)
        stack.push (Stack_Entry (/*(CoolBinary_Node*)##*/ptr,LEFT)); // Push parent
      if (ptr->get_ltree() == NULL) {           // If at leaf node
        ptr->set_ltree ((new CoolBinary_Node<Type> (value))); // Add node to ltree
        this->number_nodes++;                   // Update node count
        break;                                  // Break out of loop and exit
      }
      else {
        ptr = ptr->get_ltree();                 // Else point to left subtree
        continue;                               // And continue search
      }
    }
    else {                                      // Else down right subtree
      if (avl)
        stack.push (Stack_Entry (/*(CoolBinary_Node*)##*/ptr,RIGHT)); // Push on stack
      if (ptr->get_rtree() == NULL) {           // If at leaf node
        ptr->set_rtree ((new CoolBinary_Node<Type> (value))); // Add node to rtree
        this->number_nodes++;                   // Update node count
        break;                                  // Break out of loop and exit
      }
      else {
        ptr = ptr->get_rtree();                 // Grab right subtree dir
        continue;                               // And continue to search;
      }
    }
  }
  if (avl)                                      // Balance it if an AVL tree
    CoolBase_Binary_Tree::avl_put_balance (stack);

  this->reset();                                // Invalidate current position
  return TRUE;                                  // Return success
}


// remove_internal -- does the actual work of removing a value from bin tree
//                    for avl trees, will make call to check avl balance
// Input:          -- value to remove + optional Boolean for AVL trees
// output          -- TRUE if item sucessfully removed. FALSE otherwise.
template <class Type>
Boolean CoolBinary_Tree<Type>::remove_internal
                           (const Type& value, Boolean avl) {
  if (this->root == NULL)                       // If there are no nodes
    return FALSE;                               // indicate failure
  BT_Stack stack1;                              // Allocate traversal stack
  Left_Right route = NONE;                      // Last subtree taken
  CoolBinary_Node<Type> *ptr = (CoolBinary_Node<Type>*)this->root; // Start at root
  CoolBinary_Node<Type> *parent_ptr = NULL;             // Save pointer to parent
  CoolBinary_Node<Type> *ptr1, *ptr2;           // temp ptrs to nodes
  while (TRUE) {                                // Until we find location
    int pos = (*this->compare)(ptr->get(),value); // Compare data values
    if (pos == 0) {                             // If node to delete is found
      if (ptr->get_rtree() == NULL) {           // If no right subtree
        if (route == LEFT)                      // If child of parent's ltree
          parent_ptr->set_ltree(ptr->get_ltree()); // Set to left subtree
        else if (route == RIGHT)
          parent_ptr->set_rtree(ptr->get_ltree()); // Set to right subtree
        else this->root = ptr->get_ltree();     // Make ltree the new root
      }
      else if (ptr->get_ltree() == NULL) {      // Else if no left subtree
        if (route == LEFT)                      // If child of parent ltree
          parent_ptr->set_ltree(ptr->get_rtree()); // Set to left subtree
        else if (route == RIGHT)
          parent_ptr->set_rtree(ptr->get_rtree()); // Set to right subtree
        else this->root = ptr->get_rtree();        //    rtree is the new root.
      }
  
      // Node(a) with value to be deleted has both a left and right subtree.
      // We need to look for the node(b) with the next smallest value and
      // copy it's value into node(a). Then adjust the parent of node(b) 
      // to point at node(b)'s left subtree (right subtree will always be 
      // NULL).  ptr is left pointing at node(b) so it is the
      // one which is eventually deleted.
      else {
        if (avl)                                // for avl trees
          stack1.push (Stack_Entry(/*(CoolBinary_Node*)##*/ptr,LEFT)); // push on stack
        ptr1 = ptr;                             // Save node with matched data
        ptr2 = ptr1;                            // last parent initially ptr
        ptr = ptr->get_ltree();                 // Start with node's ltree
        while (ptr->get_rtree() != NULL) {      // Follow rtree til null rtree
          if (avl)                              // for avl trees
            stack1.push (Stack_Entry(/*(CoolBinary_Node*)##*/ptr,RIGHT)); // push on stack
          ptr2 = ptr;                           // save last parent
          ptr = ptr->get_rtree();               // get right subtree
        }
        ptr1->set (ptr->get());                 // Move next smallest value up
        if (ptr1 == ptr2)                       // ltree had no rtrees
          ptr2->set_ltree (ptr->get_ltree());   // Del node is parents ltree
        else 
          ptr2->set_rtree (ptr->get_ltree());   // Del node is parents rtree
      }

      // DELETE the node ptr points at
      this->number_nodes--;                     // Decrement node count
      if (this->number_nodes == 0)              // If no more nodes in tree
        this->root = NULL;                      // Nullify root pointer
      ptr->set_ltree (NULL);                    // Nullify left subtree pointer
      ptr->set_rtree (NULL);                    // Nullify right subtree pointer
      delete ptr;                               // Deallocate memory
      this->reset();                            // Invalidate current position<
      break;                                    // exit loop
    }
    else if (pos > 0) {                         // Data down left subtree?