-2

我正在尝试将“普通”类重写为模板类。我遇到了一个问题 - 函数int main ()。我不确定问题是否确实在这里，但编译器报告“在 'b' 之前缺少模板参数”。我在互联网上找不到与类似问题相关的示例代码。你能帮我吗？

这是我找到的代码：

#include <process.h>
#include <conio.h>
#include <iostream>
#include <cstdlib>

using namespace std;

class BinarySearchTree
{
    private:
        struct tree_node
        {
           tree_node* left;
           tree_node* right;
           int data;
        };
        tree_node* root;
    public:
        BinarySearchTree()
        {
           root = NULL;
        }

        bool isEmpty() const { return root==NULL; }
        void insert(int);
        bool search(int);

};

//----------------------------------------------------

bool BinarySearchTree::search(int d)
{
    tree_node* temp = root;
    while (temp != NULL)
        {
         if (temp->data == d)
          {
            cout<<"Tree contains this node"<<endl;
            return true;
          }
        else
          {
            if (d > temp->data)
              {
                temp = temp->right;
              }
            else
              {
                temp = temp->left;
              }
          }
        }
    cout<<"Tree does not contain this node"<<endl;
    return false;
}

void BinarySearchTree::insert(int d)
{
    tree_node* t = new tree_node;
    tree_node* parent;
    t->data = d;
    t->left = NULL;
    t->right = NULL;
    parent = NULL;

  if(isEmpty()) root = t;
  else
  {
    tree_node* curr;
    curr = root;
    // Find the Node's parent
    while(curr)
    {
        parent = curr;
        if(t->data > curr->data) curr = curr->right;
        else curr = curr->left;
    }

    if(t->data < parent->data)
       parent->left = t;
    else
       parent->right = t;
  }
}

//----------------------------------------------------

int main()
{
    BinarySearchTree b;
    int ch,tmp,tmp1,tmp2;
    while(1)
    {
       cout<<endl<<endl;
       cout<<" Binary Search Tree Operations "<<endl;
       cout<<" ----------------------------- "<<endl;
       cout<<" 1. Insertion/Creation "<<endl;
       cout<<" 2. Does Binary Searching Tree contains this node? "<<endl;
       cout<<" 3. Exit "<<endl;
       cout<<" Enter your choice : ";
       cin>>ch;
       switch(ch)
       {
           case 1 : cout<<" Enter Number to be inserted : ";
                    cin>>tmp;
                    b.insert(tmp);
                    break;
           case 2 : cout<<" Enter data to be found : ";
                    cin>>tmp;
                    b.search(tmp);
                    break;
           case 3 : system("pause");
                    return 0;
                    break;
       }
    }
}

我试图重写它：

#include <process.h> 
#include <conio.h>
#include <iostream>
#include <cstdlib>

using namespace std;

template <class T>
class BinarySearchTree
{
    private:
        struct tree_node
        {
           tree_node* left;
           tree_node* right;
           T data;
        };
        tree_node* root;
    public:
        BinarySearchTree<T>()
        {
           root = NULL;
        }

        T isEmpty() const { return root==NULL; }
        T insert(T);
        T search(T);

};

//----------------------------------------------------

template <class T>T BinarySearchTree<T>::search(T d)
{
    tree_node* temp = root;
    while (temp != NULL)
        {
         if (temp->data == d)
          {
            cout<<"Tree contains this node"<<endl;
            return true;
          }
        else
          {
            if (d > temp->data)
              {
                temp = temp->right;
              }
            else
              {
                temp = temp->left;
              }
          }
        }
    cout<<"Tree does not contain this node"<<endl;
    return false;
}


template <class T>T BinarySearchTree<T>::insert(T d)
{
    tree_node* t = new tree_node;
    tree_node* parent;
    t->data = d;
    t->left = NULL;
    t->right = NULL;
    parent = NULL;

  if(isEmpty()) root = t;
  else
  {
    tree_node* curr;
    curr = root;

    while(curr)
    {
        parent = curr;
        if(t->data > curr->data) curr = curr->right;
        else curr = curr->left;
    }

    if(t->data < parent->data)
       parent->left = t;
    else
       parent->right = t;
  }
}

//----------------------------------------------------

int main()
{
    BinarySearchTree b;
    int ch,tmp,tmp1,tmp2;
    while(1)
    {
       cout<<endl<<endl;
       cout<<" Binary Search Tree Operations "<<endl;
       cout<<" ----------------------------- "<<endl;
       cout<<" 1. Insertion/Creation "<<endl;
       cout<<" 2. Does Binary Searching Tree contains this node?"<<endl;
       cout<<" 3. Exit "<<endl;
       cout<<" Enter your choice : ";
       cin>>ch;
       switch(ch)
       {
           case 1 : cout<<" Enter Number to be inserted : ";
                    cin>>tmp;
                    b.insert(tmp);
                    break;
           case 2 : cout<<" Enter data to be found : ";
                    cin>>tmp;
                    b.search(tmp);
                    break;
           case 3 : system("pause");
                    return 0;
                    break;
       }
    }
}
4

2 回答 2

3

错误是显式的，你需要给它一个模板参数，例如：

BinarySearchTree<int> b;
于 2014-06-24T03:55:25.727 回答
1

除了模板实例化问题，我还可以看到其他问题。

  1. 如果您使用 insert 方法添加一个已经在树中的值会发生什么。它将在右侧添加一个新节点。从 BST 概念来看，这是错误的。

  2. Insert 方法实际上根本不返回任何东西。

于 2014-06-24T04:18:48.837 回答