树(普通树)

2012/10/06

数据结构树的代码实现,代码参考数据结构使用教程(第二版):
[cpp]struct GTreeNode
{
    ElemType data;
    GTreeNode *t[k];    //k叉树
}
void CreateGTree(GTreeNode *&GT,char *a)//广义表构造普通树
{
    const int MS=10;    //定义符号常量指定栈空间的大小
    GTreeNode *s[MS];   //s数组作为存储树中结点指针的栈使用
    int d[MS];          //d数组作为储存孩子结点链接到双亲节点
    int top=-1;         //top作为两个栈的栈顶指针
    GT=NULL;            //给树根指针置空
    GTreeNode *p;       //定义p为指向树结点的指针
    int i=0;
    while(a[i])
    {
        switch(a[i])
        {
            case ‘ ‘: break;
            case ‘(‘: top++;s[top]=p;d[top]=0;break;
            case ‘)’: top–;break;
            case ‘,’: d[top]++;break;
            default:
                p=new GTreeNode;p->data=a[i];
                for(int i=0;i<k;i++) p->t[i]=NULL;
                if(GT==NULL) GT=p;
                else s[top]->t[d[top]]=p;
        }i++;
    }
}
void PreRoot(GTreeNode *GT)//先根遍历
{
    if(GT!=NULL)
    {
        cout<<GT->data<<” “;
        for(int i=0;i<k;i++)
        PreRoot(GT->t[i]);
    }
}
bool FindGTree(GTreeNode *GT,ElemType &item)//查找树
{
    if(GT==NULL) return false;
    else{
        if(GT->data==item){
        item=GT->data;return true;
        }
        for(int i=0;i<k;i++)
            if(FindGTree(GT->t[i],item)) return true;
        return false;
    }
}
void PrintGTree(GTreeNode *GT)//输出树
{
    if(GT!=NULL)
    {
        cout<<GT->data<<” “;int i;
        for(i=0;i<k;i++)
            if(GT->t[i]!=NULL) break;
        if(t<k)
        {
            cout<<“(“;PrintGTree(GT->t[0]);
            for(i=1;i<k;i++){
            cout<<“,”;PrintGTree(GT->t[i]);
            }cout<<“)”;
        }
    }
}
int GTreeDepth(GTreeNode *GT)//树的深度
{
    if(GT==NULL) return 0;
    else{
    int max=0;
    for(int i=0;i<k;i++){
    int d=GTreeDepth(GT->t[i]);
    if(d>max) max=d;
    }
    return max+1;
    }
}
void ClearGTree(GTreeNode *&GT)
{
    if(GT!=NULL){
    for(int i=0;i<k;i++) ClearGTree(GT->t[i]);
    delete GT;GT=NULL;
    }
}[/cpp]

Blogroll