c++ - 无法将摩尔斯电码排序为二叉树

Question

我想了解为什么我的 Insert(string key) 没有正确排序莫尔斯电码 (a-z 0-9)。从输出看来，它正在对完全相同的摩尔斯电码进行排序。这让我相信问题出在我的 Insert 函数上，因为提供给 Insert 函数的摩尔斯电码不包含任何重复项。

void BST::Insert(node *&start, string key){
    if (start == NULL) {
        start = new node;
        start->code = key;
        start->left = start->right = NULL;
        printf("Inserting Morse Code -> %s\n",key.c_str());
    }
}


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);
    }
}

我正在生成的输出是:

Inserting Morse Code -> .-
Inserting Morse Code -> -...
Inserting Morse Code -> -...
Inserting Morse Code -> -...
Inserting Morse Code -> -...
Inserting Morse Code -> -.-.
Inserting Morse Code -> -.-.
Inserting Morse Code -> .
Inserting Morse Code -> ..-.
Inserting Morse Code -> ..-.
Inserting Morse Code -> ..-.
Inserting Morse Code -> --.
Inserting Morse Code -> --.
Inserting Morse Code -> ....
Inserting Morse Code -> ....
Inserting Morse Code -> .---
Inserting Morse Code -> .---
Inserting Morse Code -> .---
Inserting Morse Code -> .-..
Inserting Morse Code -> .-..
Inserting Morse Code -> ---
Inserting Morse Code -> .--.
Inserting Morse Code -> --.-
Inserting Morse Code -> ...-
Inserting Morse Code -> -..-
Inserting Morse Code -> -.--
Inserting Morse Code -> --..
Inserting Morse Code -> ----
Inserting Morse Code -> .----
Inserting Morse Code -> ..---
Inserting Morse Code -> ..---
Inserting Morse Code -> ...--
Inserting Morse Code -> ....-
Inserting Morse Code -> .....
Inserting Morse Code -> -....
Inserting Morse Code -> --...
Inserting Morse Code -> ---..
Inserting Morse Code -> ---..
Inserting Morse Code -> ----.
.....
....
....-
....
...-
...--
..-.
..-.
..-.
..---
..---
.
.-..
.-..
.---
.--.
.---
.---
.----
.-
-....
-...
-...
-..-
-...
-.-.
-.-.
-.--
-...
--...
--..
--.
--.-
--.
---..
---..
---
----.
----

Answer 1

有什么问题？

您的 Insert(*start, key); 位于 for 循环的主体中，该循环一直重复直到达到字符串的长度。因此，当插入 4 个莫尔斯数字的代码时，您将插入 4 次。唯一的异常(exception)是第一次插入，因为这是一个没有 for 循环的分支。

如何解决？

您需要将 key 与当前代码进行比较，以决定是向左插入还是向右插入。目前，您正试图通过混合不合适的迭代和递归方法来解决这个问题。

更好的方法是使用公共(public)前端函数:

void BST::Insert(string key) {
    Insert(root, key); 
    }

并将辅助函数设为私有(private)和递归:

void BST::Insert(node *&start, string key){
    if (start == nullptr) {    // new node must be created
        start = new node;
        start->code = key;    // better move this to the node constructor
        start->left = start->right = nullptr;  // same here
        printf("Inserting Morse Code -> %s\n",key.c_str());
    }
    else if (start->code<key) 
        Insert (start->left, key); 
    else if (start->code>key) 
        Insert (start->right, key); 
    else cout<<"Duplicate"<<endl;
}

Online demo

您可能想要修改评估订单的方式。

现在，因为它始终是相同的键，您可以将键作为 const string& 传递，以避免递归中不必要的拷贝。