0

我不能，为了我的一生，弄清楚这个问题！！！我用字符串参数调用“encode()”方法。当我遍历该字符串的字符时，我使用该字符串的字符调用“encode_char()”方法。encode_char() 方法遍历二叉树，每次左遍历都附加一个“*”，每个右遍历附加一个“-”。如果我来到一个 NULL 节点，我会跳过遍历，退出函数调用并减去添加的最后一个字符。例如。

return encode_char(node->left, let, codeString += "*"); // traverse & append
codeString = codeString.substr(0, codeString.size() - 1); // subtract last symbol
return encode_char(node->right, let, codeString += "-"); // traverse & append
codeString = codeString.substr(0, codeString.size() - 1); // subtract last symbol

目标：当我找到我正在搜索的节点时，我想返回创建的 codeString 并返回调用它的 encode() 方法。

class Morse_Code_Tree{

public:
Morse_Code_Tree() : root(NULL){}
void insert(char let, std::string codeString);
Morse_Node* getRoot(){return root;}
//std::string find(char let);
std::string decode(std::string message);
std::string encode(std::string message);
std::string encode_char(const Morse_Node* node, char let, std::string codeString);

protected:
Morse_Node* root;
};

// THIS FUNCTION IS THE PROBLEM
std::string Morse_Code_Tree::encode_char(const Morse_Node* node, char let, 
std::string codeString) {

if (node == NULL){
    // do nothing
}else if (node->letter == let){
    //cout << codeString << " ";
    return codeString;
}
else{
    return encode_char(node->left, let, codeString += "*");
    codeString = codeString.substr(0, codeString.size() - 1);
    return encode_char(node->right, let, codeString += "-");
    codeString = codeString.substr(0, codeString.size() - 1);
}
}

std::string Morse_Code_Tree::encode(std::string message){
std::string result = "";
for (size_t i = 0; i < message.length(); i++){
    std::string temp;
    char let = tolower(message[i]);
    result += encode_char(root, let, "");
}
return result;
}

void Morse_Code_Tree::insert(char let, std::string codeString){

// set root to empty
if (root == NULL){
    char letter = ' ';
    Morse_Node* blankNode = new Morse_Node(letter);
    root = blankNode;
}

Morse_Node* temp = root;
for (size_t i = 0; i < codeString.length(); i++){
    if (codeString[i] == '.'){
        if (i == codeString.length() - 1){
            Morse_Node* node = new Morse_Node(let);
            temp->left = node;
            break;
        }
        temp = temp->left;
    }
    else{
        if (i == codeString.length() - 1){
            Morse_Node* node = new Morse_Node(let);
            temp->right = node;
            break;
        }
        temp = temp->right;
    }
}
}

std::string Morse_Code_Tree::decode(std::string message){

std::string decodedMessage;
Morse_Node* temp = root;

for(size_t i = 0; i < message.length(); i++){
    char bit = message[i];
    if (bit == '*'){
        temp = temp->left;
    }
    else if (bit == '-'){
        temp = temp->right;
    }
    else if (bit == ' '){
        decodedMessage += temp->letter;
        temp = root;
    }
}
return decodedMessage;
}
4

1 回答 1

0

您的函数将仅沿左树递归，但从不会沿右树递归，因为您return从第一次递归调用 encode_char。

// THIS FUNCTION IS THE PROBLEM
std::string Morse_Code_Tree::encode_char(const Morse_Node* node, char let, std::string codeString)
{
    if (node == NULL)
    {
        /* changed to return empty string, vs random nothing */
        return std::string();
    }
    else if (node->letter == let)
    {
        //cout << codeString << " ";
        return codeString;
    }
    else
    {
        std::string rv;
        rv = encode_char(node->left, let, codeString += "*");
        if (!rv.empty()) {
            return rv; /* found something down the left side */
        }
        /* this code now reached, due to no return above, so the right tree is traversed */ 
        codeString = codeString.substr(0, codeString.size() - 1);
        rv = encode_char(node->right, let, codeString += "-");
        if (!rv.empty()) {
            return rv; /* found something in the right tree */
        }
        /* nothing found in right or left, return empty string */
        return rv;
        /* codeString = codeString.substr(0, codeString.size() - 1); */
    }
}
于 2013-11-14T05:50:37.183 回答