好的，所以我写了一个二叉搜索树，我把它放在这里，整个代码（不像无论如何都很难在网上找到这个代码......）希望有人能找到我的小错误.
#ifndef MyBSTree_H
#define MyBSTree_H
#include <iostream>
#include <string>
using namespace std;
template <typename T>
class BSTreeNode
{
public:
T m_data;
int m_depth;
BSTreeNode<T>* m_left;
BSTreeNode<T>* m_right;
BSTreeNode(const T& x){m_data = x; m_left = NULL; m_right = NULL;}
BSTreeNode(){m_left = NULL; m_right = NULL;}
BSTreeNode(const T& x, const int& d, BSTreeNode<T>* left, BSTreeNode<T>* right) {m_data = x; m_depth = d; m_left = left; m_right = right;}
};
template <typename T>
class MyBSTree
{
int m_size;
BSTreeNode<T>* root;
public:
~MyBSTree(){clear();}
MyBSTree() : m_size(0), root(NULL) {}
MyBSTree(const MyBSTree<T>& rhs)
{
*this = rhs;
}
const MyBSTree<T>& operator=(const MyBSTree<T>& rhs)
{
root = clone(rhs.root);
m_size = rhs.m_size;
}
int size() const
{
return m_size;
}
bool isEmpty() const
{
return m_size == 0;
}
int height() const
{
return treeHeight(root);
}
const T& findMax() const
{
if(isEmpty())
throw string("Empty!");
BSTreeNode<T>* node = root;
while(node->m_right != NULL)
{node = node->m_right;}
return node->m_data;
}
// Purpose: finds the minimum element in the Tree
// Returns: a const reference to the minimum element
const T& findMin() const
{
if(isEmpty())
throw string("Empty!");
BSTreeNode<T>* node = root;
while(node->m_left != NULL)
{node = node->m_left;}
return node->m_data;
}
int contains(const T& x) const
{
if(isEmpty())
return -1;
BSTreeNode<T>* tmp = root;
BSTreeNode<T>* tmpParent;
while(tmp != NULL)
{
if(tmp->m_data == x)
{
return tmp->m_depth;
}
else
{
tmpParent = tmp;
if(x > tmp->m_data)
tmp = tmp->m_right;
else
tmp = tmp->m_left;
}
}
return -(tmpParent->m_depth);
}
/*** ---- Mutator Operations ---- */
void clear()
{
TClear(root);
m_size = 0;
}
void insert(const T& x)
{
if(root == NULL)
{
root = new BSTreeNode<T>(x);
m_size++;
}
else
{
if(treeInsert(root, x))
{
m_size++;
}
}
}
void remove(const T& x)
{
if(isEmpty())
{
cout<<" This Tree is empty! "<< endl;
return;
}
bool exists = false;
BSTreeNode<T>* child = root;
BSTreeNode<T>* parent;
//check to find the element to remove, if it exists, and stops at it for one of three following steps
while(child != NULL)
{
if(child->m_data == x)
{
exists = true;
break;
}
else
{
parent = child;
if(x > child->m_data)
child = child->m_right;
else
child = child->m_left;
}
}
if(!exists)
{
return;
}
//single child
if((child->m_left == NULL && child->m_right != NULL)|| (child->m_left != NULL
&& child->m_right == NULL))
{
if(child->m_left == NULL && child->m_right != NULL)
{
if(parent->m_left == child)
{
parent->m_left = child->m_right;
delete child;
}
else
{
parent->m_right = child->m_right;
delete child;
}
}
else
{
if(parent->m_left == child)
{
parent->m_left = child->m_left;
delete child;
}
else
{
parent->m_right = child->m_left;
delete child;
}
}
return;
}
//no children, leaf
if( child->m_left == NULL && child->m_right == NULL)
{
if(parent->m_left == child)
parent->m_left = NULL;
else
parent->m_right = NULL;
delete child;
return;
}
//two children
if (child->m_left != NULL && child->m_right != NULL)
{
BSTreeNode<T>* tmp;
tmp = child->m_right;
if((tmp->m_left == NULL) && (tmp->m_right == NULL))
{
child->m_data = tmp->m_data;
delete tmp;
child->m_right = NULL;
}
else
{
if((child->m_right)->m_left != NULL)
{
BSTreeNode<T>* leftChild;
BSTreeNode<T>* leftChildParent;
leftChildParent = child->m_right;
leftChild = (child->m_right)->m_left;
while(leftChild->m_left != NULL)
{
leftChildParent = leftChild;
leftChild = leftChild->m_left;
}
child->m_data = leftChild->m_data;
delete leftChild;
leftChildParent->m_left = NULL;
}
else
{
BSTreeNode<T>* tmp;
tmp = child->m_right;
child->m_data = tmp->m_data;
child->m_right = tmp->m_right;
delete tmp;
}
}
return;
}
}
/*** ---- Output Operations ---- */
void printPreOrder() const
{
PrintPre(root);
}
void PrintPre(const BSTreeNode<T>* node) const
{
if(node != NULL)
{
cout << node->m_data << endl;
PrintPre(node->m_left);
PrintPre(node->m_right);
}
}
void printPostOrder() const
{
PrintPost(root);
}
void PrintPost(const BSTreeNode<T>* node) const
{
if(node != NULL)
{
PrintPost(node->m_left);
PrintPost(node->m_right);
cout<< node->m_data << endl;
}
}
void prettyPrint(const BSTreeNode<T>* t, int pad) const
{
string s(pad, ' ');
if (t == NULL)
cout << endl;
else
{
prettyPrint(t->m_right, pad+4);
cout << s << t->m_data << endl;
prettyPrint(t->m_left, pad+4);
}
}
void print() const
{
prettyPrint(root, 0);
}
};
template <typename T>
void TClear(BSTreeNode<T>* node)
{
if(node==NULL)
return;
if(node->m_right != NULL)
{
TClear(node->m_right);
node->m_right = NULL;
}
if(node->m_left != NULL)
{
TClear(node->m_left);
node->m_left == NULL;
}
if(node->m_right == NULL && node->m_left == NULL)
{
delete node;
node = NULL;
}
return;
}
//function from Dr. Morales, pretty slick
template <typename T>
BSTreeNode<T>* clone(const BSTreeNode<T>* t)
{
if (t == NULL)
return NULL;
else{
return new BSTreeNode<T>(t->m_data, t->m_depth, clone(t->m_left), clone(t->m_right));
}
}
template <typename T>
int treeHeight(BSTreeNode<T>* node)
{
int left = 0;
int right = 0;
int height = 1;
if(node->m_left != NULL){
left += treeHeight(node->m_left);
}
if(node->m_right != NULL){
right += treeHeight(node->m_right);
}
if(left > right)
height += left;
else
height += right;
return height;
}
template <typename T>
bool treeInsert(BSTreeNode<T>* node, const T& x)
{
if(x == node->m_data){
return false;
}
if(x < node->m_data)
{
if(node->m_left == NULL)
{
node->m_left = new BSTreeNode<T>(x);
return true;
}
else
{
return(treeInsert(node->m_left, x));
}
}
if(x > node->m_data)
{
if(node->m_right == NULL)
{
node->m_right = new BSTreeNode<T>(x);
return true;
}
else
{
return(treeInsert(node->m_right, x));
}
}
}
#endif
所以，当使用这个测试器运行时，我目前内存泄漏 360 字节（根据 valgrind）。如果我可以提供其他任何东西来帮助您找到错误，请告诉我。
编辑：它进行了 221 次分配和 196 次释放。
非常感谢这里的帮助！
#include <iostream>
#include "mybstree.h"
using namespace std;
//------------------------------------------------------
void test1()
{
MyBSTree<int> t;
cout << endl << endl << "***** " << "Test #1" << endl;
t.print();
cout << "Tree empty? " << boolalpha << t.isEmpty() << endl;
cout << "--" << endl;
t.insert(7);
t.insert(5);
t.insert(9);
t.insert(4);
t.insert(6);
t.insert(13);
t.insert(10);
t.print();
cout << "Tree empty? " << boolalpha << t.isEmpty() << endl;
cout << "--" << endl;
cout << "height = " << t.height() << endl;
cout << "size = " << t.size() << endl;
cout << "--" << endl;
return;
}
//------------------------------------------------------
void test2()
{
MyBSTree<char> t;
cout << endl << endl << "***** " << "Test #2" << endl;
t.insert('F');
t.insert('A');
t.insert('C');
t.insert('G');
t.insert('B');
t.insert('S');
t.insert('K');
t.insert('U');
t.insert('L');
t.insert('K');
t.print();
cout << "--" << endl;
cout << "Min = " << t.findMin() << endl;
cout << "Max = " << t.findMax() << endl;
return;
}
//------------------------------------------------------
void test3()
{
MyBSTree<string> t;
MyBSTree<string> t2;
cout << endl << endl << "***** " << "Test #3" << endl;
t.insert(string("Paul"));
t.insert(string("John"));
t.insert(string("George"));
t.insert(string("Ringo"));
t.insert(string("Fry"));
t.insert(string("Leela"));
t.insert(string("Zoidberg"));
t.print();
cout << "--" << endl;
cout << "Testing Operator = " << endl;
t2 = t;
t2.print();
cout << "--" << endl;
cout << "Is it a deep copy? " << endl;
t2.remove(string("George"));
t2.remove(string("John"));
t2.remove(string("Ringo"));
cout << "-- copy:" << endl;
t2.print();
cout << "-- original:" << endl;
t.print();
return;
}
//------------------------------------------------------
void test4()
{
MyBSTree<string> t;
cout << endl << endl << "***** " << "Test #4" << endl;
t.insert(string("Pizza"));
t.insert(string("Burger"));
t.insert(string("HotDog"));
t.insert(string("Shake"));
t.insert(string("Fry"));
t.insert(string("Salad"));
t.insert(string("Soda"));
t.print();
cout << "--" << endl;
cout << "Testing Copy COnstructor " << endl;
MyBSTree<string> t2(t);
t2.print();
cout << "--" << endl;
cout << "Is it a deep copy? " << endl;
t2.remove(string("Pizza"));
t2.remove(string("Salad"));
t2.remove(string("Fry"));
cout << "-- copy:" << endl;
t2.print();
cout << "-- original:" << endl;
t.print();
return;
}
void test5()
{
MyBSTree<int> t;
cout << endl << endl << "***** " << "Test #5" << endl;
cout << "Tree empty? " << boolalpha << t.isEmpty() << endl;
cout << "--" << endl;
try {
t.findMin();
}
catch (string errmsg)
{
cout << errmsg << endl;
}
try {
t.findMax();
}
catch (string errmsg)
{
cout << errmsg << endl;
}
return;
}
//------------------------------------------------------
void test6()
{
MyBSTree<int> t;
cout << endl << endl << "***** " << "Test #6" << endl;
cout << "--" << endl;
t.insert(7);
t.insert(5);
t.insert(9);
t.insert(4);
t.insert(6);
t.insert(13);
t.insert(10);
t.print();
cout << "--" << endl;
cout << "Pre Order:" << endl;
t.printPreOrder();
cout << "--" << endl;
cout << "Post Order" << endl;
t.printPostOrder();
return;
}
//------------------------------------------------------
//------------------------------------------------------
//------------------------------------------------------
//------------------------------------------------------
int main ()
{
cout << "Hello Tree Tester!! " << endl;
test1();
test2();
test3();
test4();
test5();
test6();
//cin.ignore();
//cin.get();
return 0;
}
注意：这是我的数据结构课程的家庭作业。我把整个事情都写好了，输出是正确的，只是内存泄漏。
valgrind 日志：
==30750==
==30750== HEAP SUMMARY:
==30750== in use at exit: 714 bytes in 25 blocks
==30750== total heap usage: 221 allocs, 196 frees, 7,533 bytes allocated
==30750==
==30750== 24 bytes in 1 blocks are definitely lost in loss record 3 of 25
==30750== at 0x4C2B1C7: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==30750== by 0x403552: bool treeInsert<int>(BSTreeNode<int>*, int const&) (in /nethome/users/-/-/-/a.out)
==30750== by 0x40358A: bool treeInsert<int>(BSTreeNode<int>*, int const&) (in /nethome/users/-/-/-/a.out)
==30750== by 0x402941: MyBSTree<int>::insert(int const&) (in /nethome/users/-/-/-/a.out)
==30750== by 0x401301: test1() (in /nethome/users/-/-/-/a.out)
==30750== by 0x402723: main (in /nethome/users/-/-/-/a.out)
==30750==
==30750== 24 bytes in 1 blocks are definitely lost in loss record 4 of 25
==30750== at 0x4C2B1C7: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==30750== by 0x4029EB: MyBSTree<char>::insert(char const&) (in /nethome/users/-/-/-/a.out)
==30750== by 0x4014A5: test2() (in /nethome/users/-/-/-/a.out)
==30750== by 0x402728: main (in /nethome/users/-/-/-/a.out)
==30750==
==30750== 24 bytes in 1 blocks are definitely lost in loss record 5 of 25
==30750== at 0x4C2B1C7: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==30750== by 0x403725: bool treeInsert<char>(BSTreeNode<char>*, char const&) (in /nethome/users/-/-/-/a.out)
==30750== by 0x4036FA: bool treeInsert<char>(BSTreeNode<char>*, char const&) (in /nethome/users/-/-/-/a.out)
==30750== by 0x402A2D: MyBSTree<char>::insert(char const&) (in /nethome/users/-/-/-/a.out)
==30750== by 0x4014D3: test2() (in /nethome/users/-/-/-/a.out)
==30750== by 0x402728: main (in /nethome/users/-/-/-/a.out)
==30750==
==30750== 24 bytes in 1 blocks are definitely lost in loss record 6 of 25
==30750== at 0x4C2B1C7: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==30750== by 0x403725: bool treeInsert<char>(BSTreeNode<char>*, char const&) (in /nethome/users/-/-/-/a.out)
==30750== by 0x40375D: bool treeInsert<char>(BSTreeNode<char>*, char const&) (in /nethome/users/-/-/-/a.out)
==30750== by 0x402A2D: MyBSTree<char>::insert(char const&) (in /nethome/users/-/-/-/a.out)
==30750== by 0x401518: test2() (in /nethome/users/-/-/-/a.out)
==30750== by 0x402728: main (in /nethome/users/-/-/-/a.out)
==30750==
==30750== 24 bytes in 1 blocks are definitely lost in loss record 7 of 25
==30750== at 0x4C2B1C7: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==30750== by 0x403552: bool treeInsert<int>(BSTreeNode<int>*, int const&) (in /nethome/users/-/-/-/a.out)
==30750== by 0x40358A: bool treeInsert<int>(BSTreeNode<int>*, int const&) (in /nethome/users/-/-/-/a.out)
==30750== by 0x402941: MyBSTree<int>::insert(int const&) (in /nethome/users/-/-/-/a.out)
==30750== by 0x402623: test6() (in /nethome/users/-/-/-/a.out)
==30750== by 0x40273C: main (in /nethome/users/-/-/-/a.out)
==30750==
==30750== 32 bytes in 1 blocks are definitely lost in loss record 18 of 25
==30750== at 0x4C2B1C7: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==30750== by 0x403BC6: BSTreeNode<std::string>* clone<std::string>(BSTreeNode<std::string> const*) (in /nethome/users/-/-/-/a.out)
==30750== by 0x402D27: MyBSTree<std::string>::operator=(MyBSTree<std::string> const&) (in /nethome/users/-/-/-/a.out)
==30750== by 0x403154: MyBSTree<std::string>::MyBSTree(MyBSTree<std::string> const&) (in /nethome/users/-/-/-/a.out)
==30750== by 0x401FB3: test4() (in /nethome/users/-/-/-/a.out)
==30750== by 0x402732: main (in /nethome/users/-/-/-/a.out)
==30750==
==30750== 48 (24 direct, 24 indirect) bytes in 1 blocks are definitely lost in loss record 19 of 25
==30750== at 0x4C2B1C7: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==30750== by 0x4028FF: MyBSTree<int>::insert(int const&) (in /nethome/users/-/-/-/a.out)
==30750== by 0x40127F: test1() (in /nethome/users/-/-/-/a.out)
==30750== by 0x402723: main (in /nethome/users/-/-/-/a.out)
==30750==
==30750== 48 (24 direct, 24 indirect) bytes in 1 blocks are definitely lost in loss record 20 of 25
==30750== at 0x4C2B1C7: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==30750== by 0x4028FF: MyBSTree<int>::insert(int const&) (in /nethome/users/-/-/-/a.out)
==30750== by 0x4025A1: test6() (in /nethome/users/-/-/-/a.out)
==30750== by 0x40273C: main (in /nethome/users/-/-/-/a.out)
==30750==
==30750== 62 (32 direct, 30 indirect) bytes in 1 blocks are definitely lost in loss record 21 of 25
==30750== at 0x4C2B1C7: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==30750== by 0x402C65: MyBSTree<std::string>::insert(std::string const&) (in /nethome/users/-/-/-/a.out)
==30750== by 0x401D43: test4() (in /nethome/users/-/-/-/a.out)
==30750== by 0x402732: main (in /nethome/users/-/-/-/a.out)
==30750==
==30750== 62 (32 direct, 30 indirect) bytes in 1 blocks are definitely lost in loss record 22 of 25
==30750== at 0x4C2B1C7: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==30750== by 0x4039F3: bool treeInsert<std::string>(BSTreeNode<std::string>*, std::string const&) (in /nethome/users/-/-/-/a.out)
==30750== by 0x402CA7: MyBSTree<std::string>::insert(std::string const&) (in /nethome/users/-/-/-/a.out)
==30750== by 0x401E4B: test4() (in /nethome/users/-/-/-/a.out)
==30750== by 0x402732: main (in /nethome/users/-/-/-/a.out)
==30750==
==30750== 63 (32 direct, 31 indirect) bytes in 1 blocks are definitely lost in loss record 23 of 25
==30750== at 0x4C2B1C7: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==30750== by 0x4039F3: bool treeInsert<std::string>(BSTreeNode<std::string>*, std::string const&) (in /nethome/users/-/-/-/a.out)
==30750== by 0x4039C3: bool treeInsert<std::string>(BSTreeNode<std::string>*, std::string const&) (in /nethome/users/-/-/-/a.out)
==30750== by 0x402CA7: MyBSTree<std::string>::insert(std::string const&) (in /nethome/users/-/-/-/a.out)
==30750== by 0x401DF3: test4() (in /nethome/users/-/-/-/a.out)
==30750== by 0x402732: main (in /nethome/users/-/-/-/a.out)
==30750==
==30750== 94 (32 direct, 62 indirect) bytes in 1 blocks are definitely lost in loss record 24 of 25
==30750== at 0x4C2B1C7: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==30750== by 0x403BC6: BSTreeNode<std::string>* clone<std::string>(BSTreeNode<std::string> const*) (in /nethome/users/-/-/-/a.out)
==30750== by 0x402D27: MyBSTree<std::string>::operator=(MyBSTree<std::string> const&) (in /nethome/users/-/-/-/a.out)
==30750== by 0x401953: test3() (in /nethome/users/-/-/-/a.out)
==30750== by 0x40272D: main (in /nethome/users/-/-/-/a.out)
==30750==
==30750== 185 (32 direct, 153 indirect) bytes in 1 blocks are definitely lost in loss record 25 of 25
==30750== at 0x4C2B1C7: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==30750== by 0x402C65: MyBSTree<std::string>::insert(std::string const&) (in /nethome/users/-/-/-/a.out)
==30750== by 0x4016E3: test3() (in /nethome/users/-/-/-/a.out)
==30750== by 0x40272D: main (in /nethome/users/-/-/-/a.out)
==30750==
==30750== LEAK SUMMARY:
==30750== definitely lost: 360 bytes in 13 blocks
==30750== indirectly lost: 354 bytes in 12 blocks
==30750== possibly lost: 0 bytes in 0 blocks
==30750== still reachable: 0 bytes in 0 blocks
==30750== suppressed: 0 bytes in 0 blocks
==30750==
==30750== For counts of detected and suppressed errors, rerun with: -v
==30750== ERROR SUMMARY: 13 errors from 13 contexts (suppressed: 2 from 2)
注意：我用-/-/-替换了我的个人文件目录信息