如何从字符串创建二叉查找树？

Question

我试图创建一个莫尔斯编码器-解码器，我必须使用二进制搜索树（而不是数组）。下面的部分假定获取一个字符数组（我们之前从一个文本文件创建了这个数组），并基于它创建一个搜索树。

在btree|u基本字符数组中，我们有以下格式的数据：“（字母）（摩尔斯电码）|（字母）（摩尔斯电码）|”等（例如e.| t-| z-|…）。

注意：字符串包含数据的方式是，通过从头到尾读取数据，将创建一个平衡的搜索树

二叉树的创建没有成功，我知道，因为当我运行代码时，btree_print函数不会在控制台上打印任何内容，我发现这是因为向它传递了一个空指针。

我的问题是为什么会这样，以及如何解决这个问题？我是弄乱了指针，还是在传递根指针时需要使用双重间接寻址？我真的不懂**指针，所以我试着避开它们。

typedef struct BinTree{
    char letter;
    char code[6];
    struct BinTree *left, *right;
} BTree;

BTree* add(BTree* root, char ch, char* code, int length){
    int i;
    char a;
    if (root == NULL) {
        BTree *new = (BTree*) malloc(sizeof(BTree));
        new->left = new->right = NULL;
        new->letter = ch;
        for(i=0; i<length; i++) new->code[i] = code[i];
        new->code[length] = '\0';
        return new;
    }

    a=root->letter;

    if (ch < a) root->left = add(root->left, ch, code, length);
    else if (ch > a) root->right = add(root->right, ch, code, length);

    return root;
}

void build(BTree* root, char* c, int length){
    int i, size=-1;
    char b, k[6];
    for(i=0; i<length; i++){
        if(size==-1) b=c[i];
        if(c[i]==' ') size=0;
        if(size!=-1 && c[i]!='|'){
            k[size]=c[i];
            size++;
        }
        if(c[i]=='|'){
            k[size]='\0';
            root=add(root, b, k, size);
            size=-1;
        }
    }
}

void btree_print(BTree* root){
    if(root == NULL) return;

    printf("%c %s\n",root->letter,root->code);
    btree_print(root->left);
    btree_print(root->right);
}

void btree_del(BTree* root){
    if(root==NULL) return;

    btree_del(root->left);
    btree_del(root->right);
    free(gyoker);
}

int main(){
    char btree_base[238];
    BTree* bin_root = NULL;

    build(bin_root, btree_base, 238);

    btree_print(bin_root);

    btree_del(bin_root);
    return 0;
}

Answer 1

因为您要通过值将根节点传递给build，所以对其值所做的任何更改都不会反映到调用函数中。因此，正如您所猜测的，您需要传递一个指向根的指针，这将使它成为一个b树**。

build(&bin_root, btree_base, 238);

然后在build内部，当你想访问根节点时，你必须先用*前缀来解除对根节点的引用，如下所示：

*root=add(*root, b, k, size);

add也可以从这样的工作中受益，而不是返回更新的节点。因为build已经有一个BTree**意味着你只需要像这样传入root

add(root, b, k, size);