如何在C语言摩尔斯码解码器的二叉树中按指定结构插入字符？

嘿，你的问题出在插入逻辑完全偏离了摩尔斯码二叉树的核心规则——你现在是用字符的字典序（strcmp比较）来决定左/右子节点，但摩尔斯树的结构是由字符对应的摩尔斯码的点（.）和划（-）顺序来导航的：

• 点（.）对应向左走（dot子指针）
• 划（-）对应向右走（dash子指针）
• 每一位摩尔斯码都对应树中的一层，最终到达的节点就是该字符的位置

原代码的核心问题 #

你的insert函数用字符的字典序判断左右，比如"A"的字典序比"E"小，会被插到E的左子树，这和摩尔斯码树的结构完全不符（E的右子树才是A，对应编码.-）。我们需要彻底重写插入逻辑，基于摩尔斯码的路径来插入节点。

修改后的完整代码 #

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct BTree { 
    char value[100]; 
    struct BTree *dot, *dash; 
} BTree, *tree_ptr;

// 新的插入函数：根据摩尔斯码路径插入字符
tree_ptr insert(tree_ptr root, const char *char_val, const char *morse) {
    // 如果根节点为空，先创建一个空的起始根节点
    if (root == NULL) {
        root = (tree_ptr)malloc(sizeof(BTree));
        strcpy(root->value, "");
        root->dot = NULL;
        root->dash = NULL;
    }

    tree_ptr current = root;
    // 遍历摩尔斯码的每一位，导航到目标节点
    for (int i = 0; morse[i] != '\0'; i++) {
        if (morse[i] == '.') {
            // 点：走左子树，不存在则创建空节点
            if (current->dot == NULL) {
                current->dot = (tree_ptr)malloc(sizeof(BTree));
                strcpy(current->dot->value, "");
                current->dot->dot = NULL;
                current->dot->dash = NULL;
            }
            current = current->dot;
        } else if (morse[i] == '-') {
            // 划：走右子树，不存在则创建空节点
            if (current->dash == NULL) {
                current->dash = (tree_ptr)malloc(sizeof(BTree));
                strcpy(current->dash->value, "");
                current->dash->dot = NULL;
                current->dash->dash = NULL;
            }
            current = current->dash;
        }
    }
    // 到达目标节点后，写入字符
    strcpy(current->value, char_val);
    return root;
}

// 修改前序遍历：只打印有字符的节点（跳过空的起始节点和中间路径节点）
void preorder(tree_ptr root) {
    if (root == NULL) return;
    // 仅输出存储了字符的节点
    if (strcmp(root->value, "") != 0) {
        printf("%s ", root->value);
    }
    preorder(root->dot);
    preorder(root->dash);
}

int main(void) {
    int i;
    BTree *root = NULL;
    char *characters[] = {"E", "T", "I", "A", "N", "M", "S", "U", "R", "W", "D", "K", "G", "O", "H", "V", "F", "L", "P", "J", "B", "X", "C", "Y", "Z", "Q" ,"\0"};
    char *morsecode[] = {".", "-", "..", ".-", "-.", "--","...","..-",".-.",".--", "-..","-.-","--.","---","....","...-","..-.", ".-..",".--.",".---","-...", "-..-","-.-.","-.--","--..","--.-", "\0"};

    // 同时遍历字符和对应的摩尔斯码，插入到树中
    for (i = 0; strcmp(characters[i], "\0") != 0; i++){
        root = insert(root, characters[i], morsecode[i]);
    }

    printf("前序遍历结果（符合摩尔斯树结构）：\n");
    preorder(root);
    printf("\n");

    // 注意：实际使用时记得添加内存释放逻辑，避免泄漏
    return 0;
}

关键部分解释 #

1. 插入逻辑重写：
   • 首先创建一个空的起始根节点（摩尔斯树的起点）
   • 遍历目标字符的摩尔斯码每一位，按.走左、-走右的规则导航
   • 路径上的节点不存在时就创建空节点，最终到达的节点写入对应字符
2. 遍历函数优化：
   • 跳过空的起始节点和中间路径节点，只打印存储了字符的节点
3. main函数调整：
   • 同时传入字符和对应的摩尔斯码到insert函数，不再单独传字符

运行结果 #

执行后前序遍历的输出为：

E I S H V U F A R L W P J T N D B X K C Y M G Z Q O 

完全符合你想要的结构：根节点左子节点是E，右是T；E的左是I、右是A；T的左是N、右是M，以此类推。

内容的提问来源于stack exchange，提问作者Senol Alan