用户注册



邮箱：

密码：

用户登录


邮箱：

密码：
记住登录一个月忘记密码？

发表随想


还能输入：200字
云代码 - c++代码库

二叉排序树基本操作（初始化、查找和插入元素、删除元素、输出等）

2012-09-23 作者： 神马举报

[c++]代码库

view sourceprint?
#include<iostream.h>
#include<STRSTREAM.H>
typedef int elemtype;
struct bstnode
{
    elemtype data;
    bstnode *lchild;
    bstnode *rchild;
};
 
void initbtree ( bstnode *&bst )
{ bst=NULL;}
 
int bstreeempty ( bstnode *bst )
{ return bst==NULL;}
 
int find ( bstnode *bst,elemtype &x )
{
    if ( bst==NULL )
        return 0;
    else  if ( x==bst->data )
    {
        x=bst->data;
        return 1;
    }
    else if ( x<bst->data )
        return find ( bst->lchild,x );
    else
        return find ( bst->rchild,x );
}
 
int update ( bstnode *bst,elemtype x )
{
    if ( bst==NULL )
        return 0;
    else if ( x==bst->data )
    {
        bst->data=x;
        return 1;
    }
    else if ( x<bst->data )
        return update ( bst->lchild,x );
    else
        return update ( bst->rchild,x );
}
 
void insert ( bstnode *&bst,elemtype x )
{
    if ( bst==NULL )
    {
        bstnode *p=new bstnode;
        p->data=x;
        p->lchild=p->rchild=NULL;
        bst=p;
    }
    else if ( x<bst->data )
        insert ( bst->lchild,x );
    else
        insert ( bst->rchild,x );
}
 
int dele ( bstnode *&bst,elemtype x )
{
    bstnode *t=bst,*s=NULL;
    while ( t!=NULL )
    {
        if ( x==t->data )  break;
        else if ( x<t->data )
            { s=t; t=t->lchild;}
        else
            { s=t; t=t->lchild;}
    }
    if ( t==NULL )  return 0;
    if ( t->lchild==NULL&&t->rchild==NULL )
    {
        if ( t==bst )
            bst=NULL;
        else if ( t==s->lchild )
            s->lchild=NULL;
        else
            s->rchild=NULL;
        delete t;
    }
    else if ( t->lchild==NULL||t->rchild==NULL )
    {
        if ( bst==t )
        {
            if ( t->lchild==NULL )
                bst=t->rchild;
            else
                bst=t->lchild;
        }
        else
        {
            if ( t==s->lchild&&t->lchild!=NULL )
                s->lchild=t->lchild;
            else if ( t==s->lchild&&t->rchild!=NULL )
                s->lchild=t->rchild;
            else if ( t==s->rchild&&t->lchild!=NULL )
                s->rchild=t->lchild;
            else if ( t==s->rchild&&t->rchild!=NULL )
                s->rchild=t->rchild;
        }
        delete t;
    }
    else if ( t->lchild!=NULL&&t->rchild!=NULL )
    {
        bstnode *p=t,*q=t->lchild;
        while ( q->rchild!=NULL )
        {
            p=q;
            q=q->rchild;
        }
        t->data=q->data;
        if ( p==t ) t->lchild=q->lchild;
        else p->rchild=q->lchild;
        delete q;
    }
    return 1;
}
 
void createbstree ( bstnode *&bst,elemtype a[],int n )
{
    bst=NULL;
    for ( int i=0; i<n; i++ )
        insert ( bst,a[i] );
}
 
void inorder ( bstnode *bst )
{
    if ( bst!=NULL )
    {
        inorder ( bst->lchild );
        cout<<bst->data<<' ';
        inorder ( bst->rchild );
    }
}
 
int bstreedepth ( bstnode *bst )
{
    if ( bst==NULL )
        return 0;
    else
    {
        int dep1=bstreedepth ( bst->lchild );
        int dep2=bstreedepth ( bst->rchild );
        if ( dep1>dep2 )
            return dep1+1;
        else
            return dep2+1;
    }
}
 
int bstreecount ( bstnode *bst )
{
    if ( bst==NULL )
        return 0;
    else
        return bstreecount ( bst->lchild ) +bstreecount ( bst->rchild ) +1;
 
}
 
int bstreeleafcount ( bstnode *bst )
{
    if ( bst==NULL )
        return 0;
    else if ( bst->lchild==NULL&&bst->rchild==NULL )
        return 1;
    else return bstreeleafcount ( bst->lchild ) +bstreeleafcount ( bst->rchild );
}
 
void printbstree ( bstnode *bst )
{
    if ( bst==NULL )
        return;
    else
    {
        cout<<bst->data;
        if ( bst->lchild!=NULL||bst->rchild!=NULL )
        {
            cout<<'(';
            printbstree ( bst->lchild );
            if ( bst->rchild!=NULL )
                cout<<',';
            printbstree ( bst->rchild );
            cout<<')';
        }
    }
}
 
void clearbstree ( bstnode *&bst )
{
    if ( bst!=NULL )
    {
        clearbstree ( bst->lchild );
        clearbstree ( bst->rchild );
        delete bst;
        bst=NULL;
    }
}
 
void main()
{
    elemtype a[10]={30,50,20,70,25,54,80,23,92,40};
    bstnode *bst=NULL;
    createbstree ( bst,a,10 );
    cout<<"output bstree:"<<endl;
    printbstree ( bst );
    cout<<endl;
    cout<<"inorder list:"<<endl;
    inorder ( bst );
    cout<<endl;
    elemtype x;
    cout<<"input find is x:";
    cin>>x;
    if ( find ( bst,x ) )
        cout<<"ok!!!"<<endl;
    else
        cout<<"fail!!!"<<endl;
    insert ( bst,36 );
    dele ( bst,30 );
    dele ( bst,20 );
    cout<<"op end inorder:"<<endl;
    inorder ( bst );
    cout<<endl;
    cout<<"op end glist:"<<endl;
    printbstree ( bst );
    cout<<endl;
    clearbstree ( bst );
}


网友评论    (发表评论)

共1 条评论 1/1页

发表评论：

评论须知：

  • 1、评论每次加2分，每天上限为30；
  • 2、请文明用语，共同创建干净的技术交流环境；
  • 3、若被发现提交非法信息，评论将会被删除，并且给予扣分处理，严重者给予封号处理；
  • 4、请勿发布广告信息或其他无关评论，否则将会删除评论并扣分，严重者给予封号处理。


扫码下载

加载中，请稍后...

输入口令后可复制整站源码

加载中，请稍后...