0

我有一个使用模板类的数据结构，它可以存储任何数据类型——整数、浮点数、字符串等。

因为数据会被组织起来，所以我需要一种方法来比较两个值。通常我可以使用 > 或 <，但在字符串不起作用的情况下，因为在字符串上使用 >/< 运算符不会告诉我哪个按字母顺序排在第一位。为此，我需要使用 compare() 函数。

然而，由于数据结构是一个模板类，我不能告诉它使用 compare() 函数，因为它不会识别除了字符串之外的任何东西的 compare() 函数。

作为一种解决方法，我尝试编写两个比较函数：

template (class t)
int BinaryTree<T>::compareVals(T v1, T v2);

和

template (class t)
int BinaryTree<T>::compareVals(string v1, string v2);

因此，在值是字符串类型的情况下，程序将使用带有 compare() 函数的方法。

但是尝试这样做，我得到一个编译器错误，基本上告诉我我不能重载函数。

所以我没有想法。我怎样才能使这个模板类正确地比较和排序字符串以及数字？

非常感谢您的意见！

这是整个课程，供参考：

#ifndef binarytree_class
#define binarytree_class

#include <iostream>
#include <string>
#include <vector>

using std::cout; 
using std::string;
using std::vector;

template <class T>
class BinaryTree{
    public:
        struct TreeNode{
            TreeNode * leftChild, 
                     * rightChild;
            T key;
            vector<T> data;
            int size;
        };

        BinaryTree();
        ~BinaryTree();
        bool isEmpty();
        int getSize();
        void add(T key, T data);
        void remove(T key);
        int getHeight();
        bool keyExists(T key);
        int getKeyHeight(T key);
        void displayAll();                    

    private: 
        int size;
        TreeNode * root;

        TreeNode * findParent(TreeNode * start, TreeNode * child); //finds the parent node of child in subtree starting at root start
        TreeNode * findNode(TreeNode * node, T input); //find node with data input in subtree at root node
        TreeNode * findMin(TreeNode * node);     
        void removeNode(TreeNode * node);      //Small part of algorithm (case: 2 children) borrowed from tech-faq.com/binary-tree-deleting-a-node.html
        void displaySubTree(TreeNode * node);  //displays subtree starting at node
        void sortAdd(TreeNode * eNode, TreeNode * nNode);  //adds a new node nNode to subtree starting at root eNode  
        void destroySubTree(TreeNode * node);  //destroys subtree starting at node. 
        void display(TreeNode * node, string indent, bool last); //Algorithm borrowed from http://stackoverflow.com/questions/1649027/how-do-i-print-out-a-tree-structure
        char leftOrRight(TreeNode * eNode, TreeNode * nNode); //compares keys in existing node vs new node and returns L or R
        int calcHeight(TreeNode * node, int depth);  //calculates the height from node. Algorithm borrowed from wiki.answers.com
        int compareVals(T v1, T v2);
        int compareVals(string v1, string v2);      
};

template <class T>
BinaryTree<T>::BinaryTree<T>() : size(0){}

template <class T>
bool BinaryTree<T>::isEmpty(){
    return (!size);
}

template <class T> 
int BinaryTree<T>::compareVals(T v1, T v2){
    int result;
    v1 <= v2? result = -1 : result = 1;
    return result;
}

template <class T> 
int BinaryTree<T>::compareVals(string v1, string v2){
    int result;
    result = v1.compare(v2);
    if(result >= 0)
        result = -1;
    else
        result = 1;
    return result;
}

template <class T>
int BinaryTree<T>::getSize(){
    return size;
}

template <class T>
void BinaryTree<T>::add(T key, T data){
    bool done = false;
    TreeNode * temp;

    if(keyExists(key)){
        temp = findNode(root,key);
        temp->size++;
        temp->data.push_back(key); 
    }
    else{
        temp = new TreeNode;
        temp->leftChild = 0;
        temp->rightChild = 0;
        temp->key = key;
        temp->size = 0;
        temp->data.push_back(data);        
        if(isEmpty())
            root = temp;   
        else
            sortAdd(root, temp);
       size++; 
    }
}

template <class T>
void BinaryTree<T>::sortAdd(TreeNode * eNode, TreeNode * nNode){
    if(leftOrRight(eNode, nNode) == 'L'){
        if(eNode->leftChild == 0)
            eNode->leftChild = nNode;
        else
            sortAdd(eNode->leftChild,nNode);
    } else {
        if(eNode->rightChild == 0)
            eNode->rightChild = nNode;
        else
            sortAdd(eNode->rightChild,nNode);
    }
}

template <class T>
char BinaryTree<T>::leftOrRight(TreeNode * eNode, TreeNode * nNode){
    char result;
    if(compareVals(nNode->key, eNode->key) == -1)
        result = 'L';
    else
        result = 'R';
    return result;
}

template <class T>
void BinaryTree<T>::displayAll(){
    display(root,"",true);    
}

template <class T>
void BinaryTree<T>::display(TreeNode * node, string indent, bool last){
    if(!isEmpty()){
        cout << indent;
        if(last){
            cout << "\\-";
            indent += " ";  
        } else {
            cout << "|-";
            indent += "| ";
        }
        cout << node->key << "\n";
        if(node->leftChild != 0)
            display(node->leftChild, indent, false);
        if(node->rightChild != 0)
            display(node->rightChild, indent, true); 
    } else
        cout << "TREE IS EMPTY" << "\n\n";
}

template <class T>
int BinaryTree<T>::getHeight(){
      if(!root)
        cout << "ERROR: getHeight() root is NULL!" << "\n";
      int result;
      if(isEmpty())
            result = 0;
      else
            result = calcHeight(root, 1);
      return result;
}

template <class T>
int BinaryTree<T>::getKeyHeight(T key){
    int result = -1;
    if(!keyExists(key))
        cout << "ERROR: Trying to get height of nonexistant key " << key << "\n";
    else{
        TreeNode * temp = findNode(root, key);    
        result = getHeight() - calcHeight(temp,1);
    }
    return result;
}

template <class T>
int BinaryTree<T>::calcHeight(TreeNode * node, int depth){ //Algorithm borrowed from wiki.answers.com
    int leftDepth,
        rightDepth,
        result;
    if(node->leftChild)
        leftDepth = calcHeight(node->leftChild, depth+1);
    else
        leftDepth = depth;
    if(node->rightChild)
        rightDepth = calcHeight(node->rightChild, depth+1);
    else
        rightDepth = depth;
    if(leftDepth > rightDepth)     
        result = leftDepth;
    else
        result = rightDepth;
    return result;
}

template <class T>
void BinaryTree<T>::remove(T input){
    if(!keyExists(input))
        cout << "ERR: trying to remove nonexistant key " << input << "\n";
    else{
        TreeNode * temp = findNode(root,input);
        removeNode(temp);
    }      
}

template <class T>
bool BinaryTree<T>::keyExists(T key){
    bool result;
    if(isEmpty())
        result = false;
    else{
        if(findNode(root,key) != 0)
            result = true;
        else
            result = false;
    }   
    return result;    
}


template <class T>
typename BinaryTree<T>::TreeNode * BinaryTree<T>::findNode(TreeNode * node, T input){
    TreeNode *  result = 0;     //Returns 0 if none found
    if(node->key == input)
        result = node;
    else{
        if(node->leftChild != 0)
            result = findNode(node->leftChild, input);
        if(result == 0 && node->rightChild != 0)
            result = findNode(node->rightChild, input);
    }
    return result;
}

template <class T>
void BinaryTree<T>::removeNode(TreeNode * node){
    TreeNode * parent = 0;
    if(node != root)
        parent = findParent(root,node);

    if(node->leftChild && node->rightChild){                    //Case: both children (algorithm borrowed from tech-faq.com)
        TreeNode * temp = findMin(node->rightChild);  
        string tkey = temp->key;
        removeNode(temp); 
        node->key = tkey;
    } else {
        if(parent){                                             
            if(!(node->leftChild) && !(node->rightChild)){      //case: no children & not root
                if(parent->leftChild == node)
                    parent->leftChild = 0;
                else
                    parent->rightChild = 0;    
            }    
            if(!(node->leftChild) && node->rightChild){         //case: right child only & not root
                if(parent->leftChild == node)
                    parent->leftChild = node->rightChild;
                else
                    parent->rightChild = node->rightChild;    
            }
            if(node->leftChild && !(node->rightChild)){         //case: left child only & not root
                if(parent->leftChild == node)
                    parent->leftChild = node->leftChild;
                else
                    parent->rightChild = node->leftChild;    
            }
            delete node;
            size--;
        }
        else{
            if(node->leftChild)                             //case: left child only & root
                root = node->leftChild;
            else                                           //case: right child only & root
                root = node->rightChild;
            delete node;                                   //case: no children & root intrinsically covered
            size--;    
        }
    }
}

template <class T>
typename BinaryTree<T>::TreeNode * BinaryTree<T>::findMin(TreeNode * node){
    TreeNode * result;
    if(node->leftChild == 0)
        result = node;
    else
        result = findMin(node->leftChild);
    return result;
}

template <class T>
typename BinaryTree<T>::TreeNode * BinaryTree<T>::findParent(TreeNode * start, TreeNode * child){
    TreeNode * result = 0;

    if(start->leftChild){
        if(start->leftChild->key == child->key)
            result = start;   
        else 
            result = findParent(start->leftChild, child);
    }
    if(start->rightChild && result == 0){
        if(start->rightChild->key == child->key)
            result = start;    
        else
            result = findParent(start->rightChild, child);
    }
    return result;
}

template <class T>
void BinaryTree<T>::destroySubTree(TreeNode * node){
    TreeNode * parent = 0;
    if(node != root)
        parent = findParent(root,node);
    if(node->leftChild)
        destroySubTree(node->leftChild);
    if(node->rightChild)
        destroySubTree(node->rightChild);
    if(parent){
        if(parent->leftChild == node)
            parent->leftChild = 0;
        else
            parent->rightChild = 0;
    }   
    size--;
    delete node;    
}

template <class T>
BinaryTree<T>::~BinaryTree<T>(){
    if(!isEmpty())
        destroySubTree(root);
}



#endif
4

1 回答 1

1

When Tis std::string，您最终将不得不使用具有相同签名的函数，这就是您的编译器抱怨的原因。为了克服这个问题，只需制作compareVals一个自己的模板。我还建议您制作它们static，这样您就可以在没有对象的情况下调用它们。

static int compareVals(std::string const& v1, std::string const& v2)
{
    //compare std::string
}

template<typename U>
static int compareVals(U v1, U v2)
{
    //compare everything else
}

事实上，std::string 确实内置了关系运算符，因此对于您的特定用例，可能不需要像上面那样定义比较函数。无论如何，这种方法对于避免假设运算符是为您BinaryTree将来可能最终支持的每种数据类型定义的假设仍然有用。

于 2013-09-30T01:28:38.363 回答