Visual Basic Source Code/Visual Basic Source Code.iso/vbsource/vbdatabs/bstreeb.cpp

C/C++ Source or Header | 1999-03-14 | 6.0 KB | 182 lines

// ------------------------------- //
// -------- Start of File -------- //
// ------------------------------- //
// ----------------------------------------------------------- //
// C++ Source Code File Name: bstreeb.cpp
// Compiler Used: MSVC40, DJGPP 2.7.2.1, GCC 2.7.2.1, HP CPP 10.24
// Produced By: Doug Gaer
// File Creation Date: 01/23/1997
// Date Last Modified: 03/15/1999
// Copyright (c) 1997 Douglas M. Gaer
// ----------------------------------------------------------- //
// ------------- Program Description and Details ------------- //
// ----------------------------------------------------------- //
/*
The VBD C++ classes are copyright (c) 1997, by Douglas M. Gaer.
All those who put this code or its derivatives in a commercial
product MUST mention this copyright in their documentation for
users of the products in which this code or its derivative
classes are used. Otherwise, you have the freedom to redistribute
verbatim copies of this source code, adapt it to your specific
needs, or improve the code and release your improvements to the
public provided that the modified files carry prominent notices
stating that you changed the files and the date of any change.


THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND.
THE ENTIRE RISK OF THE QUALITY AND PERFORMANCE OF THIS SOFTWARE
IS WITH YOU. SHOULD ANY ELEMENT OF THIS SOFTWARE PROVE DEFECTIVE,
YOU WILL ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR, OR
CORRECTION.

Abstract binary search tree node functions. These functions
assume the nodes are part of binary search trees, but do not
depend on the data stored in the nodes.
*/
// ----------------------------------------------------------- //

#include "bstreeb.h"

BNodeBase *Minimum(BNodeBase *Tree)
// Assuming that Tree is a binary search tree, this function
// returns the minimum node in the tree, which can be
// found by going as far left as possible. If Tree is null,
// a null is returned, else a pointer to the minimun
// node is returned.
{
  if (Tree) {
    while(Tree->Left) Tree = Tree->Left;
  }
  return Tree;
}

BNodeBase *Maximum(BNodeBase *Tree)
// Assuming that Tree is a binary search tree, this function
// returns the maximum node in the tree, which can be
// found by going as far right as possible. If Tree is null,
// a null is returned, else a pointer to the minimun
// node is returned.
{
  if (Tree) {
    while(Tree->Right) Tree = Tree->Right;
  }
  return Tree;
}

BNodeBase *ParentOfMinimum(BNodeBase *Tree)
// Assuming that Tree is a binary search tree, this function
// returns a pointer to the parent of the minimum node
// in the tree, which can be found by going as far left
// as possible. If Tree is null, or is itself the minimum,
// a null is returned.
{
  BNodeBase *ptr = 0;
  if (Tree) {
    while(Tree->Left) {
       ptr = Tree;
       Tree = Tree->Left;
    }
  }
  return ptr;
}

BNodeBase *ParentOfMaximum(BNodeBase *Tree)
// Assuming that Tree is a binary search tree, this function
// returns a pointer to the parent of the maximum node
// in the tree, which can be found by going as far right
// as possible. If Tree is null, or is itself the maximum,
// a null is returned.
{
  BNodeBase *ptr = 0;
  if (Tree) {
    while(Tree->Right) {
       ptr = Tree;
       Tree = Tree->Right;
    }
  }
  return ptr;
}

BNodeBase *ParentOfPredecessor(BNodeBase *Tree)
// Returns parent of predecessor of Tree, assumed to be
// a binary search tree. Predecessor is the right child
// of node returned, unless Tree itself is the parent. Then
// the left child is the predecessor. If Tree is a leaf, a
// 0 is returned. Assumes Tree is not Tree null.
{
  BNodeBase *ptr = 0;
  // Go left, then all the way right
  BNodeBase *q = Tree->Left;
  if (q) {
     ptr = Tree;
     while(q->Right) {
       ptr = q;
       q = q->Right;
     }
  }
  return ptr;
}

BNodeBase *ParentOfSuccessor(BNodeBase *Tree)
// Returns parent of successor of Tree, assumed to be
// a binary search tree. Successor is the left child
// of node returned, unless Tree itself is the parent.
// Then the right child is the successor. If Tree is a
// leaf, a 0 is returned. Assumes Tree is not Tree null.
{
  BNodeBase *ptr = 0;
  // Go right, then all the way left
  BNodeBase *q = Tree->Right;
  if (q) {
     ptr = Tree;
     while(q->Left) {
       ptr = q;
       q = q->Left;
     }
  }
  return ptr;
}

BNodeBase *DetachNode
(BNodeBase *&Root, BNodeBase *Tree, BNodeBase *p, int Side)
// Detaches node Tree with parent p from the tree. Node Tree is
// the left child if Side = 0, else it's the right child.
// If p is 0, it means Tree is the root, and that is handled
// accordingly. Redundantly returns the pointer Tree. May
// have to update root pointer.
{
  BNodeBase *psucc, *replacement;

  if (Tree) {
     if (Tree->Left == 0 || Tree->Right == 0) {
        // At least one child is null, so use the other
        // as the replacement. (It may be null too.)
        replacement = (Tree->Left) ? Tree->Left : Tree->Right;
     }
     else { // Neither child is null
        psucc = ParentOfSuccessor(Tree); // guaranteed not null
        if (psucc == Tree) { // Immediate successor
           replacement = psucc->Right;
        }
        else {
           // Detach replacement from where it is and relocate
           // it to where Tree used to be.
           replacement = psucc->Left;
           psucc->Left = psucc->Left->Right;
           replacement->Right = Tree->Right;
        }
        // Finish relocating replacement to go where Tree used to.
        replacement->Left = Tree->Left;
     }
     if (p) { // Fixup parent of Tree to point to replacement
        if (Side) p->Right = replacement; else p->Left = replacement;
     }
     else Root = replacement; // No parent, so Tree was the root
  }
  return Tree;
}
// ----------------------------------------------------------- //
// ------------------------------- //
// --------- End of File --------- //
// ------------------------------- //