Code Bye

一个很简单的问题类模版

#ifndef _BINARY_SEARCH_TREE_H_
#define _BINARY_SEARCH_TREE_H_
template <typename Comparable>
class BinarySearchTree{
	public:
		BinarySearchTree();
		BinarySearchTree(const BinarySearchTree* rhs);
		~BinarySearchTree();

		const Comparable & findMax() const;
		const Comparable & findMin() const;
		bool contains(const Comparable & x) const;
		bool isEmpty() const;
		void printTree() const;

		void makeEmpty();
		void insert(const Comparable & x);
		void remove(const Comparable & x);

		const BinarySearchTree & operator =(const BinarySearchTree & rhs);
	private:
		struct BinaryNode{
			Comparable element;
			BinaryNode* left;
			BinaryNode* right;

			BinaryNode(const Comparable & theElement,BinaryNode *lt,BinaryNode *rt)
				:element(theElement),left(lt),right(rt){}
		};

		BinaryNode* root;

		void insert(const Comparable & x, BinaryNode * & t)const;
		void remove(const Comparable & x, BinaryNode * & t)const;
		const BinaryNode * findMax(BinaryNode * t) const;
		const BinaryNode * findMin(BinaryNode * t) const;
		bool contains(const Comparable & x,BinaryNode* t) const;
		void makeEmpty(BinaryNode* &t);
		void printTree(BinaryNode* t) const;
		BinaryNode* clone(BinaryNode* t)const;
};
//出错函数如下:
template <typename Comparable>
bool BinarySearchTree<Comparable>::contains(const Comparable & x , BinarySearchTree<Comparable>::BinaryNode* t) const
{
	if(t == NULL) return false;
	else if(x < t->element)
		return contains(x,t->left);
	else if(x > t->element)
		return contains(x,t->right);
	else return true;
}
template <typename Comparable>
BinaryNode* BinarySearchTree<Comparable>::clone(BinarySearchTree<Comparable>::BinaryNode* t)const
{
	if(t ==NULL) reutrn NULL;
	return new BinaryNode(t->element,clone(t->left),clone(t->right));
}
template <typename Comparable>
const BinarySearchTree& BinarySearchTree<Comparable>::operator =(const BinarySearchTree& rhs)
{
	if(this != &rhs)
	{
		makeEmpty();
		root = clone(rhs.root);
	}
	return *this;
}
template <typename Comparable>
void BinarySearchTree<Comparable>::insert(const Comparable & x, BinarySearchTree<Comparable>::BinaryNode * & t)
{
	if(t==NULL)
		t = new BinaryNode(x,NULL,NULL);
	else if(x < t->element)
		insert(x,t->left);
	else if(x > t->element)
		insert(x,t->right);
	else 
		return ;
}
template <typename Comparable>
void BinarySearchTree<Comparable>::remove(const Comparable & x,BinarySearchTree<Comparable>::BinaryNode * & t)
{
	if(t==NULL)
		return ;
	if(x < t->element)
		remove(x,t->left);
	else if(x > t->element)
		remove(x,t->right);
	else if(t->left !=NULL && t->right != NULL)
	{
		t->element = findMin(t->right)->element;
		remove(t->element,t->right);
	} 
	else
	{
		BinaryNode* oldNode = t;
		t=(t->left != NULL) ? t->left : t->right
		delete oldNode;
	}
}
template <typename Comparable>
const BinarySearchTree<Comparable>::BinaryNode * BinarySearchTree<Comparable>::findMax(BinaryNode * t) const
{
	if(t == NULL) return NULL;
	if(t->right == NULL) return t;
	return findMin(t->right);
}
template <typename Comparable>
const BinarySearchTree<Comparable>::BinaryNode * BinarySearchTree<Comparable>::findMin(BinaryNode * t) const
{
	if(t == NULL) return NULL;
	if(t->left == NULL) return t;
	return findMin(t->left);
}
g++ -c -I./ binarysearchtree.cpp
binarysearchtree.cpp:42:6: error: prototype for ‘bool BinarySearchTree<Comparable>::contains(const Comparable&, BinarySearchTree<Comparable>::BinaryNode*) const’ does not match any in class ‘BinarySearchTree<Comparable>’
 bool BinarySearchTree<Comparable>::contains(const Comparable & x , BinarySearchTree<Comparable>::BinaryNode* t) const
      ^
binarysearchtree.h:38:8: error: candidates are: bool BinarySearchTree<Comparable>::contains(int) const
   bool contains(const Comparable & x,BinaryNode* t) const;
        ^
binarysearchtree.cpp:17:6: error:                 bool BinarySearchTree<Comparable>::contains(const Comparable&) const
 bool BinarySearchTree<Comparable>::contains(const Comparable & x) const
      ^
binarysearchtree.cpp:53:7: error: need ‘typename’ before ‘BinarySearchTree<Comparable>::BinaryNode’ because ‘BinarySearchTree<Comparable>’ is a dependent scope
 const BinarySearchTree<Comparable>::BinaryNode * BinarySearchTree<Comparable>::findMax(BinaryNode * t) const
       ^
binarysearchtree.cpp:61:7: error: need ‘typename’ before ‘BinarySearchTree<Comparable>::BinaryNode’ because ‘BinarySearchTree<Comparable>’ is a dependent scope
 const BinarySearchTree<Comparable>::BinaryNode * BinarySearchTree<Comparable>::findMin(BinaryNode * t) const
       ^
binarysearchtree.cpp:69:6: error: prototype for ‘void BinarySearchTree<Comparable>::insert(const Comparable&, BinarySearchTree<Comparable>::BinaryNode*&)’ does not match any in class ‘BinarySearchTree<Comparable>’
 void BinarySearchTree<Comparable>::insert(const Comparable & x, BinarySearchTree<Comparable>::BinaryNode * & t)
      ^
binarysearchtree.h:34:8: error: candidates are: void BinarySearchTree<Comparable>::insert(const Comparable&, BinarySearchTree<Comparable>::BinaryNode*&) const
   void insert(const Comparable & x, BinaryNode * & t)const;
        ^
binarysearchtree.cpp:23:6: error:                 void BinarySearchTree<Comparable>::insert(const Comparable&)
 void BinarySearchTree<Comparable>::insert(const Comparable & x)
      ^
binarysearchtree.cpp:82:6: error: prototype for ‘void BinarySearchTree<Comparable>::remove(const Comparable&, BinarySearchTree<Comparable>::BinaryNode*&)’ does not match any in class ‘BinarySearchTree<Comparable>’
 void BinarySearchTree<Comparable>::remove(const Comparable & x,BinarySearchTree<Comparable>::BinaryNode * & t)
      ^
binarysearchtree.h:35:8: error: candidates are: void BinarySearchTree<Comparable>::remove(const Comparable&, BinarySearchTree<Comparable>::BinaryNode*&) const
   void remove(const Comparable & x, BinaryNode * & t)const;
        ^
binarysearchtree.cpp:29:6: error:                 void BinarySearchTree<Comparable>::remove(const Comparable&)
 void BinarySearchTree<Comparable>::remove(const Comparable & x)
      ^
binarysearchtree.cpp:121:1: error: ‘BinaryNode’ does not name a type
 BinaryNode* BinarySearchTree<Comparable>::clone(BinarySearchTree<Comparable>::BinaryNode* t)const
 ^
binarysearchtree.cpp:128:7: error: invalid use of template-name ‘BinarySearchTree’ without an argument list
 const BinarySearchTree& BinarySearchTree<Comparable>::operator =(const BinarySearchTree& rhs)

怎么样搞定这个 错误?

解决方案

20

#ifndef _BINARY_SEARCH_TREE_H_
#define _BINARY_SEARCH_TREE_H_
template <typename Comparable>
class BinarySearchTree{
public:
    BinarySearchTree();
    BinarySearchTree(const BinarySearchTree* rhs);
    ~BinarySearchTree();
    const Comparable & findMax() const;
    const Comparable & findMin() const;
    bool contains(const Comparable & x) const;
    bool isEmpty() const;
    void printTree() const;
    void makeEmpty();
    void insert(const Comparable & x);
    void remove(const Comparable & x);
    const BinarySearchTree & operator =(const BinarySearchTree & rhs);
    struct BinaryNode{
        Comparable element;
        BinaryNode* left;
        BinaryNode* right;
        BinaryNode(const Comparable & theElement, BinaryNode *lt, BinaryNode *rt)
            :element(theElement), left(lt), right(rt){}
    };
private:
    
    BinaryNode* root;
    void insert(const Comparable & x, BinaryNode * & t)const;
    void remove(const Comparable & x, BinaryNode * & t)const;
    const BinaryNode * findMax(BinaryNode * t) const;
    const BinaryNode * findMin(BinaryNode * t) const;
    bool contains(const Comparable & x, BinaryNode* t) const;
    void makeEmpty(BinaryNode* &t);
    void printTree(BinaryNode* t) const;
    BinaryNode* clone(BinaryNode* t)const;
};
//出错函数如下:
template <typename Comparable>
bool BinarySearchTree<Comparable>::contains(const Comparable & x, typename BinarySearchTree<Comparable>::BinaryNode* t) const
{
    if (t == NULL) return false;
    else if (x < t->element)
        return contains(x, t->left);
    else if (x > t->element)
        return contains(x, t->right);
    else return true;
}
template <typename Comparable>
typename BinarySearchTree<Comparable>::BinaryNode* BinarySearchTree<Comparable>::clone(typename BinarySearchTree<Comparable>::BinaryNode* t)const
{
    if (t ==NULL) reutrn NULL;
    return new BinaryNode(t->element, clone(t->left), clone(t->right));
}
template <typename Comparable>
const BinarySearchTree<Comparable>& BinarySearchTree<Comparable>::operator =(const BinarySearchTree& rhs)
{
    if (this != &rhs)
    {
        makeEmpty();
        root = clone(rhs.root);
    }
    return *this;
}
template <typename Comparable>
void BinarySearchTree<Comparable>::insert(const Comparable & x, typename BinarySearchTree<Comparable>::BinaryNode * & t) const
{
    if (t==NULL)
        t = new BinaryNode(x, NULL, NULL);
    else if (x < t->element)
        insert(x, t->left);
    else if (x > t->element)
        insert(x, t->right);
    else
        return;
}
template <typename Comparable>
void BinarySearchTree<Comparable>::remove(const Comparable & x, typename BinarySearchTree<Comparable>::BinaryNode * & t) const
{
    if (t==NULL)
        return;
    if (x < t->element)
        remove(x, t->left);
    else if (x > t->element)
        remove(x, t->right);
    else if (t->left !=NULL && t->right != NULL)
    {
        t->element = findMin(t->right)->element;
        remove(t->element, t->right);
    }
    else
    {
        BinaryNode* oldNode = t;
        t = (t->left != NULL) ? t->left : t->right
            delete oldNode;
    }
}
template <typename Comparable>
const typename BinarySearchTree<Comparable>::BinaryNode * BinarySearchTree<Comparable>::findMax(BinaryNode * t) const
{
    if (t == NULL) return NULL;
    if (t->right == NULL) return t;
    return findMin(t->right);
}
template <typename Comparable>
const typename BinarySearchTree<Comparable>::BinaryNode * BinarySearchTree<Comparable>::findMin(BinaryNode * t) const
{
    if (t == NULL) return NULL;
    if (t->left == NULL) return t;
    return findMin(t->left);
}
#endif

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明一个很简单的问题类模版