c++ - 在 C++ 中为 BST 类（不同类型的键）制作模板

Question

我已经编写了 BST-Tree 的实现，但键只能是字符串类型。我想将该树与其他类型的键一起使用。我知道我必须定义一个模板，但不知道该怎么做，所以键会有T类型。这些示例显示了所有但不重要的东西。

using namespace std;
int ASCENDING = 0, DESCENDING = 1;
class Node {
public:
      string key; //I would like to change type to T
      Node* left;
      Node* right;
      Node(string key) {
            this->key = key;
            left = NULL;
            right = NULL;
      }
};

class BST {
public:
      Node* root;
      BST(string key) {
            root = new Node(key);
      }

    void insert(string value){
        if(root == NULL)
            root = new Node(value);
        else
            insertHelper(root, value);
    }

    void insertHelper(Node* node, string value){
        if(value < node->key){
            if(node->left == NULL)
                node->left = new Node(value);
            else
                insertHelper(node->left, value);
        }
        else{
            if(node->right == NULL)
                node->right = new Node(value);
            else
                insertHelper(node->right, value);
        }
    }
    void print(int order){
        show(order, root);
    }

      ~BST(){
        //delete all nodes
      }
private:
    void show(int order, Node* n){
        Node* pom = n;
        if(order == ASCENDING){
            if(pom != NULL){
                show(order, n->left);
                cout<<n->key<<endl;
                show(order, n->right);
            }
        }else{
            if(pom != NULL){
                show(order, n->right);
                cout<<n->key<<endl;
                show(order, n->left);
            }
        }

      }
};

Answer 1

这应该涵盖基本设置，其余更改应该类似：

template <typename T>
class Node {
public:
      T key; //I would like to change type to T
      ^^^^^ Type now T
      Node<T>* left;
      Node<T>* right;
      Node(T key) {
            this->key = key;
            left = NULL;
            right = NULL;
      }
};

template <typename T>
class BST {
public:
      Node<T>* root;
      ^^^^^^^ Node now will become Node<T> in the rest of the code as well
      BST(T key) {
            root = new Node<T>(key);
      }

      //  rest of code
};