二叉树操作算法（二叉树初始化、深度、建立、输出等）

[c++]代码库
#include<iostream.h>
#include<STRSTREAM.H>
typedef char elemtype;
struct btreenode
{
    elemtype data;
    btreenode *lchild;
    btreenode *rchild;
};
void initbtree ( btreenode *&bt )
{ bt=NULL;}
 
void precrttree ( btreenode *&bt )
{
    char ch;
    cin>>ch;
    if ( ch=='#' )
        bt=NULL;
    else
    {
        bt=new btreenode;
        bt->data=ch;
        precrttree ( bt->lchild );
        precrttree ( bt->rchild );
    }
}
 
void crtbtree ( btreenode *&bt,char *a )
{
    char ch;
    btreenode *s[20];
    int top=-1;
    bt=NULL;
    btreenode *p;
    int k;
    istrstream ins ( a );
    ins>>ch;
    while ( ch!='@' )
    {
        switch ( ch )
        {
        case'(':
            top++;
            s[top]=p;
            k=1;
            break;
        case')':
            top--;
            break;
        case',':
            k=2;
            break;
        default:
            p=new btreenode;
            p->data=ch;
            p->lchild=p->rchild=NULL;
            if ( bt==NULL )
                bt=p;
            else
            {
                if ( k==1 )  s[top]->lchild=p;
                else s[top]->rchild=p;
            }
        }
        ins>>ch;
    }
}
 
int btreeempty ( btreenode *bt )
{ return bt==NULL;}
 
void preorder ( btreenode *bt )
{
    if ( bt!=NULL )
    {
        cout<<bt->data<<' ';
        preorder ( bt->lchild );
        preorder ( bt->rchild );
    }
}
 
void inorder ( btreenode *bt )
{
    if ( bt!=NULL )
    {
        inorder ( bt->lchild );
        cout<<bt->data<<' ';
        inorder ( bt->rchild );
    }
}
 
void postorder ( btreenode *bt )
{
    if ( bt!=NULL )
    {
        postorder ( bt->lchild );
        postorder ( bt->rchild );
        cout<<bt->data<<' ';
    }
}
 
void levorder ( btreenode *bt )
{
    btreenode *q[30];
    int front=0,rear=0;
    btreenode *p;
    if ( bt!=NULL )
    {
        rear= ( rear+1 ) %30;
        q[rear]=bt;
    }
    while ( front!=rear )
    {
        front= ( front+1 ) %30;
        p=q[front];
        cout<<p->data<<' ';
        if ( p->lchild!=NULL )
        {
            rear= ( rear+1 ) %30;
            q[rear]=p->lchild;
        }
        if ( p->rchild!=NULL )
        {
            rear= ( rear+1 ) %30;
            q[rear]=p->rchild;
        }
    }
}
 
int btreedepth ( btreenode *bt )
{
    if ( bt==NULL )
        return 0;
    else
    {
        int dep1=btreedepth ( bt->lchild );
        int dep2=btreedepth ( bt->rchild );
        if ( dep1>dep2 )
            return dep1+1;
        else
            return dep2+1;
    }
}
 
int btreecount ( btreenode *bt )
{
    if ( bt==NULL )
        return 0;
    else
        return btreecount ( bt->lchild ) +btreecount ( bt->rchild ) +1;
 
}
 
int btreeleafcount ( btreenode *bt )
{
    if ( bt==NULL )
        return 0;
    else if ( bt->lchild==NULL&&bt->rchild==NULL )
        return 1;
    else return btreeleafcount ( bt->lchild ) +btreeleafcount ( bt->rchild );
}
 
void printbtree ( btreenode *bt )
{
    if ( bt==NULL )
        return;
    else
    {
        cout<<bt->data;
        if ( bt->lchild!=NULL||bt->rchild!=NULL )
        {
            cout<<'(';
            printbtree ( bt->lchild );
            if ( bt->rchild!=NULL )
                cout<<',';
            printbtree ( bt->rchild );
            cout<<')';
        }
    }
}
 
void clearbtree ( btreenode *&bt )
{
    if ( bt!=NULL )
    {
        clearbtree ( bt->lchild );
        clearbtree ( bt->rchild );
        delete bt;
        bt=NULL;
    }
}
 
void main()
{
    btreenode *bt;
    initbtree ( bt );
    char b[50];
    int tag;
    cout<<"1.pre order create btree"<<endl;
    cout<<"2.glist create btree"<<endl;
    cout<<"input selecte 1 or 2:";
    cin>>tag;
    if ( tag==2 )
    {
        cout<<"input @ end glist:"<<endl;
        cin.getline ( b,sizeof ( b ) );
        crtbtree ( bt,b );
    }
    else
    {
        cout<<"input pretree and '#':"<<endl;
        precrttree ( bt );
    }
    printbtree ( bt );
    cout<<endl;
    cout<<"pre order:";
    preorder ( bt );
    cout<<endl;
    cout<<"in order:";
    inorder ( bt );
    cout<<endl;
    cout<<"post order:";
    postorder ( bt );
    cout<<endl;
    cout<<"level order:";
    levorder ( bt );
    cout<<endl;
    cout<<"btree depth is:";
    cout<<btreedepth ( bt ) <<endl;
    cout<<"btree node num is:";
    cout<<btreecount ( bt ) <<endl;
    cout<<"btree leaf node num is:";
    cout<<btreeleafcount ( bt ) <<endl;
    clearbtree ( bt );
}
用户注册

用户登录

发表随想

该用户最新代码

编程随想

[c++]代码库

网友评论 (发表评论)

回复评论

发表评论：

评论须知：

扫码下载

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