2 mstar212 Mstar212 于 2014.12.14 13:04 提问

利用二叉排序树可以实现集合的插入,删除和查找操作求怎么把只能输入数值转换成英文单词的查找

如何改动数值为英文单词,求大神指教
#include
#include
using namespace std;
typedef struct TreeNode//声明树的结构
{

int key;//存放关键字
struct TreeNode left;//存放左子树的指针
struct TreeNode *right;//存放右子树的指针
}treeNode;
class BiSortTree
{
public:
BiSortTree(void);
void desplayTree(void);//显示这个树
void insertTree(int key);//在树中插入一个结点
int 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 作为结束标志!): "< 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)//插入一个结点通过调用BuildTree 函数
{
    Head=buildTree(Head,key);
}

treeNode* BiSortTree::searchTree(int key)//查找一个节点调用search函数
{
    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);
    }
}

int BiSortTree::deleteTree(int key)//删除一个结点
{
    treeNode *p;
    p=NULL;
    p=search(Head,key);//通过search函数先找到关键字
   if(p==NULL)//结点为空找不到关键字
    {
        cout<<"Can't find the key";
    }
    if(p==Head)//如果为头结点则直接删除
    {
        Head=NULL;
    }
    else//否则分为叶子结点,有孩子的结点和左右孩子都有的结点讨论
    {
    treeNode* parent;
        parent=searchParent(Head,p);
        if(p->left==NULL&&p->right==NULL)//叶子节点即p的左右子树都为空
        {
            if(parent->left==p)//if(!parent)
            {
                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 ;       
            }
        }
    }
    return 1;
}
treeNode* BiSortTree::searchParent(treeNode* head,treeNode* p)//寻找父亲结点
{
    if(head->left==p||head->right==p||head==p||head==NULL)
    return head;
    else
    {
        if(p->key<head->key)
             return searchParent(head->left ,p);
        else
             return searchParent(head->right ,p);
    }
}
treeNode* BiSortTree::searchMinRight(treeNode* head)//找到右子树中最小的节点
{
    if(head->left ==NULL||head==NULL)
    {
        return head;
    }
    else
    {
        return searchMinRight(head->left);
    } 
}
void BiSortTree::desplayTree(void)//递归中序遍历输出
{
    showTree(Head);
    cout<<endl;
}
void BiSortTree::showTree(treeNode* Head)
{
    if(Head!=NULL)
    {
        showTree(Head->left ) ;
        cout<<Head->key<<' ' ;
        showTree(Head->right) ;
}
}
BiSortTree::~BiSortTree() //调用析构函数,运用递归删除所有的New结点
{
    cout<<"已经消除了一棵树!!!!"<<endl;
    destroyTree(Head);
}
void BiSortTree::destroyTree(treeNode* head ) 
{
    if(head!=NULL)
    {
        destroyTree(head->left );
        destroyTree(head->right );
        delete head;
    }
}
void print()
{
               cout<<"*************以下是对二叉排序树的基本操作*************"<<endl;
              cout<<"                  1.输出二叉树                        "<<endl;
               cout<<"                  2.插入一个节点                     "<<endl;
               cout<<"                  3.查找一个节点                     "<<endl;
               cout<<"                  4.删除一个节点                     "<<endl;
}
int main()
{
    BiSortTree tree;
    int number;
    int choiceNumber;
    char flag;
    while(1)
    {
   print() ;  
       cout<<"请选择你要进行的操作(1~4)"<<endl;
       cin>>choiceNumber;
       switch(choiceNumber)
       {         
          case 1:  
                tree.desplayTree();break;
          case 2:
                cout<<"请插入一个结点: "<<endl;
                cin>>number;
                tree.insertTree(number);
                tree.desplayTree();
                break;   
           case 3:
            cout<<"请输入你要查找的结点: "<<endl;
                cin>>number;  
                if(tree.searchTree(number)==NULL)
                {
                    cout<<"未找到所要查找的结点"<<endl;
                }
                else
                 {

                    cout<<"已找到所要查找的结点"<<endl;  
                 }
                break;
         case 4:
                cout<<"请输入你要删除的数: "<<endl; 
           cin>>number;
            tree.deleteTree(number);
            tree.desplayTree();
                break;
        default: break;
       }
       cout<<"你是否要继续(Y/N)?"<<endl;
       cin>>flag;
       if(flag=='N'||flag=='n')
       break;}
return 1;}

1个回答

caozhy
caozhy   Ds   Rxr 2014.12.14 19:14
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!