二叉探索ツリーの非再帰C++実装
18054 ワード
ヘッダファイル:
実装ファイル:
テストファイル:
/*****************************************************************************
* student.h
*
* A student class including comparison operators.
*
* Zhang Ming, 2009-10
*****************************************************************************/
#ifndef STUDENT_H
#define STUDENT_H
#include <iostream>
#include <string>
using namespace std;
namespace itlab
{
class Student
{
public:
Student() : key(0), firstName("Ming"), lastName("Zhang")
{ }
Student( int number, const string &name1="Ming",
const string &name2="Zhang" )
{
key = number;
firstName = name1;
lastName = name2;
}
~Student()
{ }
inline void operator=( const Student &stu )
{
key = stu.key;
firstName = stu.firstName;
lastName = stu.lastName;
}
inline bool operator<( const Student &stu )
{ return key < stu.key; }
inline bool operator>( const Student &stu )
{ return key > stu.key; }
inline bool operator==( const Student &stu )
{ return key == stu.key; }
friend istream& operator>>( istream &in, Student &stu )
{
in >> stu.key >> stu.lastName >> stu.firstName;
return in;
}
friend ostream& operator<<( ostream &out, Student &stu )
{
out << stu.key << "\t"
<< stu.lastName << " " << stu.firstName << endl;
return out;
}
int key;
private:
string firstName;
string lastName;
};
// class Student
}
// namespace itlab
#endif
// STUDENT_H
/*****************************************************************************
* bstree.h
*
* Binary Search Tree
*
* This class provides "traversal(preorder,inorder or postorder), "search",
* "insert" and "remove" operations for Binary Search Tree.
*
* All of the algorithms are implemented by the nonrecursion method.
*
* Zhang Ming, 20010-07
*****************************************************************************/
#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H
#include <iostream>
#include <stack.h>
using namespace std;
namespace itlab
{
/**
* Node in Binary Search Tree
*/
template <typename Object>
struct BSNode
{
Object data;
BSNode<Object> *left,
*right;
BSNode() : left(NULL), right(NULL)
{ }
BSNode( const Object &x, BSNode<Object> *lp=NULL, BSNode<Object> *rp=NULL )
{ data = x; left = lp; right = rp; }
bool operator<( BSNode<Object> &x )
{ return data < x.data; }
bool operator>( BSNode<Object> &x )
{ return data > x.data; }
bool operator==( BSNode<Object> &x )
{ return data == x.data; }
};
// struct BSNode
template <typename Object, typename Key>
class BSTree
{
public:
BSTree();
~BSTree();
// BSTree( const BSTree &rhs );
// BSTree & operator=( const BSTree &rhs );
bool isEmpty();
void makeEmpty();
void preTraverse();
void inTraverse();
void postTraverse();
bool insert( const Object &x );
bool remove( Key k );
BSNode<Object>* search( Key k );
Object minItem();
Object maxItem();
private:
BSNode<Object> *root;
void preTravNonrecursion( BSNode<Object> *t );
void inTravNonrecursion( BSNode<Object> *t );
void postTravNonrecursion( BSNode<Object> *t );
void destroy( BSNode<Object> *&r );
bool insert( BSNode<Object> *&r, const Object &x );
bool remove( BSNode<Object> *&r, Key k );
BSNode<Object>* search( BSNode<Object> *r, Key k );
BSNode<Object>* minItem( BSNode<Object> *r );
BSNode<Object>* maxItem( BSNode<Object> *r );
void visit( BSNode<Object> *p );
};
// class BSTree
#include <bstree-impl.h>
}
// namespace itlab
#endif
// BINARY_SEARCH_TREE_H
実装ファイル:
/*****************************************************************************
* bstree-impl.h
*
* Implementation for binary search rree.
*
* Zhang Ming, 2010-07
*****************************************************************************/
/**
* constructors and destructor
*/
template <typename Object, typename Key>
BSTree<Object, Key>::BSTree() : root(NULL)
{ }
template <typename Object, typename Key>
BSTree<Object, Key>::~BSTree()
{
destroy(root);
}
/**
* If the tree is empty, return true.
*/
template <typename Object, typename Key>
inline bool BSTree<Object, Key>::isEmpty()
{
return ( root == NULL );
}
/**
* Make the tree empty.
*/
template <typename Object, typename Key>
inline void BSTree<Object, Key>::makeEmpty()
{
destroy( root );
}
/**
* preorder traversal
*/
template <typename Object, typename Key>
inline void BSTree<Object, Key>::preTraverse()
{
preTravNonrecursion( root );
}
/**
* inorder traversal
*/
template <typename Object, typename Key>
inline void BSTree<Object, Key>::inTraverse()
{
inTravNonrecursion( root );
}
/**
* postorder traversal
*/
template <typename Object, typename Key>
inline void BSTree<Object, Key>::postTraverse()
{
postTravNonrecursion( root );
}
/**
* Insert a new element x in the tree.
* If "x" isn't existent, return "true", else return "false".
*/
template <typename Object, typename Key>
inline bool BSTree<Object, Key>::insert( const Object &x )
{
return insert( root, x );
}
/**
* Delete the element x, which key is "k", in the tree.
* If such key is existent, copy the deleted element to "x",
* and return "true"; else return "false".
*/
template <typename Object, typename Key>
inline bool BSTree<Object, Key>::remove( Key k )
{
return remove( root, k );
}
/**
* Finding an element with key value of "k" in the tree.
*/
template <typename Object, typename Key>
inline BSNode<Object>* BSTree<Object, Key>::search( Key k )
{
return search( root, k );
}
/**
* Return smallest item in the tree.
*/
template <typename Object, typename Key>
Object BSTree<Object, Key>::minItem()
{
return minItem(root)->data;
}
/**
* Return largest item in the tree.
*/
template <typename Object, typename Key>
Object BSTree<Object, Key>::maxItem()
{
return maxItem(root)->data;
}
/**
* Destroy the tree.
*/
template <typename Object, typename Key>
void BSTree<Object, Key>::destroy( BSNode<Object> *&r )
{
if( r != NULL )
{
destroy( r->left );
destroy( r->right );
delete r;
}
r = NULL;
}
/**
* Preorder traversa the tree by nonrecursion method.
*/
template <typename Object, typename Key>
void BSTree<Object, Key>::preTravNonrecursion( BSNode<Object> *t )
{
Stack< BSNode<Object>* > s;
while( (t != NULL) || !s.isEmpty() )
{
if( t != NULL )
{
visit( t );
s.push( t );
t = t->left;
}
else
{
s.getTop( t );
s.pop();
t = t->right;
}
}
}
/**
* Inorder traversa the tree by nonrecursion method.
*/
template <typename Object, typename Key>
void BSTree<Object, Key>::inTravNonrecursion( BSNode<Object> *t )
{
Stack< BSNode<Object>* > s;
while( (t != NULL) || !s.isEmpty() )
{
if( t != NULL )
{
s.push( t );
t = t->left;
}
else
{
s.getTop( t );
visit(t);
s.pop();
t = t->right;
}
}
}
/**
* Postorder traversa the tree by nonrecursion method.
*/
template <typename Object, typename Key>
void BSTree<Object, Key>::postTravNonrecursion( BSNode<Object> *t )
{
Stack< BSNode<Object>* > s;
BSNode<Object> *pre = NULL, //last traversed node
*top = NULL; //current traversed node
while( (t != NULL) || !s.isEmpty() )
{
if( t != NULL )
{
s.push( t );
t = t->left;
}
else
{
s.getTop( top );
if( top->right != NULL && top->right != pre )
t = top->right;
else
{
visit( top );
pre = top;
s.pop();
}
}
}
}
/**
* Insert elemetn "x" into the tree "r".
*/
template <typename Object, typename Key>
bool BSTree<Object, Key>::insert( BSNode<Object> *&r, const Object &x )
{
BSNode<Object> *cur = r,
*par = NULL;
while( cur != NULL )
{
if( cur->data == x )
break;
else
{
par = cur;
if( cur->data < x )
cur = cur->right;
else if( cur->data > x )
cur = cur->left;
}
}
if( cur != NULL )
return false;
else
{
BSNode<Object> *tmp = new BSNode<Object>( x, NULL, NULL );
if( par == NULL )
r = tmp;
else
{
if( par->data < x )
par->right = tmp;
else
par->left = tmp;
}
return true;
}
}
/**
* Remove elemetn with key "k" from the tree "r".
*/
template <typename Object, typename Key>
bool BSTree<Object, Key>::remove( BSNode<Object> *&r, Key k )
{
if( r == NULL )
return false;
if( k < r->data.key )
return remove( r->left, k );
else if( r->data.key < k )
return remove( r->right, k );
else if( r->left != NULL && r->right != NULL )
{
r->data = minItem( r->right )->data;
return remove( r->right, r->data.key );
}
else
{
BSNode<Object> *oldNode = r;
r = ( r->left != NULL ) ? r->left : r->right;
delete oldNode;
return true;
}
}
/**
* Remove elemetn with key "k" from the tree "r".
*/
template <typename Object, typename Key>
BSNode<Object>* BSTree<Object, Key>::search( BSNode<Object> *r, Key k )
{
while( r != NULL )
if( k < r->data.key )
r = r->left;
else if( k > r->data.key )
r = r->right;
else
return r;
return NULL;
}
/**
* Find the smallest element in the tree "r".
*/
template <typename Object, typename Key>
BSNode<Object>* BSTree<Object, Key>::minItem( BSNode<Object> *r )
{
if( r == NULL )
return NULL;
while( r->left != NULL )
r = r->left;
return r;
}
/**
* Find the maximum element in the tree "r".
*/
template <typename Object, typename Key>
BSNode<Object>* BSTree<Object, Key>::maxItem( BSNode<Object> *r )
{
if( r == NULL )
return NULL;
while( r->right != NULL )
r = r->right;
return r;
}
/**
* Visit the item pointed by "p".
*/
template <typename Object, typename Key>
void BSTree<Object, Key>::visit( BSNode<Object> *p )
{
cout << p->data;
}
テストファイル:
/*****************************************************************************
* bstree_test.cpp
*
* Binary search tree class testing.
*
* Zhang Ming, 2010-07
*****************************************************************************/
#include <iostream>
#include <student.h>
#include <bstree.h>
using namespace std;
using namespace itlab;
int main()
{
const int N = 8,
M = 4;
int x[N] = { 3, 1, 2, 7, 5, 8, 4, 6 };
int y[N] = { 3, 2, 5, 7, 7, 9, 5, 0 };
int z[M] = { 3, 2, 1, 7 };
Student stu;
BSNode<Student> *pNode = NULL;
BSTree<Student, int> stuTree;
for( int i=0; i<N; ++i )
{
stu.key = x[i];
if( stuTree.insert( stu ) )
cout << "Insert " << x[i] << " success." << endl;
else
cout << "Insert failing." << endl;
}
cout << endl;
cout << "Preorder Travesal: " << endl;
stuTree.preTraverse();
cout << endl << "Inorder Travesal: " << endl;
stuTree.inTraverse();
cout << endl << "Postorder Travesal: " << endl;
stuTree.postTraverse();
cout << endl;
for( int i=0; i<N; ++i )
{
if( stuTree.remove( y[i] ) )
{
cout << "Remove " << y[i] <<" sucess. Preorder Travesal: "<< endl;
// stuTree.preTraverse();
stuTree.inTraverse();
// stuTree.postTraverse();
}
else
cout << "No such item (key=" << y[i] << ") in the tree!" << endl;
}
cout << endl;
for( int i=0; i<M; ++i)
{
pNode = stuTree.search( z[i] );
if( pNode )
cout << "Finding the element: " << pNode->data;
else
cout << "No such item (key=" << z[i] << ") in the tree!" << endl;
}
cout << endl;
stuTree.makeEmpty();
if( stuTree.isEmpty() )
cout << "The tree is empty." << endl;
else
cerr << "Making tree empty failing!" << endl;
cout << endl;
return 0;
}