现在的位置: 首页 > 综合 > 正文

树的括号表示法

2013年12月03日 ⁄ 综合 ⁄ 共 2124字 ⁄ 字号 评论关闭
标题: 树的括号表示法
时 限: 1000 ms
内存限制: 3000 K
总时限: 3000 ms
描述:
树的括号表示法:
先将根结点放入一对圆括号中,然后把它的子树按由左而右的顺序放入括号中,而对子树也采用同样方法处理:同层子树与它的根结点用圆括号括起来,同层子树之间用逗号隔开,最后用闭括号括起来。例如下图可写成如下形式
(a(b,c,d,e))
a
/ | | \
b c d e

现在给定一个多叉树的括号表示法,要求你创建多叉树,并按层序输出。

输入:
多叉树的括号表示法:字符串
输出: 层序输出多叉树
输入样例:
(a(b,c,d,e))
输出样例: abcde

思路:先判断输入的字符串一共有几层,如有levels层则动态初始化levels个队列。

再从第一个字符开始判断字符串中的当前字符串是属于哪一层的,若属于第i层,则插入到第i层的队列当中。

最后,依次将第1层到第levels层队列中的元素出队并输出,则完成层序输出。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef char ElemType;
/////////////////////////////队列相关/////////////////////////////////////
typedef struct _QNode
{
    ElemType key;
    struct _QNode *next;
}QNode;

typedef struct _Queue
{
    QNode *front;
    QNode *rear;
}Queue;

void InitQueue(Queue &Q)
{
    Q.front=NULL;
    Q.rear=NULL;
}//InitQueue

bool isEmpty(Queue &Q)
{
    if(Q.front==NULL)
    return true;
    return false;
}//isEmpty

void EnQueue(Queue &Q, ElemType e)
{
    QNode *s=(QNode*)malloc(sizeof(QNode));
    s->key=e;
    s->next=NULL;
    if(isEmpty(Q))
    {
        Q.front=s;
        Q.rear=s;
        return;
    }
    else
    {
        Q.rear->next=s;
        Q.rear=s;
    }
}//EnQueue

bool DeQueue(Queue &Q,ElemType &e)
{
    if(isEmpty(Q))
    return false;
    else
    {
        QNode *node=Q.front;
        e=node->key;
        Q.front=Q.front->next;
        if(Q.front==NULL)
        {
            Q.rear=NULL;
        }
        free(node);
    }
    return true;
}//DeQueue

void DestroyQueue(Queue &Q)
{
    ElemType temp;
    while(DeQueue(Q,temp)){}
}//DestroyQueue
////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//判断输入的字符串共有几层
int Levels(char *&str)
{
    int levels=0,i;
    for(i=0;i<strlen(str);i++)
    {
        if(str[i]=='(')
           levels++;
    }
    return levels;
}

//判断当前的字符e属于哪一层
int Inlevel(char *&str,ElemType e)
{
    int i=0,left=0,right=0;
    ElemType c;
    c=str[0];
    while(c!=e)
    {
        c=str[i];
        i++;
        if(c=='(') left++;
        if(c==')') right++;
     }
     return left-right;
}

int main()
{
    char *str=(char*)malloc(sizeof(char));
    scanf("%s",str);
    int levels=Levels(str);
    //动态分配levels个队列
    Queue *Q=(Queue*)malloc(sizeof(Queue)*levels);
    int i;
    for(i=0;i<levels;i++)
    {
        InitQueue(Q[i]);
    }
    for(i=0;i<strlen(str);i++)
    {
        if(str[i]!=','&&str[i]!='('&&str[i]!=')')
        {
            //当前字符属于哪个队列,就插入到哪个队列后面
            EnQueue(Q[Inlevel(str,str[i])-1],str[i]);
        }
    }

    //从第一层的队列依次出队并输出,即为层序输出
    for(i=0;i<levels;i++)
    {
        ElemType temp;
        while(!isEmpty(Q[i]))
        {
            DeQueue(Q[i],temp);
            printf("%c",temp);
        }
    }
    printf("\n");

    //销毁所有队列,可没有,但为了程序的健壮性最好有
    for(i=0;i<levels;i++)
    {
        DestroyQueue(Q[i]);
    }
    return 0;
}

抱歉!评论已关闭.