谢谢你看这个。我知道我遗漏了一些非常明显的东西，但是我已经被这个错误困住了两个小时了。基本上，当我编译我的类时，这就是返回的内容：
生成文件
全部：主要测试
主：testbintree.cpp bintree.cpp bintree.h treenode.h g++ -o main testbintree.cpp
调用“制作”：
g++ -o test bintree.cpp
bintree.cpp:2:1: error: ‘BinTree’ does not name a type
bintree.cpp:8:1: error: expected unqualified-id before ‘template’
bintree.cpp:16:1: error: ‘BinTree’ does not name a type
bintree.cpp:21:1: error: expected unqualified-id before ‘template’
bintree.cpp:43:13: error: expected initializer before ‘<’ token
bintree.cpp:73:13: error: expected initializer before ‘<’ token
bintree.cpp:117:11: error: expected initializer before ‘<’ token
bintree.cpp:131:11: error: expected initializer before ‘<’ token
bintree.cpp:143:11: error: expected initializer before ‘<’ token
bintree.cpp:168:11: error: expected initializer before ‘<’ token
bintree.cpp:193:13: error: expected initializer before ‘<’ token
bintree.cpp:202:13: error: expected initializer before ‘<’ token
bintree.cpp:210:13: error: expected initializer before ‘<’ token
bintree.cpp:218:1: error: ‘string’ in namespace ‘std’ does not name a type
bintree.cpp:225:1: error: expected unqualified-id before ‘template’
bintree.cpp:255:1: error: ‘TreeNode’ does not name a type
bintree.cpp:275:1: error: expected unqualified-id before ‘template’
bintree.cpp:288:1: error: ‘TreeNode’ does not name a type
bintree.cpp:308:1: error: expected unqualified-id before ‘template’
bintree.cpp:316:13: error: expected initializer before ‘<’ token
make: *** [test] Error 1
二进制树.cpp
template <class T>
BinTree<T>::BinTree()
{
thesize = 0; // set the size to zero
root = NULL; // root pointer to NULL
}
template <class T>
BinTree<T>::BinTree(const BinTree<T>& source)
{
root = copy(source.root, NULL); // copy all the values in source
thesize = source.thesize; // copy the size
}
template <class T>
BinTree<T>::~BinTree()
{
dealloc(root); // delete all the values in the tree
}
template <class T>
T* BinTree<T>::Search(T& x)
{
TreeNode<T>* cur = root; // set current to the root of the tree
if(!cur)
throw EmptyTreeError(); // if there was no root, throw an exception
while(cur) // while current isn't null
{
if(*(cur->item) == x) // check to see if current is the key that is being searched for
return cur->item; // return if so
else if(x < *(cur->item)) // otherwise, compare the current key with x
cur = cur->left; // and go in the correct direction
else
cur = cur->right;
}
throw ValueNotFoundError(); // if current got to NULL, then the value was not in the tree
}
template <class T>
void BinTree<T>::Insert(T* x)
{
TreeNode<T>* curPar = NULL; // current parent;
TreeNode<T>* cur = root; // current node;
while(cur) // while current isn't null
{
curPar = cur; // set the current equal to the current parent in case the loop breaks
if(*x < *(cur->item)) // compare the current key with x
cur = cur->left; // then go in the correct direction
else
cur = cur->right;
}
// create the new TreeNode that will be inserted
TreeNode<T>* in = new TreeNode<T>(x, NULL, NULL, curPar);
if(!curPar) // if current parent was NULL...
root = in; // we have had an empty tree, so set in to the root
else if(*(in->item) < *(curPar->item)) // then just check which child in should be
curPar->left = in;
else
curPar->right = in;
thesize++; // increment the size
}
template <class T>
void BinTree<T>::Delete(T& x)
{
TreeNode<T>* y;
TreeNode<T>* w; // y = new node to delete, x = the replacement child
TreeNode<T>* z = NodeSearch(x); // original node to delete
if(!(z->left && z->right)) // decide which case we're dealing with
y = z;
else
{
// Since Search returns a T* instead of a Node, this is a quick alternative to writing a
// NodeSuccessor/Predecessor, although it does add in another log(n) time operation.
y = NodeSearch(*Successor(*(z->item)));
}
// Find the replacement child (either left/right can be picked first, doesn't matter)
if(y->left)
w = y->left;
else
w = y->right;
if(w) // if x is not NULL...
w->parent = y->parent; // change x's parent to y's parent
// Now assign the parent of y to point to x in the correct direction
if(!y->parent) // if y does not have a parent
root = w; // then you must be replacing the root
else
{
if(y == y->parent->left) // otherwise check which child y was...
y->parent->left = w; // and then set y's parents pointer to x
else
y->parent->right = w;
}
if(y != z) // swap the data if we we're in case 3
z->item = y->item;
delete y; // now finally delete y
thesize--; // decrement size
}
template <class T>
T* BinTree<T>:: Maximum()
{
TreeNode<T>* cur = root; // set current equal to the root
while(cur->right) // while you can go right, keep going
cur = cur->right;
if(cur) // if you found a valid key, return it
return cur->item;
else
throw EmptyTreeError(); // otherwise the tree was empty, throw an exception
}
template <class T>
T* BinTree<T>:: Minimum() // similar algorithm for minimum
{
TreeNode<T>* cur = root;
while(cur->left)
cur = cur->left;
if(cur)
return cur->item;
throw EmptyTreeError();
}
template <class T>
T* BinTree<T>::Successor(T& x)
{
TreeNode<T>* cur = NodeSearch(x); // first search for the node with key x
if(cur->right) // if it has a right subtree...
{
cur = cur->right; // go the root of that subtree
while(cur->left) // then search for the smallest key
cur = cur->left;
return cur->item; // return the key when you find it
}
else // if current did not have a right subtree...
{
// search for the lowest ancestor of current whose left subtree contains current
while(cur->parent && cur != cur->parent->left)
cur = cur->parent;
if(cur->parent) // if you found it, return it
return cur->parent->item;
else
throw NoSuccessorFoundError(); // otherwise there is no successor; throw an exception
}
}
template <class T>
T* BinTree<T>::Predecessor(T& x) // similar algorithm to successor
{
TreeNode<T>* cur = NodeSearch(x);
if(cur->left)
{
cur = cur->left;
while(cur->right)
cur = cur->right;
return cur->item;
}
else
{
while(cur->parent && cur != cur->parent->right)
cur = cur->parent;
if(cur->parent)
return cur->parent->item;
else
throw NoPredecessorFoundError();
}
}
// All traversals rely on the helper method (along with str)
template <class T>
void BinTree<T>::InOrder()
{
std::stringstream s;
traverseHelp(s, root, 1);
std::cout << s.str() << std::endl;
}
template <class T>
void BinTree<T>::PreOrder()
{
std::stringstream s;
traverseHelp(s, root, 0);
std::cout << s.str() << std::endl;
}
template <class T>
void BinTree<T>::PostOrder()
{
std::stringstream s;
traverseHelp(s, root, 2);
std::cout << s.str() << std::endl;
}
template <class T>
std::string BinTree<T>::str(int x)
{
std::stringstream s;
traverseHelp(s, root, x);;
return s.str();
}
template <class T>
void BinTree<T>::traverseHelp(std::stringstream &s, TreeNode<T>* cur, int order)
{
if(cur) // if we have not hit a null value...
{
// check order for the correct traversal, and perform that traversal
if(!order)
{
s << *(cur->item) << " ";
traverseHelp(s, cur->left, order);
traverseHelp(s, cur->right, order);
}
else if(order == 1)
{
traverseHelp(s, cur->left, order);
s << *(cur->item) << " ";
traverseHelp(s, cur->right, order);
}
else
{
traverseHelp(s, cur->left, order);
traverseHelp(s, cur->right, order);
s << *(cur->item) << " ";
}
}
}
// Same as search, except returns a node.
template <class T>
TreeNode<T>* BinTree<T>::NodeSearch(T& x)
{
TreeNode<T>* cur = root;
if(!cur)
throw EmptyTreeError();
while(cur)
{
if(*(cur->item) == x)
return cur;
else if(x < *(cur->item))
cur = cur->left;
else
cur = cur->right;
}
throw ValueNotFoundError();
}
template <class T>
void BinTree<T>::dealloc(TreeNode<T>* x)
{
if(x) // if not NULL
{
dealloc(x->left); // deallocate the left and right
dealloc(x->right);
delete x; // then delete the current node
}
}
template <class T>
TreeNode<T>* BinTree<T>::copy(TreeNode<T>* curSource, TreeNode<T>* prevPar)
{
if(curSource) // if curSource is not NULL
{
// create the copy of the current source node
TreeNode<T>* newNode = new TreeNode<T>(curSource->item, NULL, NULL, prevPar);
newNode->left = copy(curSource->left, newNode); // set its right and left recursively
newNode->right = copy(curSource->right, newNode);
return newNode; // then return the new node
}
else
return NULL; // return NULL so the leaves' children can be set correctly
}
//********** methods required just for the sort **********************
//***Note the unit test is essentially the sorting program
// Both methods work like InOrder
template <class T>
void BinTree<T>::arrayInOrder(T A[])
{
int x = 0;
sortTraverse(root, A, x);
}
template <class T>
void BinTree<T>::sortTraverse(TreeNode<T>* cur, T A[], int& index)
{
if(cur)
{
sortTraverse(cur->left, A, index);
A[index] = *(cur->item);
index++;
sortTraverse(cur->right, A, index);
}
}
宾树.h
#ifndef BINTREE_H_
#define BINTREE_H_
#include "treenode.h"
#include<iostream>
#include<sstream>
template <class T>
class BinTree
{
TreeNode<T>* root; // root of the tree
int thesize; // int instead of size_t so that comparison with indices is less error-prone
public:
// Constructs an empty binary tree.
// post: an empty binary tree has been constructed.
BinTree();
// Constructs a binary search with with the same T*s as source
// post: a binary search tree has been construced that is identical to source
BinTree(const BinTree<T>& source);
// Deconstructs the binary tree.
// post: the binary tree has been deconstructed
~BinTree();
// Returns true if the tree is empty, returns false otherwise.
// post: The bool indicating whether or not the tree is empty is returned.
bool isEmpty() { return !root;}
// Returns the first T with the same key value as x.
// pre: x is of type T that has overloaded comparison operators; a T with key x is in the tree.
// post: A pointer to the first T with the same key value as x is returned.
T* Search(T& x);
// Inserts x into the binary tree.
// pre: x is of type T that has overloaded comparison operators.
// post: x has been inserted into its proper place in the tree.
void Insert(T* x);
// Deletes the first T with the same key value as x.
// pre: x is of type T that has overloaded comparison operators.
// post: The node containing the T with the same key value as x is now deleted.
void Delete(T& x);
// Returns the maximum of the binary search tree.
// pre: the tree must contain at least one value.
// post: the T* with the maximum key is returned.
T* Maximum();
// Returns the minimum of the binary search tree.
// pre: the tree must contain at least one value.
// post: the T* with the minimum key is returned.
T* Minimum();
// Returns the successor (next highest value) of x.
// pre: x's key is not the maximum of the tree; x is of type T that has overloaded comparison operators.
// post: a pointer of the T with the key succeding x's key is returned.
T* Successor(T& x);
// Returns predecessor (next lowest value) of x.
// pre: x's key is not the minimum of the tree; x is of type T that has overloaded comparison operators.
// post: a pointer of the T with the key preceding x's key is returned.
T* Predecessor(T& x);
// Prints an in-order traversal of the tree to standard out.
// post: an in-order traversal has been printed.
void InOrder();
// Prints a pre-order traversal of the tree to standard out.
// post: a pre-order traversal has been printed.
void PreOrder();
// Prints a post-order traversal of the tree to standard out.
// post: a post-order traversal has been printed.
void PostOrder();
// Returns a string representing a traversal of the tree.
// x = 0 for pre-order, 1 for in-order, and 2 for post-order.
// pre: 0 <= x <= 2.
// post: the correct traversal of the tree has been returned as a string.
std::string str(int x);
// Returns the length of the binary tree.
// post: the size is returned
int size() { return thesize; }
// Sorts an array A with the same values that are in the tree.
// pre: the keys in the Ts in A must have the same values as A.
// post: A is now in sorted order based on key value.
void arrayInOrder(T A[]) ;
// Does an in-order traversal of the tree and puts the values in array A
// pre: index must start off 0.
// post: A now contains the in-order traversal of the tree
void sortTraverse(TreeNode<T>* cur, T A[], int& index) ;
private:
// Recursive algorithm that traverses the source tree and copies it.
// post: the binary search tree with root curSource has been copied.
TreeNode<T>* copy(TreeNode<T>* curSource, TreeNode<T>* prevPar);
// The exact same as search, except it returns a node to help with methods like delete.
// pre: x is of type T that has overloaded comparison operators; T with key x is in the tree.
// post: the TreeNode containing with item T with has key x is returned.
TreeNode<T>* NodeSearch(T& x);
// Deletes all the nodes in the tree with root x.
// post: the tree with root x has been deleted from memory.
void dealloc(TreeNode<T>* x);
// Helper recursive function that traverses the binary search tree.
// x = 0 for pre-order, 1 for in-order, and 2 for post-order.
// pre: s must be an empty stringstream, 0 <= x <= 2.
// post: s now contains the correct traversal of the tree.
void traverseHelp(std::stringstream &s, TreeNode<T>* cur, int order);
};
class EmptyTreeError{}; // max and min exception
class ValueNotFoundError{}; // searching exception
class NoSuccessorFoundError{}; // successor exception
class NoPredecessorFoundError{}; // predecessor exception
#include "bintree.cpp" //include this to make the template work
#endif
树节点.h
#ifndef _NODE_H
#define _NODE_H
#include<cstdlib>
template <class T> class BinTree; // so that we can make list a friend... and node knows its a template
template <class T>
class TreeNode
{
friend class BinTree<T>; // allow the binary tre to use the private data of Node
T* item; // item stored in the Node
TreeNode<T>* left; // left pointer
TreeNode<T>* right; // right pointer
TreeNode<T>* parent; // parent pointer
public:
// Constructs a new node, with value item, left pointer ileft, right pointer iright, parent pointer ipar
// post: a new Treenode has been constructed
TreeNode(T* initem = 0, TreeNode<T>* ileft = NULL, TreeNode<T>* iright = NULL, TreeNode<T>* ipar = NULL )
{
item = initem;
left = ileft;
right = iright;
parent = ipar;
}
};
#endif
测试bintree.cpp
# include "bintree.h"
# include<cassert>
//Test to make sure the constructor works (also makes sure that length and str work for empty lists).
void testConstructor()
{
BinTree<int> t;
assert(t.str(1) == "");
assert(t.size() == 0);
}
// Test to make sure insertion works correctly. (along with size)
void testInsertion()
{
BinTree<int> t;
int* a = new int(3);
int* b = new int(2);
int* c = new int(0);
int* d = new int(1);
int* e = new int(5);
int* f = new int(4);
int* g = new int(6);
t.Insert(a);
t.Insert(b);
t.Insert(c);
t.Insert(d);
t.Insert(e);
t.Insert(f);
t.Insert(g);
assert(t.str(1) == "0 1 2 3 4 5 6 ");
assert(t.size() == 7);
delete a, b, c, d, e, f, g;
}
// Test to make sure isEmpty works
void testIsEmpty()
{
BinTree<int> t;
assert(t.isEmpty());
int* a = new int(3);
int* b = new int(2);
t.Insert(a);
t.Insert(b);
assert(!t.isEmpty());
delete a, b;
}
// Test to make sure the copy constructor works in multiple cases.
void testCopyConstructor()
{
BinTree<int> t;
BinTree<int> w(t);
// See if it works for an empty tree
assert(w.str(1) == "");
assert(w.size() == 0);
// Now test copying a more full tree
int* a = new int(3);
int* b = new int(2);
int* c = new int(0);
int* d = new int(1);
int* e = new int(5);
int* f = new int(4);
int* g = new int(6);
t.Insert(a);
t.Insert(b);
t.Insert(c);
t.Insert(d);
t.Insert(e);
t.Insert(f);
t.Insert(g);
BinTree<int> z(t);
assert(z.str(1) == "0 1 2 3 4 5 6 ");
assert(z.size() == 7);
//Now test deleting something and seeing if they are different
int x = 5;
t.Delete(x);
assert(t.str(1) == "0 1 2 3 4 6 ");
assert(z.str(1) == "0 1 2 3 4 5 6 ");
x = 3;
assert(z.Successor(x) == f);
delete a, b, c, d, e, f, g;
}
// Test to make sure that search at least finds the right value
// *Note: Search will be further tested in other methods (delete, max, etc..)
void testSearch()
{
BinTree<int> t;
int* a = new int(3);
int* b = new int(2);
int* c = new int(0);
int* d = new int(1);
int* e = new int(5);
t.Insert(a);
t.Insert(b);
t.Insert(c);
t.Insert(d);
t.Insert(e);
int x = 5;
assert(*(t.Search(x)) == 5 );
delete a, b, c, d, e;
}
// Test to make sure maximum works in multiple cases.
void testMaximum()
{
BinTree<int> t;
int* a = new int(3);
int* b = new int(2);
int* c = new int(0);
int* d = new int(1);
int* e = new int(5);
int* f = new int(4);
int* g = new int(6);
t.Insert(a);
// see if it works for a one element tree
assert(*(t.Maximum()) == 3 );
t.Insert(b);
t.Insert(c);
t.Insert(d);
t.Insert(e);
t.Insert(f);
t.Insert(g);
// see if it works for a more full tree
assert(*(t.Maximum()) == 6);
delete a, b, c, d, e, f, g;
}
// Test to make sure minimum works in multiple cases
void testMinimum()
{
BinTree<int> t;
int* a = new int(3);
int* b = new int(2);
int* c = new int(0);
int* d = new int(1);
int* e = new int(5);
int* f = new int(4);
int* g = new int(6);
t.Insert(a);
// see if it works for a one element tree
assert(*(t.Minimum()) == 3);
t.Insert(b);
t.Insert(c);
t.Insert(d);
t.Insert(e);
t.Insert(f);
t.Insert(g);
// see if it works for a more full tree
assert(*(t.Minimum()) == 0);
delete a, b, c, d, e, f, g;
}
void testPredecessor()
{
BinTree<int> t;
int* a = new int(3);
int* b = new int(2);
int* c = new int(0);
int* d = new int(1);
int* e = new int(5);
int* f = new int(4);
int* g = new int(6);
t.Insert(a);
t.Insert(b);
t.Insert(c);
t.Insert(d);
t.Insert(e);
t.Insert(f);
t.Insert(g);
int x = 3;
assert(*(t.Predecessor(x)) == 2);
x = 1; // this tests the ancestor case
assert(*(t.Predecessor(x)) == 0);
x = 6;
assert(*(t.Predecessor(x)) == 5);
delete a, b, c, d, e, f, g;
}
// Test to make sure successor works in multiple cases
void testSuccessor()
{
BinTree<int> t;
int* a = new int(3);
int* b = new int(2);
int* c = new int(0);
int* d = new int(1);
int* e = new int(5);
int* f = new int(4);
int* g = new int(6);
t.Insert(a);
t.Insert(b);
t.Insert(c);
t.Insert(d);
t.Insert(e);
t.Insert(f);
t.Insert(g);
int x = 3;
assert(*(t.Successor(x)) == 4);
x = 2; // this tests the ancestor case
assert(*(t.Successor(x)) == 3);
x = 5;
assert(*(t.Successor(x)) == 6);
delete a, b, c, d, e, f, g;
}
// Tests delete in multiple cases.
void testDelete()
{
BinTree<int> t;
int* a = new int(3);
int* b = new int(2);
int* c = new int(0);
int* d = new int(1);
int* e = new int(5);
int* f = new int(4);
int* g = new int(6);
t.Insert(a);
t.Insert(b);
t.Insert(c);
t.Insert(d);
t.Insert(e);
t.Insert(f);
t.Insert(g);
int x = 1; // test deleting a leaf
t.Delete(x);
assert(t.str(1) == "0 2 3 4 5 6 ");
x = 2; // test deleting a non-leaf without two nodes
t.Delete(x);
assert(t.str(1) == "0 3 4 5 6 ");
x = 5;
t.Delete(x); // test deleting a node with two children
assert(t.str(1) == "0 3 4 6 ");
delete a, b, c, d, e, f, g;
}
// Test all the traversal functions (using str(), but this also tests the standard out methods, as well).
void testTraversals()
{
BinTree<int> t;
int* a = new int(3);
int* b = new int(2);
int* c = new int(0);
int* d = new int(1);
int* e = new int(5);
int* f = new int(4);
int* g = new int(6);
t.Insert(a);
t.Insert(b);
t.Insert(c);
t.Insert(d);
t.Insert(e);
t.Insert(f);
t.Insert(g);
assert(t.str(0) == "3 2 0 1 5 4 6 ");
assert(t.str(2) == "1 0 2 4 6 5 3 ");
delete a, b, c, d, e, f, g;
}
// Test all the methods together to make sure they linked up right.
void testEverything()
{
BinTree<int> t;
int* a = new int(5);
int* b = new int(3);
int* c = new int(1);
int* d = new int(7);
int* e = new int(9);
int* f = new int(4);
int* g = new int(6);
int* h = new int(2);
int* i = new int(8);
int* j = new int(10);
t.Insert(a);
t.Insert(b);
t.Insert(c);
t.Insert(d);
t.Insert(e);
t.Insert(f);
t.Insert(g);
t.Insert(h);
t.Insert(i);
t.Insert(j);
assert(t.str(1) == "1 2 3 4 5 6 7 8 9 10 ");
int x = 1;
t.Delete(x);
assert(t.str(1) == "2 3 4 5 6 7 8 9 10 ");
x = 7;
t.Delete(x);
assert(t.str(1) == "2 3 4 5 6 8 9 10 ");
x = 5;
t.Delete(x);
assert(t.str(1) == "2 3 4 6 8 9 10 ");
x = 2;
assert(*(t.Successor(x)) == 3);
x = 9;
assert(*(t.Successor(x)) == 10);
x = 8;
assert(*(t.Predecessor(x)) == 6);
x = 4;
assert(*(t.Predecessor(x)) == 3);
delete a, b, c, d, e, f, g, h, i, j;
}
// Test for memory leaks by running testEverything in a big for loop.
void testMemoryLeaks()
{
for(int i = 0; i < 1000000; i++)
testEverything();
}
// Do the tests.
main()
{
testConstructor();
testInsertion();
testIsEmpty();
testSearch();
testMaximum();
testMinimum();
testCopyConstructor();
testPredecessor();
testSuccessor();
testDelete();
testTraversals();
testEverything();
//testMemoryLeaks();
return 0;
}
我知道我在那里有 98%，但我不知道我做错了什么导致了这个错误。谢谢！！！