base_bnt.c

来自「开放源码的编译器open watcom 1.6.0版的源代码」· C语言 代码 · 共 482 行 · 第 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.
//
// Created: MBN 07/19/89 -- Initial design and implementation
// Updated: MBN 09/19/89 -- Added conditional exception handling
// Updated: MJF 03/12/90 -- Added group names to RAISE
// Updated: VDN 02/21/92 -- New lite version
//
// The Binary_Tree class implements the type-generic  structural methods of the
// parameterized Binary_Tree<Type>  class  and is  a friend of  the Binary Node
// class.  The  Binary_Tree   class  is  intended for  the    sole  use  of the
// parameterized  Binary_Tree<Type>    class.    The    Binary_Tree<Type> class
// implements simple,  dynamic,   sorted  sequences.  Users who  require a data
// structure  for unsorted  sequences  whose structure and organization is more
// under the control of the programmer are refered to the N_Tree class.
//

#include <cool/Base_Binary_Tree.h>

#include <cool/Pair.C>
#include <cool/Stack.C>

#define IGNORE(arg) (void) arg

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

CoolBase_Binary_Tree::CoolBase_Binary_Tree () {
  this->root = NULL;                            // Initialize root pointer
  this->number_nodes = 0;                       // Initialize node count
  this->state.forward = TRUE;                   // Assume Forward direction;
}


// ~CoolBase_Binary_Tree -- destructor must be virtual to delete both state and data.
// Input:              None
// Output:             None

CoolBase_Binary_Tree::~CoolBase_Binary_Tree () {}               // state is deleted automatically


// clear -- removes root and all subtrees
// input -- none
// output -- none

void CoolBase_Binary_Tree::clear () {
  delete root;                                  // virtually delete all nodes
  this->root = NULL;
  this->number_nodes = 0;
  this->reset();                                // reset state of iterator
}

  

// calc_depth (recurse thru the Tree and return zero-based depth)
//   if update_bal is not NULL, then the avl balance for this node is
//   updated.  This avl update should be called after balancing the tree
//   as an AVL tree cannot have it's balance othere than -1, 0 1.

long CoolBase_Binary_Tree::calc_depth
                (CoolBase_Binary_Node* node, long depth, Boolean update_bal) {
  if (node == NULL) {                           // Null nodes don't count
    if (depth > 0)                              // If not the root
      --depth;                                  //   depth bumped 1 too many
    return depth;
  }
  depth++;                                      // Do left and right subtrees
  long ldepth = this->calc_depth (node->ltree, depth, update_bal);
  long rdepth = this->calc_depth (node->rtree, depth, update_bal);

  // It is an error if rdepth - ldepth is other than -1 0 or 1.
  if (update_bal)                               // If we need to update balance
    node->avl_balance =(int)(rdepth - ldepth);  // it's right tree depth - left

  if (ldepth > rdepth)                          // Return count of deepest tree
    return ldepth;
  else
    return rdepth;
}

// current-node -- Returns node at the current position

CoolBase_Binary_Node* CoolBase_Binary_Tree::node () {
  if (this->state.stack.is_empty())
    return NULL;
  else {
    Stack_Entry se = this->state.stack.top();
    return se.get_first();
  }
}

// Get the next node in the tree based on the Traversal Type.  This
// maintains a stack of parents in the tree for current position and
// knows how to move forward and backward for preorder, inorder, or
// postorder traversals.  Binary trees only use inorder and inorder_reverse
// so the code for dealing with the other traversal types is commented out
// (almost identical copy of this is in N_Tree)

Boolean CoolBase_Binary_Tree::next_internal (Traversal_Type ttype) {
  CoolBase_Binary_Node *node, *ptr1;
  CoolBase_Binary_Node *last_node = NULL;
  Stack_Entry stack_entry;
  int index;
  Boolean forward = TRUE;

  switch (ttype) {
  case INORDER_REVERSE:
//case PREORDER_REVERSE:                        // Are we going backward?
//case POSTORDER_REVERSE:
    forward = FALSE;
    break;
  }
    
  if (state.stack.is_empty()) {         // If stack is empty
    node = this->root;                          //  start with the root
    if (forward)                                //  init starting subtree
      index = -1;                               //    start at first subtree
    else                                        //    or
      index = node->num_subtrees();             //    start at last subtree
    state.stack.push (Stack_Entry (node,index));
    state.forward = forward;
    
  }
  else {                                        // Stack has some entries, so
    stack_entry = state.stack.top();            //  get top entry from stack
    node = stack_entry.get_first();             //  load up node
    index = (int)stack_entry.get_second();      //  and subtree index
    last_node = node;                           //  remember current position

    if (state.forward != forward) {             // Need to modify index
      if (forward)                              //  if we've changed direction.
        index--;
      else
        index++;
    }
    state.forward = forward;                    // Update direction.
  }

  if (forward) {                                // Going left to right
    while (TRUE) {                              // loop until next node found
      if (++index < node->num_subtrees()) {     // incremented index in range?
        if (node != last_node &&                // If we moved to new node &&
            ((ttype == INORDER  && index == 1)  // Inorder after ltree or
//           ||(ttype == PREORDER && index == 0)// Preorder before ltree
             ))
          return TRUE;                          // then this is next node

        state.stack.top().set_second(index);    // update stack with new index
        ptr1 = node->subtree(index);            // get node's next subtree
        if (ptr1) {                             // When subtree exists
          node = ptr1;                          //   point node at subtree
          index = -1;                           //   init index for new node
          state.stack.push (Stack_Entry (node, index)); 
        }
      }
      else {                                    // No more subtrees for node
//      if (node != last_node &&                // If a new node
//          ttype == POSTORDER) {               //   and Postorder mode, 
//        return TRUE;                          //   then this is next node
//      }
        state.stack.pop();// pop this node from stack
        if (state.stack.is_empty())            // Stack empty?
          return FALSE;                         //   indicate we're at the end
        else {                                  // Stack not empty, so
          stack_entry = state.stack.top();      //  update stack_entry object
          node = stack_entry.get_first(); //  load up node
          index = stack_entry.get_second();     //  and subtree index
        }
      }
    }
  }

// This is essesentially the same code as above, but going right to
// left, giving reverse order capability
  else {                                        // Going right to left
    while (TRUE) {                              // loop until next node found
      if (--index > -1) {                       // decremented index in range?
        if (node != last_node &&                // If we moved to new node &&
            ((ttype == INORDER_REVERSE &&       //  or Inorder_reverse node
              index == 0)                       //  is ready to do left subtree
//           || (ttype == POSTORDER_REVERSE &&  //  or Postorder_reverse is
//            index == (node->num_subtrees()-1))  // starting it's subtrees
             ))
          return TRUE;                          // then this is next node
        state.stack.top().set_second(index);    // update stack with new index
        ptr1 = node->subtree(index);            // get node's next subtree
        if (ptr1) {                             // When subtree exists
          node = ptr1;                          //   point node at subtree
          index = node->num_subtrees();         //   init index for new node
          state.stack.push (Stack_Entry (node, index)); 
        }
      }
      else {                                    // No more subtrees for node
//      if (node != last_node &&                // If a new node
//        ttype == PREORDER_REVERSE)            //   and Preorder_reverse
//        return TRUE;                          //   this is next node

        state.stack.pop();                      // pop this node from stack
        if (state.stack.is_empty())             // Stack empty?
          return FALSE;                         //   indicate we're at the end
        else {                                  // Stack not empty, so
          stack_entry = state.stack.top();      //  update stack_entry object
          node = stack_entry.get_first();       //  load up node
          index = (int)stack_entry.get_second();        //  and subtree index
        }
      }
    }
  }
}




  // maintain the balance of an AVL tree after a put.  The balance of
  // depths between the right subtree and left subtree are maintained
  // for each node. When this balance differs by more than 1, a single
  // or double rotation is done depending on the constellation to put
  // the balance of that node back to zero.  A single or double
  // rotation on the parent of the inserted node does the job.  Nodes
  // above the parent are not affected.

void CoolBase_Binary_Tree::avl_put_balance (BT_Stack &stack) {
  CoolBase_Binary_Node *p1, *p2, *raised_node=NULL;     // alloc tmp ptrs to Node
  CoolBase_Binary_Node *ptr;
  Left_Right route=NONE;
  Boolean more_todo = TRUE;
  while (stack.length() > 0) {                  // Loop thru nodes on stack
    Stack_Entry stack_entry = stack.pop();      // Pop next stack_entry
    ptr = stack_entry.get_first();              // Get Node 
    route = (Left_Right)stack_entry.get_second();// Get the subtree
    if (raised_node != NULL) {                  // A node was rotated up
      if (route == LEFT)                        // For a left route