BST插入摩尔斯码异常：Insert函数重复插入相同编码问题排查

我一眼就瞅出问题所在了——你的Insert(string key)方法里的循环逻辑完全跑偏了，直接导致同一个摩尔斯码被重复插入了N次（N等于该摩尔斯码的长度）！

问题根源拆解 #

看你这段公开的Insert代码：

void BST::Insert(string key) { 
    node **start = &root; 
    if (*start != NULL) { 
        for(int i = 0; i < key.length(); i++) { 
            assert(*start); 
            if (key[i] == '.') { 
                start = &((*start)->left); 
            } else if (key[i] == '-') { 
                start = &((*start)->right); 
            }else { 
                break; 
            } 
            Insert(*start, key); // 这里是罪魁祸首！
        } 
    } else { 
        Insert(root, key); 
    } 
}

你在循环的每一次迭代里都调用了辅助Insert函数。比如摩尔斯码-...的长度是4，循环会跑4次，每次都插入同一个-...，这正好和你输出里它出现4次的情况完全对应。

正确的逻辑应该是：沿着摩尔斯码的字符路径（.走左子节点，-走右子节点）遍历到空节点的位置，然后只插入一次，而不是每走一步就插一次。

修复后的代码 #

把公开的Insert方法改成这样：

void BST::Insert(string key) {
    node **start = &root;
    
    // 先沿着摩尔斯码路径遍历到目标位置
    for(int i = 0; i < key.length(); i++) {
        // 如果中途遇到空节点，直接跳出循环准备插入
        if (*start == NULL) {
            break;
        }
        if (key[i] == '.') {
            start = &((*start)->left);
        } else if (key[i] == '-') {
            start = &((*start)->right);
        } else {
            // 遇到非摩尔斯字符，停止遍历
            break;
        }
    }
    
    // 现在start指向的就是要插入的空位置，只插入一次
    Insert(*start, key);
}

额外提醒 #

你的辅助Insert函数目前只初始化了code和左右子节点，如果你需要在节点中存储摩尔斯码对应的明文（比如a-z、0-9），记得补充初始化对应的字段，不过这不是当前重复插入问题的诱因。

修改后，同一个摩尔斯码只会被插入一次，和你的输入内容保持一致，不会再出现重复插入的情况了。

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