如何根据一个字符串递归建立二叉树？

Question

node *c2(char *s){
    node *tem;
    if(*s == '#' || *s == '\0') tem = NULL;
    else{
        tem = (node*)malloc(sizeof(struct node));
        tem->data = *s;
        tem->left = NULL;
        tem->right = NULL;

        tem->left = c2(++s);
        tem->right = c2(++s);
    }
    return tem;
}

s是一个字符数组，这样建树有错吗？为什么输出的结果不对呢？谢谢大家

Answer 1

tem->left = c2(++s);
tem->right = c2(++s);

构建完左子树后s的值只是加了1，在递归调用中并没有改变当前的s值。

Answer 2

tem->left = c2()这种写法并没让树节点真正链接起来。
改成这样吧

typedef struct BiTNode {
    char data;
    struct BiTNode *left, *right;
}BiTNode, *BiTree;

void createBiTree(BiTree &T) {
    char el = *s++;
    if (el == '#' || el == '\0') {
        T = NULL;
    } else {
        T = (BiTNode *)malloc(sizeof(BiTNode));
        T->data = el;
        createBiTree(T->left);
        createBiTree(T->right);
    }
}