c++ - 内存泄漏二叉搜索树

标签 c++

好吧，所以我写了一个二叉搜索树，我把它放在这里，整个代码(反正在网上很难找到这个代码......)希望有人能找到我的小错误。

#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; 
}

注意:这是我的数据结构类(class)的家庭作业。我把整个事情都写好了，输出是正确的，只是内存泄漏。

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)

注意:我把个人文件目录信息换成-/-/-

最佳答案

如果你像这样运行 valgrind

$>valgrind --leak-check=full ./<program_to_run>

您将更好地诊断相应堆栈的泄漏问题。所以运行它并让我们知道结果。

关于c++ - 内存泄漏二叉搜索树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16226950/

上一篇：不同类型的 C++ 模板错误

下一篇：c++实现在dll外部定义的虚拟类，在dll中

相关文章：

C++:如何异步调用同步库调用？

c++ - 非自愿上下文切换的原因

C++ 异或运算符优先级

c++ - 可变参数模板类中的定义数量不同

c++ - Qt qbs 项目设置与库未找到编译错误

c++ - C++隐式转换序列中的三种转换

c++ - 如何检测c++中是否附加了调试器？

c++ - 构造函数初始化

c++ - RAII 和赋值

c# - PresentationFramework.dll 中发生 System.Windows.Markup.XamlParseException'？

©2024 IT工具网  联系我们