C++ 模板编译错误

getmonyinfo

这是一个模板类，实现最简单的二叉查找树，报错如下:

bst.cpp: In member function ‘void BinarySearchTree<T>::makeEmpty() const [with T = char]’:
bst.cpp:19:   instantiated from ‘BinarySearchTree<T>::~BinarySearchTree() [with T = char]’
bst.cpp:154:   instantiated from here
bst.cpp:29: error: no matching function for call to ‘BinarySearchTree<char>::makeEmpty(BinarySearchTree<char>::BinaryNode* const&) const’
bst.cpp:29: note: candidates are: void BinarySearchTree<T>::makeEmpty() const [with T = char]
bst.cpp:129: note:                 void BinarySearchTree<T>::makeEmpty(BinarySearchTree<T>::BinaryNode*&) const [with T = char]



代码

1. #include <iostream>
   
2. #include <string>
   
3. 
   
4. template <class T>
   
5. class BinarySearchTree
   
6. {
   
7.         public:
   
8.                 BinarySearchTree () : root (NULL) { }
   
9.                 BinarySearchTree (const BinarySearchTree &rhs) { root = clone  (rhs.root); }
   
10.                 const BinarySearchTree &operator= (const BinarySearchTree &rhs)
    
11.                 {
    
12.                         if (this != &rhs)
    
13.                         {
    
14.                                 makeEmpty ();
    
15.                                 root = clone (rhs.root);
    
16.                         }
    
17.                         return *this;
    
18.                 }
    
19.                 ~BinarySearchTree () {        makeEmpty (); }
    
20. 
    
21.                 void insert (const T &x) { insert (x, root); }
    
22.                 void remove (const T &x) { remove (x, root); }
    
23. 
    
24.                 const T &findMax () const { findMax (root); }
    
25.                 const T &findMin () const { findMin (root); }
    
26. 
    
27.                 bool contains (const T &x) const { return container (x, root); }
    
28.                 bool isEmpty () const { return (root != NULL); }
    
29.                 void makeEmpty () const { makeEmpty (root); }
    
30.                 void printTree () const { printTree (root); }
    
31.                
    
32.         private:
    
33.                 struct BinaryNode
    
34.                 {
    
35.                         T data;
    
36.                         BinaryNode *left;
    
37.                         BinaryNode *right;
    
38.                         BinaryNode (const T &elem, BinaryNode *lt, BinaryNode *rt) : data (elem), left (0), right (0) { }
    
39.                 };
    
40. 
    
41.                 BinaryNode *root;
    
42.                 void insert (const T &x, BinaryNode *&t) const;
    
43.                 void remove (const T &x, BinaryNode *&t) const;
    
44.                 BinaryNode *findMax (BinaryNode *t) const;
    
45.                 /*
    
46.                 {
    
47.                         if (t)
    
48.                                 while (t->right)
    
49.                                         t = t->right;
    
50.                         return t;
    
51.                 }*/
    
52.                 BinaryNode *findMin (BinaryNode *t) const
    
53.                 {
    
54.                         if (t == NULL)
    
55.                                 return NULL;
    
56.                         if (t->left == NULL)
    
57.                                 return NULL;
    
58.                         return findMin (t->left);
    
59.                 }
    
60.                 BinaryNode *clone (BinaryNode *t) const
    
61.                 {
    
62.                         if (t == NULL)
    
63.                                 return NULL;
    
64.                         return new BinaryNode (t->data, clone(t->left), clone(t->right));
    
65.                 }
    
66.                 bool contains (const T &x, BinaryNode *t) const;
    
67.                 void makeEmpty (BinaryNode *&t) const;
    
68.                 void printTree (BinaryNode *t) const;
    
69. 
    
70. };
    
71. 
    
72. template <class T>
    
73. void BinarySearchTree<T>::insert (const T &x, BinaryNode *&t) const
    
74. {
    
75.         if (t == NULL)
    
76.                 t = new BinaryNode (x, NULL, NULL);
    
77.         else if (x < t->data)
    
78.                 insert (x, t->left);
    
79.         else if (x > t->data)
    
80.                 insert (x, t->right);
    
81.         else
    
82.                 ;//same value , do nothing
    
83. }
    
84. 
    
85. template <class T>
    
86. void BinarySearchTree<T>::remove (const T &x, BinaryNode *&t) const
    
87. {
    
88.         if (t == NULL)
    
89.                 return;
    
90.         if (x < t->data)
    
91.                 remove (x, t->left);
    
92.         else if (x > t->data)
    
93.                 remove (x, t->right);
    
94.         else if (t->left && t->right)        //Two children
    
95.         {
    
96.                 t->data = findMin (t->right)->data;
    
97.                 remove(t->data, t->right);
    
98.         }
    
99.         else
    
100.         {
     
101.                 BinaryNode *oldNode = t;
     
102.                 t = (t->left) ? t->left : t->right;
     
103.                 delete t;
     
104.         }
     
105. }
     
106. template <class T>
     
107. struct BinarySearchTree<T>::BinaryNode *BinarySearchTree<T>::findMax (BinaryNode *t) const
     
108. {
     
109.         if (t)
     
110.                 while (t->right)
     
111.                         t=t->right;
     
112.         return t;
     
113. }
     
114. 
     
115. 
     
116. template <class T>
     
117. bool BinarySearchTree<T>::contains (const T &x, BinaryNode *t) const
     
118. {
     
119.         if (t == NULL)
     
120.                 return false;
     
121.         else if (x < t->data)
     
122.                 return contains (x, t->left);
     
123.         else if (x > t->data)
     
124.                 return contains (x, t->right);
     
125.         return true;
     
126. }
     
127. 
     
128. template <class T>
     
129. void BinarySearchTree<T>::makeEmpty (BinaryNode *&t) const
     
130. {
     
131.         if (t != NULL)
     
132.         {
     
133.                 makeEmpty (t->left);
     
134.                 makeEmpty (t->right);
     
135.                 delete t;
     
136.         }
     
137.         t = NULL;        //
     
138. }
     
139. 
     
140. template <class T>
     
141. void BinarySearchTree<T>::printTree (BinaryNode *t) const
     
142. {
     
143.         std::cout << "LNR" << std::endl;
     
144.         if (t != NULL)
     
145.         {
     
146.                 printTree (t->left);
     
147.                 std::cout << " " << t->data;
     
148.                 printTree (t->right);
     
149.         }
     
150. }
     
151. 
     
152. int main ()
     
153. {
     
154.         BinarySearchTree<char> bst;
     
155.         bst.insert ('F');
     
156.         bst.insert ('B');
     
157.         bst.insert ('G');
     
158.         bst.insert ('A');
     
159.         bst.insert ('D');
     
160.         bst.insert ('I');
     
161.         bst.insert ('C');
     
162.         bst.insert ('E');
     
163.         bst.insert ('H');
     
164.         //bst.isEmpty ();
     
165. 
     
166.         bst.printTree ();
     
167.         return 0;
     
168. }
     

复制代码

bruceteen

struct BinarySearchTree<T>::BinaryNode *BinarySearchTree<T>::findMax (BinaryNode *t) const
改为
typename BinarySearchTree<T>::BinaryNode* BinarySearchTree<T>::findMax( BinaryNode* t ) const

void makeEmpty () const { makeEmpty (root); }
改为
void makeEmpty() { makeEmpty(root); }