用于莫尔斯电码转换的二叉搜索树

问题描述 投票：0回答：1

我正在使用二叉搜索树进行莫尔斯转换。 （是的，我知道这对于这项任务来说不是必需的，但这是为了学校作业。）

我对如何解决这个问题感到困惑，因为我的一般理解是我必须将莫尔斯表“集中”在 G 上？因为它的 ASCII 码在中间。这样就会平衡树，这样从A-9开始遍历就不会只是一个链表了。插入将如何进行？我可以从 A-9 插入，包括标点符号吗？

我尝试从 A-Z 插入，但我的 BST 损坏了。我成功插入了 G、A、C，结果是：

          C|-.-.

G|--.

          A|.-

考虑到这一点，我像这样设置了 BST：

template <typename KeyType, typename ValueType>
class BST {
private:
    BSTNode<KeyType, ValueType>* pRoot;

    void destroyBST(BSTNode<KeyType, ValueType>* bstNode);

    void insertNode(BSTNode<KeyType, ValueType>* bstNode, const KeyType &key, const ValueType &value);

    void printBSTHelper(BSTNode<KeyType, ValueType>* pRoot,int space);

    void printBSTinOrderHelper(BSTNode<KeyType, ValueType>* bstNode);

public:
    // Constructor
    BST() : pRoot(nullptr) {}


    // Destructor
    ~BST(){
        destroyBST(pRoot);
    }

    void insert(KeyType key, ValueType value);

    ValueType search(KeyType key);

    void printBST();

    void printBSTinOrder();
};

template<typename KeyType, typename ValueType>
ValueType BST<KeyType, ValueType>::search(KeyType key) {
    BSTNode<KeyType,ValueType>* pCurr = pRoot;
    while(pCurr != nullptr){
        if(key < pCurr->getKey()){
            pCurr = pCurr->getPLeft();
        }else if(key > pCurr->getKey()){
            pCurr = pCurr->getPRight();
        }else if (key == pCurr->getKey() ){
            return pCurr->getValue();
        }
    }
    return ValueType();
}

template<typename KeyType, typename ValueType>
void BST<KeyType, ValueType>::insert(KeyType key, ValueType value) {
    insertNode(this->pRoot,key,value);
}

template<typename KeyType, typename ValueType>
void BST<KeyType, ValueType>::printBSTinOrderHelper(BSTNode<KeyType, ValueType> *bstNode) {
    if(bstNode == nullptr){
        return;
    }else{
        printBSTinOrderHelper(bstNode->getPLeft());
        cout << bstNode->getKey() << " " << bstNode->getValue() << endl;
        printBSTinOrderHelper(bstNode->getPRight());
    }

}

template<typename KeyType, typename ValueType>
void BST<KeyType, ValueType>::printBSTinOrder() {
    printBSTinOrderHelper(this->pRoot);
}

template<typename KeyType, typename ValueType>
void BST<KeyType, ValueType>::printBST() {
    printBSTHelper(pRoot,0);
}

template<typename KeyType, typename ValueType>
void BST<KeyType, ValueType>::printBSTHelper(BSTNode<KeyType, ValueType> *pRoot, int space) {
    if(pRoot == nullptr){
        return;
    }
    space += 10;
    printBSTHelper(pRoot->getPRight(),space);
    cout << endl;
    for(int i = 10; i < space; i++){
        cout << " ";
    }
    cout << pRoot->getKey() << "|" << pRoot->getValue() << endl;
    printBSTHelper(pRoot->getPLeft(),space);
}

template<typename KeyType, typename ValueType>
void BST<KeyType, ValueType>::destroyBST(BSTNode<KeyType, ValueType> *bstNode) {
    if(bstNode != nullptr){
        destroyBST(bstNode->getPLeft());
        destroyBST(bstNode->getPRight());
        delete bstNode;
    }
}

template<typename KeyType, typename ValueType>
void BST<KeyType, ValueType>::insertNode(BSTNode<KeyType, ValueType> *bstNode, const KeyType &key, const ValueType &value) {
    if(bstNode == nullptr){
        this->pRoot = new BSTNode<KeyType,ValueType>(key,value);
    }else{
        if(key < bstNode->getKey()){
            if(pRoot->getPLeft() == nullptr){
                pRoot->setPLeft(new BSTNode<KeyType,ValueType>(key,value));
            }else{
                insertNode(pRoot->getPLeft(),key,value);
            }
        }else if(key > bstNode->getKey()){
            if(pRoot->getPRight() == nullptr){
                pRoot->setPRight(new BSTNode<KeyType,ValueType>(key,value));
            }else{
                insertNode(pRoot->getPRight(),key,value);
            }
        }else{
            cout << "|Duplicate Value "<< endl;
        }
    }
}

我已经像这样设置了我的 BSTNode：

template <typename KeyType, typename ValueType>
class BSTNode {
private:
    KeyType key;
    ValueType value;
    BSTNode<KeyType, ValueType>* pLeft;
    BSTNode<KeyType, ValueType>* pRight;
public:

    BSTNode(KeyType k, ValueType v) : key(k), value(v), pLeft(nullptr), pRight(nullptr) {}

    KeyType getKey() const {
        return key;
    }

    void setKey(KeyType key) {
        BSTNode::key = key;
    }

    ValueType getValue() const {
        return value;
    }

    void setValue(ValueType value) {
        BSTNode::value = value;
    }

    BSTNode<KeyType, ValueType> *getPLeft() const {
        return pLeft;
    }

    void setPLeft(BSTNode<KeyType, ValueType> *pLeft) {
        BSTNode::pLeft = pLeft;
    }

    BSTNode<KeyType, ValueType> *getPRight() const {
        return pRight;
    }

    void setPRight(BSTNode<KeyType, ValueType> *pRight) {
        BSTNode::pRight = pRight;
    }

};

如果重要的话，这是我的 main():

int main() {
    BST<char,string> morseBST;
    morseBST.insert('G',"--.");
    morseBST.insert('A',".-");
    morseBST.insert('C',"-.-.");
    morseBST.insert('B',"-...");
    morseBST.printBST();
}
c++ binary-search-tree morse-code
1个回答
0
投票

我对如何解决这个问题感到困惑，因为我的一般理解是我必须将莫尔斯表“集中”在 G 上？因为它的 ASCII 码在中间。这样会平衡树，这样从A-9遍历就不会只是一个链表了。

@john 几乎做到了这一点。你不需要平衡 BST。

坦率地说，编写自动平衡二叉树的代码是一个非常高级的主题。我很难相信你会完成这个任务。我想最好的实用方法是创建一个包含字母和代码的表，然后将表中的条目以随机顺序插入到二叉树中。 – 约翰

如果随机选择字母和数字进行插入，您最终应该得到一个“树状”结构。

要了解平衡二叉树，请查阅优秀的算法文本，例如 Cormen、Leiserson、Rivest 和 Stein 所著的备受推崇的 算法简介。

插入失败

OP 的代码非常好。唯一真正的失败在于功能

insert
。

那里的代码调用了一个递归函数

insertNode
来帮忙，但这完全没有必要。函数插入节点修改了
pRoot
，这是其失败的原因之一。当 
pRoot
为空时，有一种特殊情况，但只应在函数 
insert
开始时检查一次。

之后，

search
和
insert
之间的功能有很多相似之处。

在 

search
声明已找到 
key
的地方，函数 
insert
应声明“重复键”，并拒绝进行插入。在 
search
声明 
key
不在树中的地方，
insert
应该添加它。

这是修补功能的一种方法

insert
。没有使用
insertNode
功能，所以可以删除。

template<typename KeyType, typename ValueType>
void BST<KeyType, ValueType>::insert(KeyType key, ValueType value) 
{
    if (pRoot == nullptr)
    {
        // Treat the null root as a special case.
        pRoot = new BSTNode<KeyType, ValueType>(key, value);
        return;
    }
    // Otherwise, loop "forever" until you either find the correct 
    // place for insertion, or else encounter a duplicate key.
    auto pCurr{ pRoot };
    for (;;)
    {
        auto current_key{ pCurr->getKey() };
        if (key < current_key)
        {
            if (pCurr->getPLeft())
            {
                pCurr = pCurr->getPLeft();
                continue;
            }
            pCurr->setPLeft(new BSTNode<KeyType, ValueType>(key, value));
            break;
        }
        else if (key > current_key)
        {
            if (pCurr->getPRight())
            {
                pCurr = pCurr->getPRight();
                continue;
            }
            pCurr->setPRight(new BSTNode<KeyType, ValueType>(key, value));
            break;
        }
        else  // (key == current_key)
        {
            std::cerr << "|Duplicate Value \n\n";
            break;
        }
    }
}

搜索需要更好的方式来指示“未找到”

OP 中的代码在搜索失败时返回默认构造的 ValueType 对象。

我宁愿让它返回

std::optional< ValueType >
。这样，当搜索失败时，可以返回
std::nullopt
。

否则，函数

search
的返回类型可能会更改为
ValueType*
，以便在搜索失败时返回
nullptr
。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.