标题: | 树的括号表示法 |
时 限: | 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; }