以前看《数据结构与算法--c++版》，写的一个二叉搜索树，贴在这，留做纪念！
#include <queue>
#include <stack>
#include <istream>
using namespace std;
#ifndef BINARY_SEARCH_TREE
#define BINARY_SEARCH_TREE
/**//**堆栈*/
template<class T> class Stack : public stack<T>
{
public:
T pop()
{
T temp = stack<T>::top();
stack<T>::pop();
return temp;
}
};
/**//***
队列
*/
template<class T> class Queue : public queue<T>
{
public:
T dequeue()
{
T temp = queue<T>::front();
queue<T>::pop();
return temp;
}
void enqueue(const T& el )
{
queue<T>::push( el );
}
};
/**//**
二叉树节点
*/
template<class T> class BSTNode
{
public:
BSTNode()
{
left_ = right_ = 0;
}
BSTNode( const T& el, BSTNode<T>* l = 0, BSTNode<T>* r = 0 )
{
value_ = el;
left_ = l;
right_ = r;
}
T Value()
{
return value_;
}
void SetValue( const T& vl )
{
value_ = vl;
}
BSTNode<T>* Left()
{
return left_;
}
void SetLeft( BSTNode<T>* left )
{
left_ = left;
}
BSTNode<T>* Right()
{
return right_;
}
void SetRight( BSTNode<T>* right )
{
right_ = right;
}
private:
T value_;
BSTNode<T>* left_;
BSTNode<T>* right_;
};
/**//**
搜索二叉树的定义
*/
template<class T> class BST
{
private:
//根节点
BSTNode<T>* root_;
//节点数量
int node_count_;
public:
/**///////////////////////////////////////////////////////////////////////////
//构造析构
BST(){
root_ = 0;
node_count_ = 0;
}
virtual ~BST()
{
Clear();
}
/**///////////////////////////////////////////////////////////////////////////
//公有方法
template<typename U> friend ostream& operator << ( ostream& os, const BSTNode<U>* root );
void Clear()
{
Clear( root_);
root_ = 0;
}
/**//***
当前搜索树是否为空
*/
bool isEmpty() const
{
return root_ == 0;
}
/**//**
获取节点总数量
*/
int GetNodeCount() const
{
return node_count_;
}
/**//**
获取树的根节点
*/
const BSTNode<T>* GetRoot() const
{
return root_;
}
//前序遍历
void PreOrder()
{
RecursionPreOrder(root_);
}
//中序遍历
void InOrder()
{
RecursionInOrder(root_);
}
//后序遍历
void PostOrder()
{
RecursionPostOrder(root_);
}
//morris中序遍历
void MorrisInOrder()
{
BSTNode<T>* cur_node = root_;
while ( cur_node != NULL )
{
//没有左节点，访问节点，并转向右节点
if ( cur_node->Left() == NULL )
{
VisitNode(cur_node);
cur_node = cur_node->Right();
}
else
{
//退化树
BSTNode<T>* temp = cur_node->Left();
while ( temp ->Right() != NULL && temp->Right() != cur_node )
{
//找到左节点的最右节点
temp = temp->Right();
}
if ( temp->Right() == 0 )
{
//给该节点成为它的左子节点最右侧节点的右子节点
temp->SetRight( cur_node );
//cur_node.left现在为根节点，原根节点已经成为temp的右子节点。
cur_node = cur_node->Left();
}
else
{
//退化完成,访问刚转换完的节点，即原根节点的左节点
VisitNode(cur_node);
//恢复树
temp->SetRight( 0 );
cur_node = cur_node->Right();
}
}
}
}
//前序遍历--非递归实现
void NonRecursionPreOrder()
{
//使用堆栈
BSTNode<T>* cur_node = root_;
Stack<BSTNode<T>*> nodeStack;
nodeStack.push( root_ );
while ( nodeStack.size() != 0 || cur_node != NULL )
{
while ( cur_node != NULL )
{
//访问当前节点
VisitNode( cur_node );
//压左子节点
cur_node = cur_node->Left();
if ( cur_node != NULL )
{
nodeStack.push( cur_node );
}
}
if( nodeStack.size() != 0 )
{
cur_node = nodeStack.pop();
cur_node = cur_node->Right();
}
}
}
//中序遍历--非递归实现
void NonRecursionInOrder()
{
//使用堆栈
BSTNode<T>* cur_node = root_;
Stack<BSTNode<T>*> nodeStack;
nodeStack.push( root_ );
while ( nodeStack.size() != 0 )
{
while ( cur_node != NULL )
{
//压左子节点
cur_node = cur_node->Left();
if ( cur_node != NULL )
{
nodeStack.push( cur_node );
}
}
cur_node = nodeStack.pop();
//访问当前节点
VisitNode( cur_node );
cur_node = cur_node->Right();
if ( cur_node != NULL )
{
nodeStack.push( cur_node );
}
}
}
//后序遍历--非递归实现
void NonRecursionPostOrder()
{
BSTNode<T>* cur_node = root_;
BSTNode<T>* prev_node = NULL;
Stack<BSTNode<T>*> nodeStack;
nodeStack.push( root_ );
while ( nodeStack.size() != 0 )
{
//左边节点压栈
while ( cur_node != NULL )
{
cur_node = cur_node->Left();
if ( cur_node != 0 )
{
nodeStack.push( cur_node );
}
}
//左边的栈保存完毕
//开始退栈
cur_node = nodeStack.pop();
//左子树在上面的循环已经处理结束
//如果没有右子树，则访问当前节点
//如果右子树已经访问过，则访问当前节点。
if ( cur_node->Right() != 0 &&
prev_node != cur_node->Right() )
{
//再次保存当前节点
nodeStack.push( cur_node );
nodeStack.push( cur_node->Right() );
}
else
{
prev_node = cur_node;
VisitNode( cur_node );
}
cur_node = cur_node->Right();
}
}
/**//**
搜索
*/
BSTNode<T>* Search(const T& el )
{
BSTNode<T>* search_node = root_;
while ( search_node != 0 )
{
if ( search_node->Value() == el )
{
return search_node;
}
if ( el > search_node->Value() )
{
search_node = search_node->Right();
}
else
{
search_node = search_node->Left();
}
}
return NULL;
}
/**//**
插入结点，使用该函数来构造一棵树
*/
void Insert( const T& el )
{
BSTNode<T>* new_node = new BSTNode<T>( el );
++node_count_;
//空树，构造根节点
if ( root_ == NULL )
{
root_ = new_node;
return;
}
BSTNode<T>* cur_node = root_;
BSTNode<T>* prev_node = NULL;
//查找待插入的位置
while( cur_node != NULL )
{
prev_node = cur_node;
if( el > cur_node->Value() )
{
cur_node = cur_node->Right();
}
else
{
cur_node = cur_node->Left();
}
}
//插入新构造的节点
if( prev_node->Value() > el )
{
prev_node->SetLeft( new_node );
}
else
{
prev_node->SetRight( new_node );
}
}
//合并删除，增加树的高度
void DeleteByMerging( BSTNode<T>* node )
{
}
//复制删除，高度不变，但多次增删会仍会造成树不平衡
void DeleteByCopying( BSTNode<T>* node )
{
}
//根据排序数组构造一颗平衡树
void Balance( T[], int first, int last )
{
}
//DSW平衡算法
void BalanceByDSW()
{
}
//退化，将树退化为链表，利用左旋转
void Degenerate2ListUsingLeftRotate()
{
BSTNode<T>* temp_node = root_;
BSTNode<T>* gr = NULL;
while( temp_node != NULL )
{
if( temp_node->Left() != NULL )
{
//需要保存left，因为左旋转后
//temp_node的左节点已经发生变化，变化为其左节点的右节点了
BSTNode<T>* cur_node = temp_node->Left();
RotateLeft( gr, temp_node, temp_node->Left() );
temp_node = cur_node;
}
else
{
gr = temp_node;
temp_node = temp_node->Right();
}
}
}
//退化，将树退化为链表，利用右旋转
void Degenerate2ListUsingRightRotate()
{
BSTNode<T>* temp_node = root_;
BSTNode<T>* gr = NULL;
while( temp_node != NULL )
{
if( temp_node->Right() != NULL )
{
//需要保存left，因为左旋转后
//temp_node的左节点已经发生变化，变化为其左节点的右节点了
BSTNode<T>* cur_node = temp_node->Right();
RotateRight( gr, temp_node, temp_node->Right() );
temp_node = cur_node;
}
else
{
gr = temp_node;
temp_node = temp_node->Left();
}
}
}
void PrintRight()
{
BSTNode<T>* temp_node = root_;
while( temp_node != NULL )
{
VisitNode( temp_node );
temp_node = temp_node->Right();
}
}
void PrintLeft()
{
BSTNode<T>* temp_node = root_;
while( temp_node != NULL )
{
VisitNode( temp_node );
temp_node = temp_node->Left();
}
}
/**////////////////////////////////////////////////////////////////////////
//保护方法，提供供子类重写的函数，并给出了默认实现
protected:
//默认访问节点的实现
virtual void VisitNode( BSTNode<T>* p )
{
cout << p->Value() << " ";
}
/**///////////////////////////////////////////////////////////////////////////
//私有方法
private:
//左旋转
void RotateLeft( BSTNode<T>* gr, BSTNode<T>* par, BSTNode<T>* cur )
{
// null point;
if( par == 0 || cur == 0 )
{
return;
}
//relationship is not right;
if ( par->Left() != cur )
{
return;
}
if( gr != NULL && gr->Right() != par )
{
return;
}
if( gr != NULL )
{
gr->SetRight( cur );
}
else
{
root_ = cur;
}
par->SetLeft( cur->Right() );
cur->SetRight( par );
}
//和左旋转完全对称
void RotateRight( BSTNode<T>* gr,BSTNode<T>* par, BSTNode<T>* cur )
{
// null point;
if( par == 0 || cur == 0 )
{
return;
}
//relationship is not right;
if ( par->Right() != cur )
{
return;
}
if( gr != NULL && gr->Left() != par )
{
return;
}
if( gr != NULL )
{
gr->SetLeft( cur );
}
else
{
root_ = cur;
}
par->SetRight( cur->Left() );
cur->SetLeft( par );
}
//释放内存，删除所有节点
void Clear( BSTNode<T>* root )
{
//递归删除，后续遍历
BSTNode<T>* p = root;
if ( NULL != p )
{
Clear( p->Left() );
Clear( p->Right() );
delete p;
}
}
//前序遍历
void RecursionPreOrder( BSTNode<T>* p )
{
if ( NULL != p )
{
VisitNode(p);
RecursionPreOrder( p->Left() );
RecursionPreOrder( p->Right() );
}
}
//后序遍历
void RecursionPostOrder(BSTNode<T>* p)
{
if ( NULL != p )
{
RecursionPostOrder( p->Left() );
RecursionPostOrder( p->Right() );
VisitNode(p);
}
}
//中序遍历
void RecursionInOrder(BSTNode<T>* p)
{
if ( NULL != p )
{
RecursionInOrder( p->Left() );
VisitNode(p);
RecursionInOrder( p->Right() );
}
}
};
#endif
int main()
{
cout << "Hello This is C++ Program Using Code::Block!" << "\r\n";
cout << "this is binary search tree test program" << "\r\n";
BST<int> bst_tree;
bst_tree.Insert( 10 );
bst_tree.Insert( 5 );
bst_tree.Insert( 20 );
bst_tree.Insert( 3 );
bst_tree.Insert( 7 );
cout << bst_tree.GetNodeCount() << "\r\n";
/**//*const BSTNode<int>* bst_root = bst_tree.GetRoot();
BSTNode<int>* temp = const_cast<BSTNode<int>*>(bst_root);
while( temp != NULL )
{
cout << temp->Value() << " ";
if( temp->Value() == 5 )
{
temp = temp->Right();
}
else
{
temp = temp->Left();
}
}*/
cout << "递归前序遍历：";
bst_tree.PreOrder();
cout << "\r\n";
cout << "递归中序遍历：";
bst_tree.InOrder();
cout << "\r\n";
cout << "递归后序遍历：";
bst_tree.PostOrder();
cout << "\r\n";
cout << "Morris中序遍历：";
bst_tree.MorrisInOrder();
cout << "\r\n";
cout << "非递归前序遍历：";
bst_tree.NonRecursionPreOrder();
cout << "\r\n";
cout << "非递归中序遍历：";
bst_tree.NonRecursionInOrder();
cout << "\r\n";
cout << "非递归后序遍历：";
bst_tree.NonRecursionPostOrder();
cout << "\r\n";
cout << "将树退化为链表(左旋转)：";
bst_tree.Degenerate2ListUsingLeftRotate();
bst_tree.PrintRight();
cout << "\r\n";
cout << "将树退化为链表(右旋转)：";
bst_tree.Degenerate2ListUsingRightRotate();
bst_tree.PrintLeft();
cout << endl;
return 0;
}