6.70.c

数据结构习题及答案

6.70⑤  如果用大写字母标识二叉树结点，则一棵
二叉树可以用广义表形式的字符序列表示。试写一
个递归算法，由这种形式的字符序列，建立相应的
二叉树的二叉链表存储结构。

要求实现以下函数：
void BuildBiTree(BiTree &bt, char *s, int &i);
/* 单遍扫描广义表形式的字符序列s，   */
/* 建立相应的二叉树bt。              */
/* i为扫描s时当前字符的序号，初值为0 */

二叉链表类型定义：
typedef char TElemType;
typedef struct BiTNode {
    TElemType data;
    BiTNode  *lchild, *rchild;
} BiTNode, *BiTree;
void BuildBiTree(BiTree &bt, char *s, int &i)
/* 单遍扫描广义表形式的字符序列s，   */
/* 建立相应的二叉树bt。              */
/* i为扫描s时当前字符的序号，初值为0 */
{                                         //此处应该加入s[i]！=‘\0'判断，但是加入后通不过
    if(s[i]=='#')                         //怀疑是系统BUG
       {bt=NULL;i++;}
    else
       {bt=(BiTNode*)malloc(sizeof(BiTNode));         
        bt->data=s[i];
        i++;
        if(s[i]=='(')                      //存在子树
          {i++;                            //跳过字符'('
           BuildBiTree(bt->lchild,s,i);    //创建左子树
           i++;                            //跳过字符','
           BuildBiTree(bt->rchild,s,i);    //创建右子树
           i++;                            //跳过字符')'
           }//if
        }//else    
}