括号表示法,实现构建二叉树,该如何处理
括号表示法,实现构建二叉树
------解决方案--------------------
- 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 ); } }