错误记录

题目来源：严蔚敏《数据结构》C语言版本习题册 6.70

【题目】6.70
如果用大写字母标识二叉树结点，则一棵二叉树可以用符合下面语法图的字符序列表示。试写一个递归算法，由这种形式的字符序列，建立相应的二叉树的二叉链表存储结构
根据广义表GList 创建二叉树BiTree（严蔚敏《数据结构》6.70） - 图1

【注意】这是我一开始犯的错误
根据以上匹配的公式得出这个测试数据：A(B(#,D(#,#)),C(E(#,F(#,#)),#)) —>这个是错的
【理解一下公式】

若二叉树为空 —>#
若二叉树存在 —> ‘字母’
- 二叉树有孩子 —> ( , )
- 没有孩子 —> `` 直接没有东西

【测试数据】A(B(#,D),C(E(#,F),#))
【思路】递归定义使用递归函数

【答案】

// @Version：最新
// @测试数据：A(B(#,D),C(E(#,F),#))
// @Time:20181005
Status CreateBiTreeByGList2(BiTree *pT) {
    char c;
    while (1) {
        c = getchar();
        if (c=='#') *pT = NULL; //空树
        else if (c>='A' && c<='Z') {
            *pT = (BiTNode *)malloc(sizeof(BiTNode)); if (!*pT) exit(OVERFLOW);
            (*pT)->data = c;
            (*pT)->lchild=(*pT)->rchild=NULL;
        } 
        else if (c=='(') {
            CreateBiTreeByGList2( &(*pT)->lchild );
            CreateBiTreeByGList2( &(*pT)->rchild );
        }
        else 
            break;
    }
    return OK;
}

【完整代码】

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#ifndef BASE
#define BASE
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int bool;
#endif
#define TElemType char //固定为char，若修改需要修改方法
typedef struct BiTNode { // 结点结构
    TElemType      data;
    struct BiTNode  *lchild, *rchild; // 左右孩子指针
}BiTNode, *BiTree;
void visit(TElemType e) {
    printf("%c", e);
}
// 先序遍历二叉树
void PreOrder(BiTree T) { // - 递归
    if (!T) return ;
    visit(T->data);
    PreOrder(T->lchild);
    PreOrder(T->rchild);
}
// 中序遍历二叉树
void InOrder(BiTree T) { // - 递归
    if (!T) return ;
    InOrder(T->lchild);
    visit(T->data);
    InOrder(T->rchild);
}
// 后序遍历二叉树
void PostOrder(BiTree T) { // - 递归
    if (!T) return ;
    PostOrder(T->lchild);
    PostOrder(T->rchild);
    visit(T->data);
}
// 6.70 由广义表形式的输入建立二叉链表
// @Version:0.0.1
// @测试数据：A(B(#,D(#,#)),C(E(#,F(#,#)),#))
// @Time:20181003
// @Desc:公式理解错误-->测试数据出错
Status CreateBiTreeByGList(BiTree *pT) {
    char c;
    BiTNode *p;
    c = getchar();
    if (c=='#') p=NULL; //空子树
    else {
        p = (BiTNode *)malloc(sizeof(BiTNode)); if (!p) exit(OVERFLOW);
        p->data=c; //赋值
        if (getchar()!='(') return ERROR; //格式错误
        if ( !CreateBiTreeByGList( &p->lchild ) ) return ERROR; //建立左子树
        if (getchar()!=',') return ERROR; //格式错误
        if ( !CreateBiTreeByGList( &p->rchild ) ) return ERROR; //建立右子树
        if (getchar()!=')') return ERROR; //格式错误
    }
    *pT = p; //把p传出去
    return TRUE;
}
// @Version：最新
// @测试数据：A(B(#,D),C(E(#,F),#))
// @Time:20181005
Status CreateBiTreeByGList2(BiTree *pT) {
    char c;
    while (1) {
        c = getchar();
        if (c=='#') *pT = NULL; //空树
        else if (c>='A' && c<='Z') {
            *pT = (BiTNode *)malloc(sizeof(BiTNode)); if (!*pT) exit(OVERFLOW);
            (*pT)->data = c;
            (*pT)->lchild=(*pT)->rchild=NULL;
        } 
        else if (c=='(') {
            CreateBiTreeByGList2( &(*pT)->lchild );
            CreateBiTreeByGList2( &(*pT)->rchild );
        }
        else 
            break;
    }
    return OK;
}
int main() {
/* 6.70测试数据
A(B(#,D),C(E(#,F),#))
*/
    BiTree T;
    int cnt;
    cnt = CreateBiTreeByGList2(&T);
    if (cnt) {
        printf("二叉链表：\n");
        PreOrder(T);printf("\n");
        InOrder(T);printf("\n");
        PostOrder(T);printf("\n");
    } else {
        printf("输入不规范\n");
    }
    return 0;
}

错误记录

版本：Version0.0.1
时间：20181005

【测试数据】A(B(#,D(#,#)),C(E(#,F(#,#)),#))
【答案】

// v0.0.1
// 6.70 由广义表形式的输入建立二叉链表
Status CreateBiTreeByGList(BiTree *pT) {
    char c;
    BiTNode *p;
    c = getchar();
    if (c=='#') p=NULL; //空子树
    else {
        p = (BiTNode *)malloc(sizeof(BiTNode)); if (!p) exit(OVERFLOW);
        p->data=c; //赋值
        if (getchar()!='(') return ERROR; //格式错误
        if ( !CreateBiTreeByGList( &p->lchild ) ) return ERROR; //建立左子树
        if (getchar()!=',') return ERROR; //格式错误
        if ( !CreateBiTreeByGList( &p->rchild ) ) return ERROR; //建立右子树
        if (getchar()!=')') return ERROR; //格式错误
    }
    *pT = p; //把p传出去
    return TRUE;
}

【完整代码】

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#ifndef BASE
#define BASE
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int bool;
#endif
#define TElemType char //固定为char，若修改需要修改方法
typedef struct BiTNode { // 结点结构
    TElemType      data;
    struct BiTNode  *lchild, *rchild; // 左右孩子指针
}BiTNode, *BiTree;
void visit(TElemType e) {
    printf("%c", e);
}
// 先序遍历二叉树
void PreOrder(BiTree T) { // - 递归
    if (!T) return ;
    visit(T->data);
    PreOrder(T->lchild);
    PreOrder(T->rchild);
}
// 中序遍历二叉树
void InOrder(BiTree T) { // - 递归
    if (!T) return ;
    InOrder(T->lchild);
    visit(T->data);
    InOrder(T->rchild);
}
// 后序遍历二叉树
void PostOrder(BiTree T) { // - 递归
    if (!T) return ;
    PostOrder(T->lchild);
    PostOrder(T->rchild);
    visit(T->data);
}
// 6.70 由广义表形式的输入建立二叉链表
Status CreateBiTreeByGList(BiTree *pT) {
    char c;
    BiTNode *p;
    c = getchar();
    if (c=='#') p=NULL; //空子树
    else {
        p = (BiTNode *)malloc(sizeof(BiTNode)); if (!p) exit(OVERFLOW);
        p->data=c; //赋值
        if (getchar()!='(') return ERROR; //格式错误
        if ( !CreateBiTreeByGList( &p->lchild ) ) return ERROR; //建立左子树
        if (getchar()!=',') return ERROR; //格式错误
        if ( !CreateBiTreeByGList( &p->rchild ) ) return ERROR; //建立右子树
        if (getchar()!=')') return ERROR; //格式错误
    }
    *pT = p; //把p传出去
    return TRUE;
}
int main() {
/* 6.70测试数据
A(B(#,D(#,#)),C(E(#,F(#,#)),#))
*/
    BiTree T;
    int cnt;
    cnt = CreateBiTreeByGList(&T);
    if (cnt) {
        printf("二叉链表：\n");
        PreOrder(T);printf("\n");
        InOrder(T);printf("\n");
        PostOrder(T);printf("\n");
    } else {
        printf("输入不规范\n");
    }
    return 0;
}

根据 广义表GList 创建 二叉树BiTree（严蔚敏《数据结构》6.70）

错误记录

根据广义表GList 创建二叉树BiTree（严蔚敏《数据结构》6.70）