c++ - 将摩尔斯电码插入二叉树

Question

我正在尝试将摩尔斯电码插入到二叉树中，但我的 Insert() 出现了问题。我对它失败的原因感到困惑。

二叉树类:

class BST
{
    private:
            struct Node
            {
                string letter;
                string code;
                Node *left;
                Node *right;
            };
            Node *root;

    public:
            BST()
            {
                root = NULL;
            }
            void Insert(Node *&r, string letter, string code)
            {
                if(r == NULL)
                {
                    r = new Node; 
                    r->letter = letter; 
                    r->code = code;
                    r->left = r->right = NULL; 
                }
            }
            void Insert(string letter, string code)
            {
                Node *r = root;
                if(r != NULL)
                {
                    for(int i = 0; i < code.length(); i++)
                    {
                        if(code[i] == '.') r = r->left;
                        else if(code[i] == '-') r = r->right;
                        else break;
                    }
                    Insert(r, letter, code);
                }
                else Insert(root, letter, code);
            }
};

主要内容:

struct alphaTree
{
    string letter;
    string code;
};

alphaTree tree[] = {  
                       {"ROOT", ""},  {"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", "--.-"}  
                    };

for(int i = 0; i < 27; i++)
{
    t.Insert(tree[i].letter, tree[i].code);
}

我的 tree[] 数组的前 3 个元素被插入，但程序在尝试插入 “I” 时崩溃。

Answer 1

当您插入一个新节点时，左右父节点不会更新。

您可能认为 parent 已更新，因为您通过引用传递指针，但您传递的是 r而不是 r->left或 r->root你应该这样做。

一种可能的解决方案是使用 **r相反，如果 *r在void Insert(string letter, string code)

您可以更改如下内容:( Working example here )

    void Insert(string letter, string code)
    {
        Node **r = &root;
        if(*r != NULL)
        {
            for(int i = 0; i < code.length(); i++)
            {
                assert(*r);
                if(code[i] == '.') r = &((*r)->left);
                else if(code[i] == '-') r = &((*r)->right);
                else break;
            }
            Insert(*r, letter, code);
        }
        else Insert(root, letter, code);
    }

与您的问题无关，但作为旁注:

1. 在 for(int i = 0; i < code.length(); i++)你正在比较一个带有 singed int 的无符号(长度)。你应该改变 i到std::string::size_type.
2. 函数void Insert(string letter, string code)你应该添加assert(*r) 在访问 *r 之前 children 。