bintree.h

ALGAE是一个快速创建算法演示的框架。目前支持的算法实现语言包括java和c

// 
// Modified from code appearing in "Data Structures and Algorithm
//   Analysis in C++", by Mark Allen Weiss, 
// Copyright 1994 by Benjamin/Cummings Publishing Company
//
// 
#ifndef BINARYSEARCHTREE_H
#define BINARYSEARCHTREE_H

#include <algae/config.h>
#include <iostream>
#include <iomanip>

#include <algae/visible.h>
#include <utils/visqueue.h>
#include <utils/visptr.h>


template <class Etype>
class Binary_Search_Tree;

template <class Etype>
class Tree_Node;

template <class Etype>
int Height( Tree_Node<Etype> * T );


template <class Etype>
class Tree_Node: public Visible
{
protected:
  Etype Element;
  Tree_Node *Left;
  Tree_Node *Right;
  
  Tree_Node( Etype E = 0, Tree_Node *L = NULL,
	     Tree_Node *R = NULL )
    : Element( E ), Left( L ), Right( R ), Visible(AlgAE::Cyan)
    { }

  friend int Height<Etype>( Tree_Node<Etype> * T );

  friend class Binary_Search_Tree<Etype>;


  virtual void touchAllPointers() const
    {
      touch(Left, AlgAE::SSW);
      touch(Right, AlgAE::SSE);
    }
  virtual void writeText(std::ostream& out) const
    {
      out << setw(3) << Element;
    }
};


template <class Etype>
class Binary_Search_Tree: public Visible
{
protected:
  void Make_Empty( Tree_Node<Etype> * & T );
  void Insert( const Etype & X, Tree_Node<Etype> * & T );
  void Remove( const Etype & X, Tree_Node<Etype> * & T );
  
  Tree_Node<Etype>* Copy( const Tree_Node<Etype> * T );
  Tree_Node<Etype>* Find( const Etype & X, Tree_Node<Etype> * T ) const;
  Tree_Node<Etype>* Find_Min( Tree_Node<Etype> * T ) const;
  Tree_Node<Etype>* Find_Max( Tree_Node<Etype> * T ) const;
  
  static void preOrder ( const Tree_Node<Etype> * T );
  static void inOrder ( const Tree_Node<Etype> * T );
  static void postOrder ( const Tree_Node<Etype> * T );
  static void levelOrder ( const Tree_Node<Etype> * T );
  
  
  Tree_Node<Etype> *Root;
  Tree_Node<Etype> *Last_Find;
  
  Binary_Search_Tree( Binary_Search_Tree & Value ); // Disabled.


public:
  // Constructors.
  Binary_Search_Tree( )
    : Root( NULL ), Last_Find( NULL ), Visible(AlgAE::White) { }

  // Destructor.
  virtual ~Binary_Search_Tree( )
    { Make_Empty( Root ); Root = Last_Find = NULL; }

  // Operators.
  const Binary_Search_Tree &
    operator = ( const Binary_Search_Tree & Value );
  const Etype & operator ( ) ( ) const
    { return Last_Find->Element; }

  // Member functions.
  void Make_Empty( )
    { Make_Empty( Root ); Root = Last_Find = NULL; }

  virtual int Find( const Etype & X )
    { return int( Last_Find = Find( X, Root ) ); /*{*/ Visible::unHighlightAll();
    }
  virtual int Find_Min( )
    { return int( Last_Find = Find_Min( Root ) );  /*{*/ Visible::unHighlightAll();
    }
  virtual int Find_Max( )
    { return int( Last_Find = Find_Max( Root ) );  /*{*/ Visible::unHighlightAll();
    }
  virtual void Insert( const Etype & X )
    { Insert( X, Root );    /*{*/ Visible::unHighlightAll();
    }
  virtual void Remove( const Etype & X )
    { Remove( X, Root );  /*{*/ Visible::unHighlightAll();
    }

  void preOrder() const
    { preOrder(Root);   /*{*/ Visible::unHighlightAll();
    }
  void inOrder() const
    { inOrder(Root);    /*{*/ Visible::unHighlightAll();
    }
  void postOrder() const
    { postOrder(Root);   /*{*/ Visible::unHighlightAll();
    }

  void levelOrder() const;

  virtual void touchAllPointers() const
    {
      touch (Root, AlgAE::ESE);
    }

  virtual void writeText(std::ostream& out) const
    {
      out << "root";
    }
};



/////////////////////////////////////////////////////////////////

template <class Etype>
const Binary_Search_Tree<Etype> &
Binary_Search_Tree<Etype>::
operator = ( const Binary_Search_Tree<Etype> & Value )
{
    if( this != &Value )
    {
        Make_Empty( Root );
        Root = Copy( Value.Root );
        Last_Find = Root;
    }
    return *this;
}

template <class Etype>
Tree_Node<Etype> *
Binary_Search_Tree<Etype>::
Copy( const Tree_Node<Etype> *T )
{
    if( T != NULL )
        return new Tree_Node<Etype>
            ( T->Element, Copy( T->Left ), Copy( T->Right ) );
    else
        return NULL;
}



template <class Etype>
void
Binary_Search_Tree<Etype>::
Make_Empty( Tree_Node<Etype> * & T )
{
    if( T != NULL )
    {
        Make_Empty( T->Left );
        Make_Empty( T->Right );
        delete T;
        T = NULL;
    }
}



template <class Etype>
Tree_Node<Etype>*
Binary_Search_Tree<Etype>::
Find( const Etype & X, Tree_Node<Etype> * T ) const
{
    if( T == NULL )
        return NULL;
    else /*{*/ {T->highlight(AlgAE::Yellow); algae->FRAME("Find: Searching for key");/*}*/if( X < T->Element )
        /*{*/ {T->highlight(AlgAE::SSW); algae->FRAME("Find: go left");/*}*/return Find( X, T->Left );  /*{*/ }
    else if( X > T->Element )
        /*{*/ {T->highlight(AlgAE::SSE); algae->FRAME("Find: go right");/*}*/return Find( X, T->Right );  /*{*/ }
    else
        /*{*/ {algae->FRAME ("Found it!");/*}*/return T;      /*{*/ }}
}


template <class Etype>
Tree_Node<Etype>*
Binary_Search_Tree<Etype>::
Find_Min( Tree_Node<Etype> *T ) const
{
    if( T == NULL )
        return NULL;
    else/*{*/ {T->highlight(AlgAE::Yellow); algae->FRAME("Searching for min");/*}*/if( T->Left == NULL )
        /*{*/ {T->highlight(AlgAE::SSW); algae->FRAME("go left");/*}*/return T;          /*{*/ }
    else
        /*{*/ {T->highlight(AlgAE::SSE); algae->FRAME("go right");/*}*/return Find_Min( T->Left );  /*{*/ }}
}



template <class Etype>
Tree_Node<Etype>*
Binary_Search_Tree<Etype>::
Find_Max( Tree_Node<Etype> *T ) const
{
    if( T != NULL )
        while( T->Right != NULL )  /*{*/ {T->highlight(AlgAE::Yellow); algae->FRAME("Looking for max");
            T = T->Right;          /*{*/ }
    return T;
}



template <class Etype>
void
Binary_Search_Tree<Etype>::
Insert( const Etype & X, Tree_Node<Etype> * & T )
{
    if( T == NULL )
    {
        /*{*/ algae->FRAME("Insert new node here");/*}*/T = new Tree_Node<Etype>( X );
    /*{*/ algae->FRAME("Inserted");/*}*/}
    else /*{*/ {T->highlight(AlgAE::Yellow); algae->FRAME("Looking for insertion loc");/*}*/if( X < T->Element )
        Insert( X, T->Left );
    else /*{*/ {T->highlight(AlgAE::Yellow); algae->FRAME("Looking for insertion loc.");/*}*/if( X > T->Element )
        Insert( X, T->Right );
   /*{*/}}/*}*/ // Else X is in the tree already.  We'll do nothing.
}



template <class Etype>
void
Binary_Search_Tree<Etype>::
Remove( const Etype & X, Tree_Node<Etype> * & T )
{
    Tree_Node<Etype> *Tmp_Cell;

    if( T != NULL )
      { /*{*/ T->highlight(AlgAE::Yellow); algae->FRAME("Searching for key");
        if( X < T->Element )    // Go left.
            Remove( X, T->Left );
        else
        if( X > T->Element )    // Go right.
            Remove( X, T->Right );
        else                    // Found element to be removed.
        /*{*/ { algae->FRAME("Found key to delete");/*}*/if( T->Left != NULL && T->Right != NULL )       // Two children.
        {       // Replace with smallest in right subtree.
            Tmp_Cell = Find_Min( T->Right ); /*{*/ Tmp_Cell->setColor(AlgAE::Black); algae->FRAME("Smallest in right subtree");
            T->Element = Tmp_Cell->Element;  /*{*/ Visible::unHighlightAll(); algae->FRAME("Copied smallest: now remove redundant value");
            Remove( T->Element, T->Right );
        }
        else            // One or zero child.
        {
            Tmp_Cell = T; /*{*/ algae->FRAME("Bypass node to delete");
            if( T->Left == NULL )       // Only a right child.
                T = T->Right;
            else
            if( T->Right == NULL )      // Only a left child.
                T = T->Left;
            /*{*/ algae->FRAME("and delete the node");/*}*/delete Tmp_Cell;
          }        /*{*/ }
      }
}


template <class Etype>
void
Binary_Search_Tree<Etype>::
preOrder ( const Tree_Node<Etype> * T )
{
  if (T != 0)
    {
      cout << T->Element << " " << flush;  /*{*/ T->highlight(AlgAE::Yellow); algae->FRAME("pre-order"); T->unHighlight(); T->highlight(AlgAE::SSW);
      preOrder(T->Left);          /*{*/ T->unHighlight(AlgAE::SSW); T->highlight(AlgAE::SSE);
      preOrder(T->Right);         /*{*/ T->unHighlight(AlgAE::SSE);
    }
}

template <class Etype>
void
Binary_Search_Tree<Etype>::
inOrder ( const Tree_Node<Etype> * T )
{
  if (T != 0)
    {                             /*{*/ T->highlight(AlgAE::SSW);
      inOrder(T->Left);           /*{*/ T->unHighlight(AlgAE::SSW);
      cout << T->Element << " " << flush;  /*{*/ T->highlight(AlgAE::Yellow); algae->FRAME("in-order"); T->unHighlight(); T->highlight(AlgAE::SSE);
      inOrder(T->Right);          /*{*/ T->unHighlight(AlgAE::SSE);
    }
}

template <class Etype>
void
Binary_Search_Tree<Etype>::
postOrder ( const Tree_Node<Etype> * T )
{
  if (T != 0)
    {                       /*{*/ T->highlight(AlgAE::SSW);
      postOrder(T->Left);   /*{*/ T->unHighlight(AlgAE::SSW); T->highlight(AlgAE::SSE);
      postOrder(T->Right);  /*{*/ T->unHighlight(AlgAE::SSE);
      cout << T->Element << " " << flush; /*{*/ T->highlight(AlgAE::Yellow); algae->FRAME("post-order"); T->unHighlight();
    }
}



template <class Etype>
void
Binary_Search_Tree<Etype>::
levelOrder () const
{
/*{*/ typedef VisibleConstPointer<Tree_Node<Etype>, AlgAE::N> vNodePtr;
  VisibleQueue<vNodePtr> q (AlgAE::Blue, false);
  if (Root != 0)
    q.push(Root); /*{*/ algae->FRAME("initial");
  while (!q.empty())
    {
     const Tree_Node<Etype>* T = q.front();
     q.pop();
     cout << T->Element << " "; /*{*/ T->highlight(AlgAE::Yellow); algae->FRAME("level-order");
     if (T->Left != 0)
        q.push (T->Left);
     if (T->Right != 0)
        q.push (T->Right); /*{*/ algae->FRAME("updated queue");
    }                      /*{*/ Visible::unHighlightAll();
}


////////////////////////////////////

#endif