Утечки памяти внутри двоичного дерева поиска ⇐ C++

[Anonymous]

Я пытался диагностировать утечки памяти внутри созданного двоичного класса дерева дерева поиска и класса узлов, но я просто спускаю свое мнение. Какие -либо предложения или очевидные выбросы, которые могут предоставить, которые могут предоставить? < /P>
#ifndef BSTREE_H
#define BSTREE_H
#include
#include
#include "BS_Node.h"
#include "Exception.h"
#include "Queue.h"

// Forward declarations for both classes
template
class BSNode;

// Now define BSNode with the friendship
template
class BSTree {
friend class BSNode;
private:
BSNode* root;
BSNode* insertNode(BSNode* node, const T& item);
BSNode* deleteNode(BSNode* node, const T& item);
BSNode* findMin(BSNode* node) const;
void purgeNode(BSNode* node);
int heightNode(BSNode* node) const;
void inOrderNode(BSNode* node, void (*visit)(T data)) const;
void preOrderNode(BSNode* node, void (*visit)(T data)) const;
void postOrderNode(BSNode* node, void (*visit)(T data)) const;
bool containsNode(BSNode* node, const T& item) const;
BSNode* copyTreeNodes(BSNode* node) const;

public:
// Default constructor
BSTree();

// Destructor
~BSTree();

// Copy constructor
BSTree(const BSTree& other);

// Move constructor
BSTree(BSTree&& other) noexcept;

// Copy assignment operator
BSTree& operator=(const BSTree& other);

// Move assignment operator
BSTree& operator=(BSTree&& other) noexcept;

void insert(const T& item);
void remove(const T& item);
void purge();
int height() const;
void inOrder(void (*visit)(T data)) const;
void preOrder(void (*visit)(T data)) const;
void postOrder(void (*visit)(T data)) const;
void breadthFirst(void (*visit)(T data)) const;
bool isEmpty() const;
bool contains(const T& item) const;
BSNode* getRoot() const;
void display(void (*visit)(T data)) const;
};

// Default constructor
template
BSTree::BSTree() : root(nullptr)
{
}

// Destructor
template
BSTree::~BSTree() {
purge();
}

// Copy constructor
template
BSTree::BSTree(const BSTree& other) : root(nullptr)
{
root = copyTreeNodes(other.root);
}

// Move constructor
template
BSTree::BSTree(BSTree&& other) noexcept : root(nullptr)
{
root = other.root;
other.root = nullptr;
}

// Copy assignment operator
template
BSTree& BSTree::operator=(const BSTree& other)
{
if (this != &other)
{
// Clean up existing resources
purge();

// Copy the other tree
root = copyTreeNodes(other.root);
}
return *this;
}

// Move assignment operator
template
BSTree& BSTree::operator=(BSTree&& other) noexcept {
if (this != &other) {
purge(); // Delete existing nodes
root = other.root;
other.root = nullptr;
}
return *this;
}

// Helper method for deep copying tree nodes
template
BSNode* BSTree::copyTreeNodes(BSNode* node) const
{
if (node == nullptr) {
return nullptr;
}

// Create a new node with the same data
BSNode* newNode = new BSNode(node->getData());

// Recursively copy left and right subtrees
newNode->left = copyTreeNodes(node->getLeft());
newNode->right = copyTreeNodes(node->getRight());

return newNode;
}

template
void BSTree::insert(const T& item)
{
root = insertNode(root, item);
}

template
void BSTree::remove(const T& item)
{
root = deleteNode(root, item);
}

template
void BSTree::purge() {
//delete root;
purgeNode(root);
root = nullptr;
}

template
int BSTree::height() const
{
return heightNode(root);
}

template
void BSTree::inOrder(void (*visit)(T data)) const {
if (root == nullptr)
{
throw Exception("Cannot return an empty list");
}
inOrderNode(root, visit);
}

template
void BSTree::preOrder(void (*visit)(T data)) const
{
if (root == nullptr)
{
throw Exception("Cannot return an empty list");
}
preOrderNode(root, visit);
}

template
void BSTree::postOrder(void (*visit)(T data)) const
{
if (root == nullptr)
{
throw Exception("Cannot return an empty list");
}
postOrderNode(root, visit);
}

template
void BSTree::breadthFirst(void (*visit)(T data)) const
{
if (root != nullptr)
{
Queue q;
q.Enqueue(root);

while (!q.isEmpty())
{
BSNode* current = q.Peek();
q.Dequeue();

visit(current->getData());

if (current->getLeft() != nullptr)
{
q.Enqueue(current->getLeft());
}

if (current->getRight() != nullptr)
{
q.Enqueue(current->getRight());
}
}

}
else
{
throw Exception("Cannot return an empty list");
}
}

template
bool BSTree::isEmpty() const
{
return root == nullptr;
}

template
bool BSTree::contains(const T& item) const
{
return containsNode(root, item);
}

template
BSNode* BSTree::getRoot() const
{
return root;
}

template
void BSTree::display(void (*visit)(T data)) const
{
inOrder(visit);
}

// Private methods
template
BSNode* BSTree::insertNode(BSNode* node, const T& item)
{
if (node == nullptr)
return new BSNode(item);

if (item < node->getData())
node->left = insertNode(node->left, item);
else if (item > node->getData())
node->right = insertNode(node->right, item);

return node;
}

template
BSNode* BSTree::deleteNode(BSNode* node, const T& item)
{
if (node == nullptr)
return nullptr;

if (item < node->getData())
node->left = deleteNode(node->left, item);
//node->getLeft() = deleteNode(node->getLeft(), item);
else if (item > node->getData())
node->right = deleteNode(node->right, item);
//node->getRight() = deleteNode(node->getRight(), item);
else {
// Node to be deleted found

// Case 1: Leaf node
if (node->getLeft() == nullptr && node->getRight() == nullptr)
{
delete node;
return nullptr;
}

// Case 2: Node with one child
if (node->getLeft() == nullptr)
{
BSNode* temp = node->getRight();
delete node;
return temp;
}
if (node->getRight() == nullptr)
{
BSNode* temp = node->getLeft();
delete node;
return temp;
}

// Case 3: Node with two children
// Find inorder successor (smallest in right subtree)
BSNode* temp = findMin(node->getRight());

// Copy the inorder successor's data to this node
node->data = temp->data;

// Delete the inorder successor
node->right = deleteNode(node->getRight(), temp->getData());
}

return node;
}

template
BSNode* BSTree::findMin(BSNode* node) const
{
if (node == nullptr)
return nullptr;

while (node->getLeft() != nullptr)
node = node->getLeft();

return node;
}

template
void BSTree::purgeNode(BSNode* node)
{
if (node != nullptr)
{
purgeNode(node->left);
purgeNode(node->right);
delete node;
}
}
template
int BSTree::heightNode(BSNode* node) const
{
if (node == nullptr)
{
throw Exception("Can't return an empty height");
}

// Handle left child
int leftHeight = 0;
if (node->getLeft() != nullptr) {
leftHeight = heightNode(node->getLeft());
}

// Handle right child
int rightHeight = 0;
if (node->getRight() != nullptr) {
rightHeight = heightNode(node->getRight());
}

return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

template
void BSTree::inOrderNode(BSNode* node, void (*visit)(T data)) const
{
if (node != nullptr) {
inOrderNode(node->getLeft(), visit);
visit(node->getData());
inOrderNode(node->getRight(), visit);
}
}

template
void BSTree::preOrderNode(BSNode* node, void (*visit)(T data)) const
{
if (node != nullptr) {
visit(node->getData());
preOrderNode(node->getLeft(), visit);
preOrderNode(node->getRight(), visit);
}
}

template
void BSTree::postOrderNode(BSNode* node, void (*visit)(T data)) const
{
if (node != nullptr)
{
postOrderNode(node->getLeft(), visit);
postOrderNode(node->getRight(), visit);
visit(node->getData());
}
}

template
bool BSTree::containsNode(BSNode* node, const T& item) const
{
if (node == nullptr)
return false;

if (item == node->getData())
return true;

if (item < node->data)
return containsNode(node->getLeft(), item);
else
return containsNode(node->getRight(), item);
}
#endif
< /code>
#pragma once
#ifndef BS_NODE_H
#define BS_NODE_H

template
class BSTree;

// Now define BSNode with the friendship
template
class BSNode {
friend class BSTree;
public:
// Default constructor
BSNode();

// Parameterized constructor
BSNode(const T& item);

// Copy constructor
BSNode(const BSNode& other);

// Move constructor
BSNode(BSNode&& other) noexcept;

// Copy assignment operator
BSNode& operator=(const BSNode& other);

// Move assignment operator
BSNode& operator=(BSNode&& other) noexcept;

// Destructor
~BSNode();

T getData() const;
void setData(const T& item);
BSNode* getLeft() const;
void setLeft(BSNode* node);
BSNode* getRight() const;
void setRight(BSNode* node);
bool isLeaf() const;

private:
T data;
BSNode* left;
BSNode* right;
};

// Default constructor
template
BSNode::BSNode() : data(), left(nullptr), right(nullptr)
{}

// Parameterized constructor
template
BSNode::BSNode(const T& item) : data(item), left(nullptr), right(nullptr)
{}

template
BSNode::BSNode(const BSNode& other) : data(other.data), left(nullptr), right(nullptr)
{
if (other.left != nullptr) {
left = new BSNode(*other.left); // Recursive deep copy
}
if (other.right != nullptr) {
right = new BSNode(*other.right); // Recursive deep copy
}
}

// Move constructor
template
BSNode::BSNode(BSNode&& other) noexcept
: data(std::move(other.data)), left(other.left), right(other.right)
{
// Reset the moved-from object
other.left = nullptr;
other.right = nullptr;
}

// Copy assignment: Copies ONLY the data, leaves pointers alone.
template
BSNode& BSNode::operator=(const BSNode& other) {
if (this != &other) { // Check for self-assignment
data = other.data;
}
return *this;
}

// Move assignment: Moves ONLY the data, leaves pointers alone.
template
BSNode& BSNode::operator=(BSNode&& other) noexcept {
if (this != &other) { // Check for self-assignment
data = std::move(other.data);
}
return *this;
}

// Destructor
template
BSNode::~BSNode()
{
//data = T();
//delete left;
//delete right;
}

template
T BSNode::getData() const
{
return data;
}

template
void BSNode::setData(const T& item)
{
data = item;
}

template
BSNode* BSNode::getLeft() const
{
return left;
}

template
void BSNode::setLeft(BSNode* node)
{
left = node;
}

template
BSNode* BSNode::getRight() const
{
return right;
}

template
void BSNode::setRight(BSNode* node)
{
right = node;
}

template
bool BSNode::isLeaf() const
{
return (left == nullptr && right == nullptr);
}
< /code>
I suspect that my dtor inside my node class should have the given comments uncommented but when I do I throw an Exception. You can also assume that my Queue class is functional and working as intended from other tests.

Подробнее здесь: https://stackoverflow.com/questions/796 ... earch-tree