avlbin~1.h

经典c++程序的实现

class AVLBinNode {                // Binary tree node class
public:
  BELEM element;               // The node's value
  AVLBinNode* left;               // Pointer to left child
  AVLBinNode* right;              // Pointer to right child  
  int bf;					   // balance factor
  static AVLBinNode* freelist;
  // Two constructors -- with and without initial values
  AVLBinNode() { left = right = NULL; }
  AVLBinNode(BELEM e, AVLBinNode* l =NULL, AVLBinNode* r =NULL)
    { element = e; left = l; right = r; }
  ~AVLBinNode() { }               // Destructor
  AVLBinNode* leftchild() const { return left; }
  AVLBinNode* rightchild() const { return right; }
  BELEM value() const { return element; };
  void setValue(BELEM val) { element = val; }
  bool isLeaf() const          // Return TRUE if is a leaf
    { return (left == NULL) && (right == NULL); }
  void* operator new(size_t);  // Overload new  
  void operator delete(void*); // Overload delete
};

// This creates space for the freelist variable
AVLBinNode* AVLBinNode::freelist = NULL;

void* AVLBinNode::operator new(size_t) { // Overload new
  if (freelist == NULL) return ::new AVLBinNode; // Create new space
  AVLBinNode* temp = freelist;       // Otherwise, get from freelist
  freelist = freelist->left;
  return temp;                    // Return the link node
}

void AVLBinNode::operator delete(void* ptr) { // Overload delete
  ((AVLBinNode*)ptr)->left = freelist;  // Put on freelist
  freelist = (AVLBinNode*)ptr;
}