括号表示法,实现构建二叉树,该如何处理

括号表示法,实现构建二叉树
C/C++ code
表示方法:a( b(c,d), e(f,g) )

这是颗完全二叉树

b(c,d)是左子树

e(f,g)是右子树

a是根节点

写一个算法:可以这种表示方法来 构建二叉树。

struct BiTNood
{

char c;
BiTNode* left;
BiTNode* right;
};

void CreateBiTree(char s[], int len, BiTNood* & p)
{
//实现之 
}




------解决方案--------------------
C/C++ code

struct BiTNode
{
char c;
BiTNode* left;
BiTNode* right;
};

// 起始点是一个括号的内部
// 寻找分隔左右子树的逗号,条件是左子树开始,括号要匹配
int  FindComma( char s[], int len ) {
    int  match = 0;
    for( int i = 1; i < len; ++i ) {
        if( s[i] == '(' ) ++match;
        else if( s[i] == ')' ) --match;
        else if( s[i] == ',' && match == 0 ) return i;
    }
    return -1;
}

void CreateBiTree(char s[], int len, BiTNood* & p)
{
    if( len <= 0 ) return;
    p = new BiTNode();  // p是指针类型,是按照引用传递进来的,这样改变p的值,函数外也能知晓,如果不是引用,例如CreateBiTree(char s[], int len, BiTNood* p)则不能这样做。
    p->c = s[0];
    if( len == 1 ) { p->left = p->right = NULL; }  // 这是叶节点
    else {  // 这是枝干节点
        int  commaPos = FindComma( s+2, len-2 ); // s+2是左子树开始位置,commaPos是相对于左子树的偏移
        CreateBiTree( s+2, commaPos, p->left );
        CreateBiTree( s+2+commaPos+1, len-3-commaPos-1, p->right );
    }
}