avltree.h

#ifndef AVLTREE_CLASS
#define AVLTREE_CLASS

#include <iostream.h>
#include <stdlib.h>

#include "bstree.h"

// ***********************************************************
// **********     AVLTreeNode class 		 *******************
// ***********************************************************

template <class T>
class AVLTree;

// inherits the TreeNode class
template <class T>
class AVLTreeNode: public TreeNode<T>
{
   private:
      // additional data member needed by AVLTreeNode
      int balanceFactor;
      // used by AVLTree class methods to allow assignment
      // to a TreeNode pointer without casting
      AVLTreeNode<T>* & Left(void);
      AVLTreeNode<T>* & Right(void);

   public:
      // constructor
      AVLTreeNode (const T& item, AVLTreeNode<T> *lptr = NULL,
                   AVLTreeNode<T> *rptr = NULL, int balfac = 0);
         
      // methods that return left/right TreeNode pointers as 
      // AVLTreeNode pointers; handles casting for the client
      AVLTreeNode<T>* Left(void) const;
      AVLTreeNode<T>* Right(void) const;

      // method to access new data field
      int GetBalanceFactor(void);
   
      // AVLTree methods needs access to left and right
      friend class AVLTree<T>;
};

// return a reference to left after casting it to an
// AVLTreeNode pointer. use to change left
template <class T>
AVLTreeNode<T>* & AVLTreeNode<T>::Left(void)
{
   return (AVLTreeNode<T> *)left;
}

// return a reference to right after casting it to an
// AVLTreeNode pointer. use to change right
template <class T>
AVLTreeNode<T>* & AVLTreeNode<T>::Right(void)
{
   return (AVLTreeNode<T> *)right;
}


// constructor; initialize balanceFactor and the base class.
// default pointer values NULL initialize node as a leaf node
template <class T>
AVLTreeNode<T>::AVLTreeNode (const T& item,
      AVLTreeNode<T> *lptr, AVLTreeNode<T> *rptr, int balfac):
   TreeNode<T>(item,lptr,rptr), balanceFactor(balfac)
{}

// return left after casting it to an AVLTreeNode pointer
template <class T>
AVLTreeNode<T>* AVLTreeNode<T>::Left(void) const
{
   return (AVLTreeNode<T> *)left;
}

// return right after casting it to an AVLTreeNode pointer
template <class T>
AVLTreeNode<T>* AVLTreeNode<T>::Right(void) const
{
   return (AVLTreeNode<T> *)right;
}

template <class T>
int AVLTreeNode<T>::GetBalanceFactor(void)
{
   return balanceFactor;
}

// *************  AVLTree class  *************************
// *******************************************************

// constants to indicate the balance factor of a node
const int leftheavy = -1;
const int balanced = 0;
const int rightheavy = 1;

// derived search tree class
template <class T>
class AVLTree: public BinSTree<T>
{
   private:
   
      // memory allocation
      AVLTreeNode<T> *GetAVLTreeNode(const T& item,
               AVLTreeNode<T> *lptr,AVLTreeNode<T> *rptr);
      
      // used by copy constructor and assignment operator
      AVLTreeNode<T> *CopyTree(AVLTreeNode<T> *t);
      
      // used by Insert and Delete method to re-establish 
      // the AVL conditions after a node is added or deleted
      // from a subtree
      void SingleRotateLeft (AVLTreeNode<T>* &p);
      void SingleRotateRight (AVLTreeNode<T>* &p);
      void DoubleRotateLeft (AVLTreeNode<T>* &p);
      void DoubleRotateRight (AVLTreeNode<T>* &p);
      void UpdateLeftTree (AVLTreeNode<T>* &tree,
                      int &reviseBalanceFactor);
      void UpdateRightTree (AVLTreeNode<T>* &tree,
                        int &reviseBalanceFactor);
      
      // class specific versions of the general Insert and
      // Delete methods
      void AVLInsert(AVLTreeNode<T>* &tree,
            AVLTreeNode<T>* newNode, int &reviseBalanceFactor);
      void AVLDelete(AVLTreeNode<T>* &tree,
            AVLTreeNode<T>* newNode, int &reviseBalanceFactor);
      
   public:
      // constructors, destructor
      AVLTree(void);
      AVLTree(const AVLTree<T>& tree);
      
      // assignment operator
      AVLTree<T>& operator= (const AVLTree<T>& tree);
      
      // standard list handling methods
      virtual void Insert(const T& item);
      virtual void Delete(const T& item); 
};

// allocate an AVLTreeNode; terminate the program on a memory
// allocation error
template <class T>
AVLTreeNode<T> *AVLTree<T>::GetAVLTreeNode(const T& item,
               AVLTreeNode<T> *lptr, AVLTreeNode<T> *rptr)
{
   AVLTreeNode<T> *p;

   p = new AVLTreeNode<T> (item, lptr, rptr);
   if (p == NULL)
   {
      cerr << "Memory allocation failure!\n";
      exit(1);
   }
   return p;
}

template <class T>
AVLTreeNode<T> *AVLTree<T>::CopyTree(AVLTreeNode<T> *t)
{
   AVLTreeNode<T> *newlptr, *newrptr, *newNode;
   
   if (t == NULL)
   return NULL;
   
   if (t->Left() != NULL) 
   newlptr = CopyTree(t->Left());
   else
   newlptr = NULL;
 
   if (t->Right() != 0) 
   newrptr = CopyTree(t->Right());
   else
   newrptr = NULL;
 
   newNode = GetAVLTreeNode(t->data, newlptr, newrptr);
   return newNode;
}


template <class T>
void AVLTree<T>::SingleRotateLeft (AVLTreeNode<T>* &p)
{
   AVLTreeNode<T> *rc;

   rc = p->Right();
   p->balanceFactor = balanced;
   rc->balanceFactor = balanced;
   p->Right() = rc->Left();
   rc->Left() = p;
   p = rc;
} 

// rotate clockwise about node p; make lc the new pivot
template <class T>
void AVLTree<T>::SingleRotateRight (AVLTreeNode<T>* & p)
{
   // the left subtree of p is heavy
   AVLTreeNode<T> *lc;

   // assign the left subtree to lc
   lc = p->Left();
   
   // update the balance factor for parent and left child
   p->balanceFactor = balanced;
   lc->balanceFactor = balanced;

   // any right subtree of lc must continue as right subtree
   // of lc. do this by making it a left subtree of p
   p->Left() = lc->Right();

   // rotate p (larger node) into right subtree of lc
   // make lc the pivot node
   lc->Right() = p;
   p = lc;
} 

template <class T>
void AVLTree<T>::DoubleRotateLeft (AVLTreeNode<T>* &p)
{
   AVLTreeNode<T> *rc, *np;
   
   rc = p->Right();
   np = rc->Left();
   if (np->balanceFactor == leftheavy)
   {
      p->balanceFactor = balanced;
      rc->balanceFactor = rightheavy;
   }
   else if (np->balanceFactor == balanced)
   {
      p->balanceFactor = balanced;
      rc->balanceFactor = balanced;
   }
   else
   {
      p->balanceFactor = leftheavy;
      rc->balanceFactor = balanced;
   }
   np->balanceFactor = balanced;
   rc->Left() = np->Right();
   np->Right() = rc;
   p->Right() = np->Left();
   np->Left() = p;
   p = np;
} 

// double rotation right about node p
template <class T>
void AVLTree<T>::DoubleRotateRight (AVLTreeNode<T>* &p)
{
   // two subtrees that are rotated
   AVLTreeNode<T> *lc, *np;

   // in the tree,  node(lc) < nodes(np) < node(p)
   lc = p->Left();		// lc is left child of parent
   np = lc->Right();		// np is right child of lc

	// update balance factors for p, lc, and np
	if (np->balanceFactor == rightheavy)
	{
		p->balanceFactor = balanced;
		lc->balanceFactor = leftheavy;
	}
   else if (np->balanceFactor == balanced)
   {
      p->balanceFactor = balanced;
      lc->balanceFactor = balanced;
   }
   else
   {
      p->balanceFactor = rightheavy;
      lc->balanceFactor = balanced;
   }
   np->balanceFactor = balanced;

   // before np replaces the parent p, take care of subtrees
   // detach old children and attach new children
   lc->Right() = np->Left();
   np->Left() = lc;
   p->Left() = np->Right();
   np->Right() = p;
   p = np;
} 


template <class T>
void AVLTree<T>::UpdateLeftTree (AVLTreeNode<T>* &p,
                         int &reviseBalanceFactor)
{
   AVLTreeNode<T> *lc;
   
   lc = p->Left();             // left subtree is also heavy
   if (lc->balanceFactor == leftheavy) 
   {
      SingleRotateRight(p);    // need a single rotation
      reviseBalanceFactor = 0;
   }
   // is right subtree heavy?
   else if (lc->balanceFactor == rightheavy)
   {
      // make a double rotation
      DoubleRotateRight(p);
      // root is now balanced
      reviseBalanceFactor = 0;
   }
}

template <class T>
void AVLTree<T>::UpdateRightTree (AVLTreeNode<T>* &p,
                           int &reviseBalanceFactor)
{
   AVLTreeNode<T> *rc;
   
   rc = p->Right();
   if (rc->balanceFactor == rightheavy) 
   {
   	SingleRotateLeft(p);
   	reviseBalanceFactor = 0;
   }
   else if (rc->balanceFactor == leftheavy) 
   {
   	DoubleRotateLeft(p);
   	reviseBalanceFactor = 0;
   }
}

// insert a new node using the basic List operation and format
template <class T>
void AVLTree<T>::Insert(const T& item)
{

   // declare AVL tree node pointer. using base class method
   // GetRoot, cast to larger node and assign root pointer
   AVLTreeNode<T> *treeRoot = (AVLTreeNode<T> *)GetRoot(),
               *newNode;
   
   // flag used by AVLInsert to rebalance nodes
   int reviseBalanceFactor = 0;
   
   // get a new AVL tree node with empty poiner fields
   newNode = GetAVLTreeNode(item,NULL,NULL);
   
   // call recursive routine to actually insert the element
   AVLInsert(treeRoot, newNode, reviseBalanceFactor);
   
   // assign new values to data members root, size
   // current in the base class
   root = treeRoot;
   current = newNode;
   size++;
}

template <class T>
void AVLTree<T>:: AVLInsert(AVLTreeNode<T>* & tree,
                AVLTreeNode<T>* newNode, int& reviseBalanceFactor)
{
   // flag indicates change node's balanceFactor will occur
   int rebalanceCurrNode;

   // scan reaches an empty tree; time to insert the new node
   if (tree == NULL)
   {
      // update the parent to point at newNode     
      tree = newNode;

      // assign balanceFactor = 0 to new node
      tree->balanceFactor = balanced;

      // broadcast message; balanceFactor value is modified
      reviseBalanceFactor = 1;       
   }

   // recursively move left if new data < current data
   else if (newNode->data < tree->data)
   {
      AVLInsert(tree->Left(),newNode,rebalanceCurrNode);
      // check if balanceFactor must be updated. 
      if (rebalanceCurrNode)
      {
         // case 3: went left from node that is already heavy
         // on the left. violates AVL condition; rotatate
         if (tree->balanceFactor == leftheavy)
            UpdateLeftTree(tree,reviseBalanceFactor);
            
         // case 1: moving left from balanced node. resulting
         // node will be heavy on left
         else if (tree->balanceFactor == balanced)
         {
            tree->balanceFactor = leftheavy;
            reviseBalanceFactor = 1;
         }
         // case 2: scanning left from node heavy on the
         // right. node will be balanced
         else
         {
            tree->balanceFactor = balanced;
            reviseBalanceFactor = 0;
         }
      }
      else
         // no balancing occurs; do not ask previous nodes
         reviseBalanceFactor = 0;
   }

   // otherwise recursively move right
   else
   {
      AVLInsert(tree->Right(), newNode, rebalanceCurrNode);
      // check if balanceFactor must be updated. 
      if (rebalanceCurrNode)
      {
         // case 2: node becomes balanced
         if (tree->balanceFactor == leftheavy)
         {
            // scanning right subtree. node heavy on left.
            // the node will become balanced
            tree->balanceFactor = balanced;     
            reviseBalanceFactor = 0;
         }
         // case 1: node is initially balanced
         else if (tree->balanceFactor == balanced)
         {
            // node is balanced; will become heavy on right
            tree->balanceFactor = rightheavy;
            reviseBalanceFactor = 1;
         }
         else
            // case 3: need to update node
            // scanning right from a node already heavy on 
            // the right. this violates the AVL condition
            // and rotations are needed.
            UpdateRightTree(tree, reviseBalanceFactor);
      }
      else
         reviseBalanceFactor = 0;
   }
}


template <class T>
AVLTree<T>::AVLTree(void): BinSTree<T>()
{}

template <class T>
AVLTree<T>::AVLTree(const AVLTree<T>& tree)
{
   root=(TreeNode<T> *)CopyTree((AVLTreeNode<T> *)tree.root);
   current = root;
   size = tree.size;
}

template <class T>
AVLTree<T>& AVLTree<T>::operator= (const AVLTree<T>& tree)
{
   ClearList();
   root=(TreeNode<T> *)CopyTree((AVLTreeNode<T> *)tree.root);
   current = root;
   size = tree.size;
   return *this;
}

// Delete is empty. suppress warning message that item not used
#pragma warn -par
// Find the node with value item and delete it.
template <class T>
void AVLTree<T>::Delete(const T& item)
{
}

// spacing between levels
const int indentAVLBlock = 6;

// inserts num blanks on the current line
void IndentAVLBlanks(int num)
{
   for(int i = 0;i < num; i++) 
      cout << " ";
}

// print an AVL tree sideways using an RNL tree traversal
template <class T>
void AVLPrintTree (AVLTreeNode<T> *t, int level)
{
   // print tree with root t, as long as t != NULL
   if (t != NULL)
   {
      // print right branch of AVL tree t
      AVLPrintTree(t->Right(),level + 1);
      // indent. output node data and balance factor
      IndentAVLBlanks(indentAVLBlock*level);
      cout << t->data << ':' << t->GetBalanceFactor()<<endl;
      // print left branch of AVL tree t
      AVLPrintTree(t->Left(),level + 1);
   }
}

#endif // AVLTREE_CLASS

bstree.h

#ifndef BINARY_SEARCH_TREE_CLASS
#define BINARY_SEARCH_TREE_CLASS

#include <iostream.h>
#include <stdlib.h>

#ifndef NULL
const int NULL = 0;
#endif  // NULL

#include "treenode.h"

template <class T>
class BinSTree
{
    protected:
        // pointer to tree root and node most recently accessed
        TreeNode<T> *root;
        TreeNode<T> *current;
        
        // number of elements in the tree
        int size;
    
        // memory allocation/deallocation
        TreeNode<T> *GetTreeNode(const T& item,
                        TreeNode<T> *lptr,TreeNode<T> *rptr);
        void FreeTreeNode(TreeNode<T> *p);
        
        // used by copy constructor and assignment operator
        TreeNode<T> *CopyTree(TreeNode<T> *t);
        
        // used by destructor, assignment operator and ClearList
        void DeleteTree(TreeNode<T> *t);

        // locate a node with data item and its parent in tree.
        // used by Find and Delete
        TreeNode<T> *FindNode(const T& item,
                              TreeNode<T>* & parent) const;

    public:
        // constructors, destructor
        BinSTree(void);
        BinSTree(const BinSTree<T>& tree);
        ~BinSTree(void);
        
        // assignment operator
        BinSTree<T>& operator= (const BinSTree<T>& rhs);
        
        // standard list handling methods
        int Find(T& item);
        void Insert(const T& item);
        void Delete(const T& item);
        void ClearList(void);
        int ListEmpty(void) const;
        int ListSize(void) const;
        
        // tree specific methods
        void Update(const T& item);
        TreeNode<T> *GetRoot(void) const;
};

// allocate a new tree node and return a pointer to it
template <class T>
TreeNode<T> *BinSTree<T>::GetTreeNode(const T& item,TreeNode<T> *lptr,TreeNode<T> *rptr)
{
    TreeNode<T> *p;

    // the data field and both pointers are initialized
    p = new TreeNode<T> (item, lptr, rptr);
    if (p == NULL)
    {
        cerr << "Memory allocation failure!\n";
        exit(1);
    }
    return p;
}

// delete the storage occupied by a tree node
template <class T>
void BinSTree<T>::FreeTreeNode(TreeNode<T> *p)
{
    delete p;
}

// copy tree t and make it the tree stored in the current object
template <class T>
TreeNode<T> *BinSTree<T>::CopyTree(TreeNode<T> *t)
{
    TreeNode<T> *newlptr, *newrptr, *newNode;
   
    // if tree branch NULL, return NULL
    if (t == NULL)
        return NULL;
        
    // copy the left branch of root t and assign its root to newlptr
    if (t->left != NULL) 
        newlptr = CopyTree(t->left);
    else
        newlptr = NULL;
 
    // copy the right branch of tree t and assign its root to newrptr
    if (t->right != NULL) 
        newrptr = CopyTree(t->right);
    else
        newrptr = NULL;
 
    // allocate storage for the current root node and assign its data value
    // and pointers to its subtrees. return its pointer
    newNode = GetTreeNode(t->data, newlptr, newrptr);
    return newNode;
}

// delete the tree stored by the current object
template <class T>
void BinSTree<T>::DeleteTree(TreeNode<T> *t)
{
    // if current root node is not NULL, delete its left subtree,
    // its right subtree and then the node itself
    if (t != NULL)
    {
        DeleteTree(t->left);
        DeleteTree(t->right);
        FreeTreeNode(t);
    }
}

// search for data item in the tree. if found, return its node
// address and a pointer to its parent; otherwise, return NULL
template <class T>
TreeNode<T> *BinSTree<T>::FindNode(const T& item,
                                   TreeNode<T>* & parent) const
{   
    // cycle t through the tree starting with root
    TreeNode<T> *t = root;
    
    // the parent of the root is NULL
    parent = NULL;
    
    // terminate on on empty subtree
    while(t != NULL)
    {
        // stop on a match
        if (item == t->data)
            break;
        else 
        {
            // update the parent pointer and move right or left
            parent = t;
            if (item < t->data)
                t = t->left;
            else 
                t = t->right;
        }
    }
    
    // return pointer to node; NULL if not found
    return t;
}

// constructor. initialize root,current to NULL, size to 0
template <class T>
BinSTree<T>::BinSTree(void): root(NULL),current(NULL),size(0)
{}

// copy constructor
template <class T>
BinSTree<T>::BinSTree(const BinSTree<T>& tree)
{
    // copy tree to the current object. assign current and size
    root = CopyTree(tree.root);
    current = root;
    size = tree.size;
}

// destructor
template <class T>
BinSTree<T>::~BinSTree(void)
{
    // just call ClearList
    ClearList();
}

// assignment operator
template <class T>
BinSTree<T>& BinSTree<T>::operator= (const BinSTree<T>& rhs)
{
    // can't copy a tree to itself
    if (this == &rhs)
        return *this;
        
    // clear current tree. copy new tree into current object
    ClearList();
    root = CopyTree(rhs.root);
    
    // assign current to root and set the tree size
    current = root;
    size = rhs.size;
    
    // return reference to current object
    return *this;
}

// search for item. if found, assign the node data to item
template <class T>
int BinSTree<T>::Find(T& item)
{
    // we use FindNode, which requires a parent parameter
    TreeNode<T> *parent;

    // search tree for item. assign matching node to current
    current = FindNode (item, parent);
    
    // if item found, assign data to item and return True
    if (current != NULL)
    {
        item = current->data;
        return 1;
    }
    else
    	// item not found in the tree. return False
        return 0;
}

// insert item into the search tree
template <class T>
void BinSTree<T>::Insert(const T& item)
{
    // t is current node in traversal, parent the previous node
    TreeNode<T> *t = root, *parent = NULL, *newNode;

    // terminate on on empty subtree
    while(t != NULL)
    {
        // update the parent pointer. then go left or right
        parent = t;
        if (item < t->data)
            t = t->left;
        else 
            t = t->right;
    }
    
    // create the new leaf node
    newNode = GetTreeNode(item,NULL,NULL);
    
    // if parent is NULL, insert as root node
    if (parent == NULL)
        root = newNode;
        
    // if item < parent->data, insert as left child        
    else if (item < parent->data)                   
        parent->left = newNode;
        
    else
        // if item >= parent->data, insert as right child     
        parent->right = newNode;
        
    // assign current as address of new node and increment size
    current = newNode;
    size++;
}

// if item is in the tree, delete it
template <class T>
void BinSTree<T>::Delete(const T& item)
{
    // DNodePtr = pointer to node D that is deleted
    // PNodePtr = pointer to parent P of node D
    // RNodePtr = pointer to node R that replaces D
    TreeNode<T> *DNodePtr, *PNodePtr, *RNodePtr;
    
    // search for a node containing data value item. obtain its
    // node address and that of its parent
    if ((DNodePtr = FindNode (item, PNodePtr)) == NULL)
        return;
    
    // If D has a NULL pointer, the
    // replacement node is the one on the other branch
    if (DNodePtr->right == NULL)
        RNodePtr = DNodePtr->left;
    else if (DNodePtr->left == NULL)
        RNodePtr = DNodePtr->right;
        
    // Both pointers of DNodePtr are non-NULL.
    else
    {
        // Find and unlink replacement node for D.
        // Starting on the left branch of node D,
        // find node whose data value is the largest of all
        // nodes whose values are less than the value in D.
        //  Unlink the node from the tree.
        
        // PofRNodePtr = pointer to parent of replacement node
        TreeNode<T> *PofRNodePtr = DNodePtr;
        
        // first possible replacement is left child of D
        RNodePtr = DNodePtr->left;
    
        // descend down right subtree of the left child of D,
        // keeping a record of current node and its parent.
        // when we stop, we have found the replacement
        while(RNodePtr->right != NULL)
        {
            PofRNodePtr = RNodePtr;
            RNodePtr = RNodePtr->right;
        }
        
        if (PofRNodePtr == DNodePtr)
            // left child of deleted node is the replacement.
            // assign right subtree of D to R
            RNodePtr->right = DNodePtr->right;
        else
        {
            // we moved at least one node down a right branch
            // delete replacement node from tree by assigning
            // its left branch to its parent
            PofRNodePtr->right = RNodePtr->left;
            
            // put replacement node in place of DNodePtr.
            RNodePtr->left = DNodePtr->left;
            RNodePtr->right = DNodePtr->right;
        }
    }

    // complete the link to the parent node.
    
    // deleting the root node. assign new root
    if (PNodePtr == NULL)
        root = RNodePtr;
        
    // attach R to the correct branch of P
    else if (DNodePtr->data < PNodePtr->data)
        PNodePtr->left = RNodePtr;
    else
        PNodePtr->right = RNodePtr;
        
    // delete the node from memory and decrement list size
    FreeTreeNode(DNodePtr);
    size--;
}

// delete all the nodes in the tree. current now NULL and size is 0
template <class T>
void BinSTree<T>::ClearList(void)
{
    DeleteTree(root);
    root = NULL;
    current = NULL;
    size = 0;
}

// indicate whether the tree is empty
template <class T>
int BinSTree<T>::ListEmpty(void) const
{
    return root == NULL;
}

// return the number of data items in the tree
template <class T>
int BinSTree<T>::ListSize(void) const
{
    return size;
}

// if current node is defined and its data value matches item,
// assign node value to item ; otherwise, insert item in tree
template <class T>
void BinSTree<T>::Update(const T& item)
{   
    if (current != NULL && current->data == item)
            current->data = item;
    else
        Insert(item);
}

// return the address of the root node.
template <class T>
TreeNode<T> *BinSTree<T>::GetRoot(void) const
{
    return root;
}

#endif  // BINARY_SEARCH_TREE_CLASS

ListNode.h

#ifndef LIST_NODE_CLASS
#define LIST_NODE_CLASS


class Node {
protected:
  Node *_next;	// связь к последующему узлу
  Node *_prev;	// связь к предшествующему узлу
public:
  Node (void);
  virtual ~Node (void);
  Node *next(void);
  Node *prev(void);
  Node *insert(Node*);  // вставить узел после текущего
  Node *remove(void);  // удалить узел из списка, возвратить его указатель
  void splice(Node*);
};

Node::Node (void):
_next ( this ) , _prev ( this ) {}

Node::-Node (void) {}

Node *Node::next(void) 
{
  return _next;
}
Node *Node::prev(void) 
{
  return _prev;
}

Node *Node::insert(Node *b)
{
  Node *c = _next;
  b->__next = c;
  b->_prev = this ;
  _next = b;
  c->_prev = b;
  return b;
}

Node *Node::remove(void)
{
  _prev->_next = _next;
  _next->_prev = _prev;
  _next = _prev = this;
  return  this;
}

void Node::splice (Node *b)
{
  Node *a = this;
  Node *an = a->_next;
  Node *bn = b->_next;
  a->_next = bn;
  b->_next = an;
  an->_prev = b;
  bn->_prev = a;
}

template<class T> class List;

template<class T> class ListNode : public Node  {
 public :
  Т _val;
  ListNode (Т val);
  friend class List<T>;
};

template<class T> ListNode::ListNode (Т val) :
   _val(val) {}

template<class T> class List {
 private:
  ListNode<T> *header;
  ListNode<T> *win;
  int _length;
 public :
  List (void);
  ~List (void);
  Т insert (T);
  T append (Т);
  List *append(List *);
  Т prepend(T);
  Т remove (void);
  void val (T);
  Т val (void);
  T next (void);
  T prev(void);
  T first (void);
  T last (void);
  int length (void);
  bool isFirst (void);
  bool isLast (void);
  bool isHead(void);
};

template<class T> List<T>::List(void) : 
  _length(0)
{
  header = new ListNode<T> (NULL);
  win = header;
}

template<class T> List<T>::~List (void)
{
  while (length() > 0) {
    first();
	remove ();
  }
  delete header;
}

template<class T> T List<T>::insert(T val)
{
  win->insert(new ListNode<T>(val) );
  ++_length;
  return val;
}

template<class Т> Т List<T>::prepend(T val)
{
  header->insert (new ListNode<T> (val));
  ++_length;
  return val;
}

template<class T> Т List<T>::append (T val)
{
  header->prev()->insert (new ListNode<T> (val) );
  ++_length;
  return val;
}

template<class T> List<T>* List<T>::append (List<T> *1)
{
  ListNode<T> *a = (ListNode<T>*) header->prev() ;
  a->splice(l->header);
  _length += l-> _length;
  l->header->remove();
  l->_length = 0;
  l->win = header;
  return this;
}

template<class T> T List<T>::remove (void)
{
  if (win == header) return NULL;
  void *val = win->_val;
  win = (ListNode<T>*) win->prev();
  delete (ListNode<T>*) win->next()->remove();
  -— _length ;
  return val;
}

void List<T>::val (T v)
{
  if (win != header) 
    win->_val = v;
}

template<class T> T List<T>::val(void)
{
  return win->_val;
}

template<class T> T List<T>::next(void)
{
  win = (ListNode<T>*) win->next();
  return win->_val;
}

template<class T> T List<T>::prev(void)
{
  win = (ListNode<T>*) win->prev();
  return win->_val;
}

template<class T> T List<T>::first (void)
{
  win = (ListNode<T>*) header->next();
  return win->_val;
}

template<class T> T List<T>::last (void)
{
  win = (ListNode<T>*) header->prev();
  return win->_val;
}

template<class T> int List<T>::length (void)
{
  return _length;
}

template<class T> bool List<T>::isPirst(void)
{
  return ( (win == header->next() ) && (_length > 0) );
}

template<class T> bool List<T>::isLast (void)
{
  return ( (win == header->prev() ) && (_length > 0) );
}

template>class T> bool List<T>::isHead(void)
{
  return (win == header);
}


#endif  // LIST_NODE_CLASS

treenode.h

#ifndef TREE_NODE_CLASS
#define TREE_NODE_CLASS

#include <iostream.h>
#include <stdlib.h>
#include "ListNode.h"

template<class T>
class SearchTree;

template<class T>
class BraidedSearchTree;

template<class T> class TreeNode {
 protected:
  TreeNode  *_lchild;
  TreeNode  *_rchild;
  Т val;
 public:
  TreeNode(T);
  virtual ~TreeNode(void);
  friend class SearchTree<T>;        // возможные пополнения
  friend class BraidedSearchTree<T>; // структуры
};

template<class T> TreeNode<T>::TreeNode(T v) :
  val(v), _lchild(NULL), _rchild (NULL) {}
  
 template<class T> TreeNode<T>::~TreeNode(void) {
  if (_lchild) delete _lchild;
  if (_rchild) delete _rchild;
}

template<class T> class SearchTree {
 private:
  TreeNode *root;
  int  (*) (T,T) cmp;
  TreeNode<T> *_findMin(TreeNode<T> *);
  void _remove(T, TreeNode<T> * &);
  void _inorder(TreeNode<T> *, void (*) (T) );
 public:
  SearchTree (int(*) (Т, Т) );
  ~SearchTree (void);
  int isEmpty (void);
  Т find(T);
  Т findMin(void);
  void inorder (void(*) (T) );
  void insert(T);
  void remove(T);
  T removeMin (void);
};

template<class T> SearchTree<T>::SearchTree (int (*с) (Т, Т) ) :
  cmp(с), root (NULL) {}
  
template<class T> int SearchTree<T>::isEmpty (void)
{
  return (root == NULL);
}

template<class T> SearchTree<T>::~SearchTree (void)
{
  if (root) delete root;
}

template<class T> T SearchTree::find (T val)
{
  TreeNode *n = root;
  while (n) {
    int result = (*cmp) (val, n->val);
    if (result < 0)
      n = n->_lchild;
	else if (result > 0)
      n = n->_rchild;
	else
      return n->val;
  }
  return  NULL;
}

template<class T> T SearchTree<T>::findMin (void)
{
  TreeNode<T> *n = _findMin (root);
  return (n ? n->val : NULL);
}

template<class T>
TreeNode<T> *SearchTree<T>::_findMin (TreeNode<T> *n)
{
  if (n  == NULL)
    return NULL;
  while   (n->_lchild)
    n = n->_lchild;
  return n;
}

/*
 * Обход двоичного дерева — это процесс, при котором каждый узел посещается точно только один раз. Компонентная
 * функция inorder выполняет специальную форму обхода, известную как симметричный обход. Стратегия заключается
 * сначала в симметричном обходе левого поддерева, затем посещения корня и потом в симметричном обходе правого
 * поддерева. Узел посещается путем применения функции обращения к элементу, записанному в узле.
 * 
 * Компонентная функция inorder служит в качестве ведущей функции. Она обращается к собственной компонентной
 * функции _inorder, которая выполняет симметричный обход от узла n и применяет функцию visit к каждому
 * достигнутому узлу.
 * Lt > t > Rt scheme
 */
template<class T> void SearchTree<T>::inorder (void (*visit)    (Т) )
{
  _inorder (root, visit);
}

template<class T>
void SearchTree::_inorder (TreeNode<T> *n, void(*visit) (T)
{
  if (n) {
    _inorder (n->_lchild, visit);
    (*visit) (n->val);
    _inorder (n->_rchild, visit);
  }
}

template<class T> void SearchTree<T>::insert(T val)
{
  if (root == NULL) {
    root = new TreeNode<T>(val);
	return;
  } else {
    int result;
    TreeNode<T> *p, *n = root;
    while (n) {
	  p = n;
      result = (*cmp) (val, p->val);
	if (result < 0)
      n = p->_lchild;
	else if (result > 0)
      n = p->_rchild;
	else
      return;
	}
    if (result < 0)
      p->_lchild = new TreeNode<T>(val);
	else
      p-> rchild = new TreeNode<T>(val);
  }
}

template<class T> void SearchTree<T>::remove(Т val)
{
  _remove(val, root); 
}

template<class T>
void SearchTree<T>::_remove(Т val, TreeNode<T> * &n)
{
  if (n == NULL)
    return;
  int result = (*cmp) (val, n->val);
  if (result < 0)
    _remove(val, n->_lchild);
  else if (result > 0)
    _remove (val, n->_rchild);
  else {                              // случай 1
    if (n->_lchild == NULL) {
	  TreeNode<T> *old = n;
	  n = old->_rchild;
	  delete old;
	}
    else if (n->_rchild == NULL {     // случай 2
      TreeNode<T> *old = n;
      n = old->_lchild;
	  delete old;
    }
    else {	                          // случай 3
      TreeNode<T> *m = _findMin(n->_rchild);
	  n->val = m->val;
	  remove(m->val, n->_rchild);
	}
  }
}

template<class Т> Т SearchTree<T>::removeMin (void)
{
  Т v = findMin();
  remove (v);
  return v;
}

/*
 * Древовидная сортировка — способ сортировки массива элементов — реализуется в виде простой программы,
 * использующей деревья поиска. Идея заключается в занесении всех элементов в дерево поиска и затем в
 * интерактивном удалении наименьшего элемента до тех пор, пока не будут удалены все элементы. Программа heapSort
 * (пирамидальная сортировка) сортирует массив s из n элементов, используя функцию сравнения cmp.
 */
template<class T> void heapSort (T s[], int n, int(*cmp) (T,T) )
{
  SearchTree<T> t(cmp);
  for (int i = 0; i < n; i++)
    t.insert(s[i]);
  for (i = 0; i < n; i++)
    s[i) = t.removeMin();
}

//----------------------------------------------------------------------

template<class T>
class BraidedNode : public Node, public TreeNode<T> {
 public :
  BraidedNode (T);
  BraidedNode<T> *rchild(void);
  BraidedNode<T> *lchild (void);
  BraidedNode<T> *next (void);
  BraidedNode<T> *prev(void);
  friend class BraidedSearchTree<T>;
};

template<class T> BraidedNode<T>::BraidedNode (Т val) : 
  TreeNode<T> (val) {}
  
template<class T>
BraidedNode<T> *BraidedNode<T>::rchild (void)
{
  return (BraidedNode<T> *)_rchild;
}

template<class T>
BraidedNode<T> *BraidedNode<T>::lchild (void)
{
  return (BraidedNode<T> *) )_lchild;
}

template<class T>
BraidedNode<T> *BraidedNode<T>::next (void)
{
  return (BraidedNode<T> *)_next;
}

template<class T>
BraidedNode<T> *BraidedNode<T>::prev (void)
{
  return (BraidedNode<T> *)_prev;
}

template<class T> class BraidedSearchTree {
 private:
  BraidedNode<T> *root;    // головной узел
  BraidedNode<T> *win;     // текущее окно
  int (*cmp) (T,T);        // функция сравнения
  void _remove(T, TreeNode<T> * &);
 public:
  BraidedSearchTree (int(*) (T,T) );
  ~BraidedSearchTree (void);
  Т next (void);
  Т prev (void);
  void inorder (void(*) (T) );
  Т val (void);
  bool isFirst (void);
  bool isLast (void);
  bool is Head (void);
  bool isEmpty (void);
  Т find (T);
  Т findMin (void);
  T insert (T);
  void remove (void);
  T removeMin (void);
};

template<class T>
BraidedSearchTree<T>::BraidedSearchTree (int (*с) (Т, Т) ) :
  cmp(c)
{
  win = root = new BraidedNode<T> (NULL);
}

template<class T>
BraidedSearchTree<T>::~BraidedSearchTree (void)
{
  delete root;
}

template<class Т> Т BraidedSearchTree<T>::next (void)
{
  win = win->next();
  return win->val;
}

template<class T> Т BraidedSearchTree<T>::prev(void)
{
  win = win->prev();
  return win->val;
}

template<class T> T BraidedSearchTree<T>::val (void)
{
  return win->val;
}

template<class T>
void BraidedSearchTree<T>::inorder (void (*visit) (Т) )
{
  BraidedNode<T> *n = root->next();
  while (n != root) {
    (*visit)(n->val);
    n = n->next();
  }
}

template<class T> bool BraidedSearchTree<T>::isFirst (void)
{
  return (win == root->next() ) && (root != root->next ());
}

template<class T> bool BraidedSearchTree<T>::isLast (void)
{
  return (win == root->prev() ) && (root != root->next() );
}

template<class T> bool BraidedSearchTree<T>::isHead (void)
{
  return   (win == root);
}

template<class T> bool BraidsdSearchTree<T>::isEmpty ()
{
  return   (root == root->next() );
}

template<class Т> Т BraidedSearchTree<T>::find (T val)
{
  BraidedNode<T> *n = root->rchild();
  while (n) {
    int result = (*cmp) (val, n->val);
    if (result < 0)
      n = n->lchild();
    else if (result > 0)
	  n = n->rchild();
	else {
      win=n;
      return n->val;
    }
  }
  return NULL;
}

template<class Т> Т BraidedSearchTree<T>::findMin (void)
{
  win = root->next ();
  return win->val;
}

template<class T> T BraidedSearchTree<T>::insert(T val)
{
  int result = 1;
  BraidedNode<T> *p = root;
  BraidedNcde<T> *n = root->rchild();
  while (n) { 
    p = n;
    result = (*cmp) (val, p->val);
    if (result < 0)
      n = p->lchild();
    else if (result > 0)
      n = p->rchild();
    else
      return NULL;
  }
  win = new BraidedNode<T>(val);
  if (result < 0) {
    p->_lchild = win;
    p->prev()->Node::insert(win);
  } else {
    p->_rchild = win;
    p->Node::insert(win);
  }
  return val;
}

template<class T> void BraidedSearchTree<T>::remove(void)
{
  if (win != root)
    _remove(win->val, root->_rchild);
}

template<class T>
void BraidedSearchTree<T>::_remove(T val, TreeNode<T>* &n)
{
  int result = (*cmp) (val, n->val);
  if (result < 0)
    _remove(val, n->_lchild);
  else if (result > 0)
    _remove(val, n->_rchild);
  else {                         // случай 1
    if (n->_lchild == NULL) {
      BraidedNode<T> *old = (BraidedNode<T>*)n;
      if (win == old)
        win = old->prev();
      n = old->rchild();
      old->Node::remove();
      delete old;
    }
    else if (n->_rchild == NULL) { // случай 2
      BraidedNode<T> *old = (BraidedNode<T>*)n;
      if (win == old)
        win = old->prev();
      n = old->lchild();
      old->Node::remove();
      delete old;
    }
    else  {                       // случай 3
      BraidedNode<T> *m = ( (BraidedNode<T>*)n)->next();
      n->val = m->val;
      _remove(m->val, n->_rchild);
    }
  }
}

template<class T> T BraidedSearchTree<T>::removeMin(void)
{
  Т val = root->next()->val;
  if (root != root->next() )
    _remove(val, root->_rchild);
  return val;
}


#endif  // TREE_NODE_CLASS