Powers7's Blog

版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
http://powers7.blogbus.com/logs/21544893.html

自己根据课本上的算法编写的二叉树的部分操作！代码如下: 

for example: abd##e##cf##g## 

#include<iostream>
using namespace std;

typedef char DataType;

/******结点类型**************/
typedef struct BitNode
{
    DataType data;
    struct BitNode *lchild,*rchild;
}BitNode,*BitTree;

BitTree BinTreeInit(BitTree BT);
BitTree BinTreeCreat(BitTree &BT);
BitTree BinTreeEmpty(BitTree BT);
BitTree PreOrderTraverse(BitTree BT);
BitTree InOrderTraverse(BitTree BT);
BitTree PostOrderTraverse(BitTree BT);
BitTree BinTreeClear(BitTree BT);
int height(BitTree BT);
int Count(BitTree BT);


BitNode *T=NULL;


int main()
{
    
    system("cls");
    cout<<"输入二叉树:"<<endl;
    BinTreeCreat(T);    
    cout<<endl;

    BinTreeEmpty(T);
    cout<<endl;

    cout<<"深度"<<endl<<height(T)<<endl;
    
    cout<<"结点的个数"<<endl<<Count(T)<<endl;

    
    cout<<"前序"<<endl;
    PreOrderTraverse(T);
    cout<<endl;
    
    cout<<"中序"<<endl;
    InOrderTraverse(T);
    cout<<endl;
    
    cout<<"后序"<<endl;
    PostOrderTraverse(T);
    cout<<endl;
    
    cout<<"删除"<<endl;
    BinTreeClear(T);
    cout<<endl;

    system("pause");
    return 0;
}

/**********二叉树初始化*****************/
BitTree BinTreeInit( BitTree BT )
{
    BT=NULL;
    return BT;
}
/***********建立一个二叉树**************/
BitTree BinTreeCreat(BitTree &BT)
{
    char ch;
    cin>>ch;
    if(ch=='#') BT=NULL;
    else
    {
        BT=(BitNode *)malloc(sizeof(BitNode));
        BT->data=ch;
        BT->lchild=BinTreeCreat(BT->lchild);
        BT->rchild=BinTreeCreat(BT->rchild);
    }
    return BT;
}
/*************检查二叉树是否为空****************/
BitTree BinTreeEmpty(BitTree BT)
{
    if(BT==NULL)
    {
        return NULL;
    }
    else
    {
        return 0;    
    }
    return BT;
}
/*************按任意一种次序输出二叉树********/

/***************前序遍历*****************/
BitTree PreOrderTraverse(BitTree BT)
{
    if(BT)
    {
        cout<<BT->data;
        PreOrderTraverse(BT->lchild);       
        PreOrderTraverse(BT->rchild);
    }
    return BT;
}
/*********中序遍历**********/
BitTree InOrderTraverse(BitTree BT)
{
    if(BT)
    {
        InOrderTraverse(BT->lchild);
        cout<<BT->data;
        InOrderTraverse(BT->rchild);
    }
    return BT;
}
/****************后序遍历*****************/
BitTree PostOrderTraverse(BitTree BT)
{
    if(BT)
    {
        InOrderTraverse(BT->lchild);
        InOrderTraverse(BT->rchild);            
        cout<<BT->data;
    }
    return BT;    
}
/***************删除二叉树*****************/
BitTree BinTreeClear(BitTree BT)
{
    if(BT)
    {
        if(BinTreeClear(BT->lchild))
        {
            if(BinTreeClear(BT->rchild))
            {
                cout<<"Deleting..."<<endl;
                free((void*)BT);
                return 0;
            }
            
        }
    }
    else
    {
        return 0;
    }
    return BT;
}
/***********************求深度***********************/
int height(BitTree BT)
{
    int hl,hr;
    if(BT==NULL)
    {
        return 0;
    }
    else
    {
        hl=height(BT->lchild);
        hr=height(BT->rchild);

        if(hl>hr)
        {
            return (hl+1);
        }
        else
        {
            return (hr+1);
        }
    }
}
/******************结点的个数********************/
int Count(BitTree BT)
{
    if(BT)
    {
        return Count(BT->lchild)+Count(BT->rchild)+1;
    }
    else
    {
        return 0;
    
    }
}