用c++ 实现的二叉排序树（含源代码）[1]

/*以下是用c++ 实现的二叉排序树的源代码*/


#include<iostream.h>
typedef struct treenode
{
int key;
struct treenode *left;
struct treenode *right;

}treenode;

class bisorttree
{
public:
    bisorttree(void);
void desplaytree(void);//显示这个树
void inserttree(int key);//在树中插入一个值
  deletetree(int key);//在树中删除一个值
    treenode* searchtree(int key);//在树中查找一个值
   
~bisorttree();

private:
treenode*  buildtree(treenode* head,int number);//建立一个树
treenode*  search(treenode* head ,int key);//查找
treenode* bisorttree::searchparent(treenode* head,treenode* p);//查找出p的父亲节点的指针
treenode* bisorttree::searchminright(treenode* head);//找到右子树中最小的节点

void showtree(treenode* head);//显示
    void destroytree(treenode* head);//删除

treenode *head;
   



};



/**************以下是建立一个二叉排序树****************/
bisorttree::bisorttree()
{
   cout<<"建立一棵二叉排序树,请输入你要建树的所有数(以-1 作为结束标志!): "<<endl;
   head=null;
   int number;
   cin>>number;
   while(number!=-1)
   {
   head=buildtree(head,number);
       cin>>number; 
  
   }

}
treenode* bisorttree::buildtree(treenode* head,int number)
{

treenode *p;   
p=new treenode;
    p->key=number;
p->left =p->right=null;

if(head==null)
{

    
      return p;
}
else
{
 
       if(p->key <head->key)
head->left=buildtree(head->left,number);
   else
  head->right=buildtree(head->right,number);
 
       return head;
}





}
/*****************以下是在一棵二叉排序树插入一个数***********************************/
void bisorttree::inserttree(int key)
{

head=buildtree(head,key);

}
/*****************以下是在一个二叉排序树查找一个数是否存在*************************/
treenode*  bisorttree::searchtree(int key)
{
return search(head,key);
}
treenode* bisorttree::search(treenode* head ,int key)
{ 
if(head==null)
return null;
if(head->key==key)
return head;
else
{
if(key<head->key )
return search( head->left,key);

    else
return search(head->right,key);


}

}

/************以下是在一个二叉排序树删除一个给定的值*********************************/
bisorttree::deletetree(int key)
{

treenode *p;
p=null;
    p=search(head,key);
if(p==null)
{
cout<<"don't find the key";

}
    if(p==head)
{
head=null;

}
else
{
treenode* parent;
parent=searchparent(head,p);
if(p->left==null&&p->right==null)//叶子节点
{
    if(parent->left==p)
{
parent->left=null;
}
    else
{
parent->right=null;

}
}
        else//非叶子节点
{
           if(p->right==null)//该节点没有右孩子
   {
   if(parent->left==p)
   {
     parent->left=p->left ;
   }
       else
   {
   parent->right=p->left;

   }
   }

   else//该点有左右孩子
   {
   treenode * rightminson,* secondparent;//secondparent为右子树中的最小节点的父亲
   rightminson=searchminright(p->right);
   secondparent=searchparent(p->right ,rightminson);
          
               secondparent->left=rightminson->right;
 
                              
           if(p->right==rightminson)//右子树中的最小节点的父亲为p
   {
     
        p->right=rightminson->right ;
 
   }
     
   p->key=rightminson->key ;