急!急!求二叉排序树程序
发布网友
发布时间：2022-08-29 19:44
共1个回答
热心网友
时间：2024-10-21 19:37
//二叉排序树类的前视定义
template<class Type> class BSTree;
//二叉排序树结点类的定义
template<class Type>
class BSTreeNode
{friend class BSTree <Type>;
private:
Type data; //数据域（在此为关键字）
BSTreeNode <Type> *leftChild, *rightChild;
public:
BSTreeNode():leftChild(NULL),rightChild (NULL){};//构造函数
BSTreeNode(const Type &d) : data (d), leftChild (NULL),rightChild (NULL) {} ; //构造函数
~BSTreeNode(){}; //析构函数
};
//二叉排序树的类定义
template <class Type>
class BSTree
{
private:
BSTreeNode<Type> * root; //二叉排序树的根指针
void Insert ( const Type & x, BSTreeNode<Type> *&p );
//在p为根的二叉排序树上插入数据元素x
void Delete ( const Type & k, BSTreeNode<Type> *&p );
//在p为根的二叉排序树上删除关键字为k的结点
BSTreeNode<Type> * Min(BSTreeNode<Type> *p);
BSTreeNode<Type> * Find(const Type &k, BSTreeNode<Type> *p );
//在p为根的二叉排序树上查找关键字为k的结点
void InOrder(BSTreeNode<Type> *r);
public:
BSTree() : root (NULL) {}//构造函数
Type Find ( const Type &k ) {//查找
BSTreeNode<Type>* p=Find ( k, root );
if(p==NULL){
cout<<"There is not a node that equals "<<k<<endl;
return NULL;
}
return p->data;
}
void Insert(const Type &x) { Insert ( x, root ); } //插入
void Delete(const Type &k) { Delete ( k, root ); } //删除
void SortDisplay(){InOrder(root);cout<<endl;}
};
template <class Type>
void BSTree<Type>::
Insert(const Type &x, BSTreeNode<Type> * &p) {
//在p为根的二叉排序树插入结点的递归算法
if ( p == NULL ) //空二叉树
p = new BSTreeNode<Type>(x); //创建数据元素x的结点
else if (x<p->data )
//在左子树插入
Insert ( x, p->leftChild );
else if ( x > p->data )
//在右子树插入
Insert ( x, p->rightChild );
else //结点x已存在
{
cout << "There has node x" << endl;
}
}
template <class Type>
BSTreeNode<Type> * BSTree<Type> ::
Find (const Type &k, BSTreeNode<Type> *p) {
//在p为根的二叉排序树上进行查找的递归算法
if ( p == NULL ) return NULL; //查找失败
else if ( k<p->data )
//在左子树上递归查找
return Find (k,p->leftChild );
else if (k>p->data )
//在右子树上递归查找
return Find ( k, p->rightChild );
else return p; //相等,查找成功
}
template <class Type>
void BSTree<Type> ::
Delete(const Type &k, BSTreeNode<Type> * &p){
//在p为根的二叉排序树上删除关键字为k的结点
if ( p != NULL ){
BSTreeNode<Type> * temp;
if ( k < p->data )
Delete ( k, p->leftChild );
else if ( k > p->data )
Delete ( k, p->rightChild );
else if ( p->leftChild != NULL && p->rightChild != NULL ){
BSTreeNode<Type> * tparent=p;
temp=p->rightChild;
while(temp->leftChild!=NULL){
tparent=temp;
temp=temp->leftChild;
}
p->data = temp->data;
if(tparent==p)
Delete ( p->data,tparent->rightChild );
else Delete ( p->data,tparent->leftChild );
}
else {
temp = p;
if ( p->leftChild == NULL )
p = p->rightChild;
else if ( p->rightChild == NULL )
p = p->leftChild;
delete temp;
}
}
}
template <class Type>
void BSTree<Type>::InOrder(BSTreeNode<Type>* r){
if(r!=NULL){
InOrder(r->leftChild);
cout<<r->data<<" ";
InOrder(r->rightChild);
}
}
void main (){
BSTree<int> a;
int x;
cout<<"输入序列："<<" ";
for(int i=0;;i++){
cin>>x;
if(x==-1)break;
a.Insert(x);
}
cout<<endl;
cout<<"输出中序遍历序列应为：";
a.SortDisplay();
cout<<endl;
cout<<"输入需要删除的整数："<<" ";
int y;
cin>>y;
cout<<endl;
cout<<"查找结果是:"<<a.Find(y)<<endl;
cout<<endl;
a.Delete(y);
cout<<"输出删除后的中序遍历序列应为："<<" ";
a.SortDisplay();
}
