213 树 - 嵌套括号表示法

主要内容

1. 树的括号表示法
2. 问题描述
3. 实现代码

1. 树的括号表示法

树的括号表示规则 （1）若树T为空树，则其括号表示为空 （2）若树T只包含一个结点，则其括号表示即为该结点本身 （3）若树T由根结点A和它的m棵子树T1,T2,...,Tm构成，则其括号表示为：A(T1的括号表示，T2的括号表示,... ,Tm的括号表示) 其中，子树的括号表示同样应该遵循以上规则. 例如，下面的树的三种表示方式： 括号表示法为： A(B(E,F),C(G(J)),D(H,I(K,L,M)))

2. 问题描述

先将根结点放入一对圆括号中，然后把它的子树按由左而右的顺序放入括号中，而对子树也采用同样方法处理：同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。 现在给定一个多叉树的括号表示法，要求你创建多叉树，并按层序序列输出。 输入 多叉树的括号表示法：字符串 输出 层序输出多叉树 样例输入 (a(b,c,d,e)) 样例输出 abcde

3. 参考代码

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
const int maxn = 1000;
int main()
{
    char ch[maxn];
    int rec[maxn];
    memset(rec,0,sizeof(rec));
    scanf("%s",ch);
    int len = strlen(ch); //读取输入的字符串的长度，不包含'\0'
    int level = 1;        //树的层数
    int maxLevel = -10000;
    for(int i = 0 ; i < len ; i++)
    {
        if(ch[i] == '(')
        {
            level++;
            continue;
        }
        else if(ch[i] == ')')
        {
            level--;
            continue;
        }
        else if(ch[i] == ',')
        {
            continue;
        }

        rec[i] = level;        //记录字符串ch中第i个字符为树的第level层
        maxLevel = max(maxLevel,level);  //记录树的最大层数
    }
//    cout << maxLevel << endl;
    for(int i = 1 ; i <= maxLevel ; i++) //按层数从低到高输出
    {
        for(int j = 0 ; j < len; j++)
        {
            if(rec[j] == i)  //如果低j个字符属于本层，则输出。
            cout << ch[j];
        }
    }
    cout << endl;

    return 0;
}