二叉搜索树的析构函数
Destructor for Binary Search Tree
我正在尝试为我的二叉搜索树编写析构函数,我知道如何递归循环遍历树,但我不知道如何在析构函数中执行此操作以便删除每个节点。
我的Header是:
struct Node;
typedef string TreeType;
typedef Node * TreePtr;
//Defines a Node
struct Node
{
TreeType Info;
int countDuplicates = 1;
TreePtr Left, Right;
};
class Tree
{
public:
//Constructor
Tree();
//Destructor
~Tree();
//Retruns true if the tree is Empty
bool Empty();
//Inserts a Node into the tree
bool Insert(TreeType);
//Delete decides what type of delection needs to occur, then calls the correct Delete function
bool Delete(Node * , Node * );
//Deletes a leaf node from the tree
bool DeleteLeaf(TreePtr, TreePtr);
//Deletes a two child node from the tree
bool DeleteTwoChild(TreePtr);
//Deletes a one child node from the tree
bool DeleteOneChild(TreePtr, TreePtr);
//Finds a certain node in the tree
bool Find(TreeType);
//Calculates the height of the tree
int Height(TreePtr);
//Keeps a count of the nodes currently in the tree;
void Counter();
private:
//Prints the nodes to the output text file in order alphabetically
void InOrder(ofstream &,TreePtr);
//Defines a TreePtr called Root
TreePtr Root;
//Defines a TreePtr called Current
TreePtr Current;
//Defines a TreePtr called Parent
TreePtr Parent;
};
我的构造函数是:
Tree::Tree()
{
Root = NULL;
Current = NULL;
Parent = NULL;
}
有没有递归调用析构函数的方法?如果没有,我如何遍历每个节点删除它。
void Tree::DestroyRecursive(TreePtr node)
{
if (node)
{
DestroyRecursive(node->left);
DestroyRecursive(node->right);
delete node;
}
}
Tree::~Tree()
{
DestroyRecursive(Root);
}
你需要两个析构函数:
Tree::~Tree()
{
delete Root;
}
和
Node::~Node()
{
delete Left;
delete Right;
}
但是这里你真的不需要两个 类。每个 Node
都是一棵树。
当您调用 delete
或您的 Tree
生命周期结束时(从块中退出,就像最后的示例一样),您必须 delete
Tree
children Node
和 delete
运算符将调用析构函数,请参阅最后的示例。
这将使 Tree 在调用 Tree 析构函数时从内存中完全消失。
试试这个:
#include <iostream>
using namespace std;
class Node {
Node *left, *right;
public:
Node(Node *l, Node *r);
~Node();
};
class Tree {
Node *root;
public:
Tree(Node *rt);
~Tree();
};
Tree::Tree(Node *rt):root(rt) {
cout << "new Tree with root node at " << rt << endl;
}
Tree::~Tree() {
cout << "Destructor of Tree" << endl;
if (root) delete root;
}
Node::Node(Node *l, Node *r):left(l), right(r) {
cout << "Node@"
<< this
<< "(left:" << l
<< ", right:" << r << ")"
<< endl;
}
Node::~Node() {
cout << "~Node@" << this
<< endl;
if (left) delete left;
if (right) delete right;
}
int main() {
Tree t(
new Node(
new Node(
new Node(
new Node(0, 0),
0),
0),
new Node(0, new Node(0, 0))));
}
这是我的实现。一个树等于一个树节点。
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
~TreeNode() {
delete left;
delete right;
}
...
};
只需删除树的根节点,然后递归删除整棵树。
TreeNode* root = new TreeNode(2);
delete root;
您可能已经知道 删除 的作用。
When delete is used to deallocate memory for a C++ class object, the
object's destructor is called before the object's memory is
deallocated (if the object has a destructor).
所以,在一个treeNode的析构函数中,你只需要销毁你手动分配的左右指针即可。您无需担心节点本身的释放。
我正在尝试为我的二叉搜索树编写析构函数,我知道如何递归循环遍历树,但我不知道如何在析构函数中执行此操作以便删除每个节点。
我的Header是:
struct Node;
typedef string TreeType;
typedef Node * TreePtr;
//Defines a Node
struct Node
{
TreeType Info;
int countDuplicates = 1;
TreePtr Left, Right;
};
class Tree
{
public:
//Constructor
Tree();
//Destructor
~Tree();
//Retruns true if the tree is Empty
bool Empty();
//Inserts a Node into the tree
bool Insert(TreeType);
//Delete decides what type of delection needs to occur, then calls the correct Delete function
bool Delete(Node * , Node * );
//Deletes a leaf node from the tree
bool DeleteLeaf(TreePtr, TreePtr);
//Deletes a two child node from the tree
bool DeleteTwoChild(TreePtr);
//Deletes a one child node from the tree
bool DeleteOneChild(TreePtr, TreePtr);
//Finds a certain node in the tree
bool Find(TreeType);
//Calculates the height of the tree
int Height(TreePtr);
//Keeps a count of the nodes currently in the tree;
void Counter();
private:
//Prints the nodes to the output text file in order alphabetically
void InOrder(ofstream &,TreePtr);
//Defines a TreePtr called Root
TreePtr Root;
//Defines a TreePtr called Current
TreePtr Current;
//Defines a TreePtr called Parent
TreePtr Parent;
};
我的构造函数是:
Tree::Tree()
{
Root = NULL;
Current = NULL;
Parent = NULL;
}
有没有递归调用析构函数的方法?如果没有,我如何遍历每个节点删除它。
void Tree::DestroyRecursive(TreePtr node)
{
if (node)
{
DestroyRecursive(node->left);
DestroyRecursive(node->right);
delete node;
}
}
Tree::~Tree()
{
DestroyRecursive(Root);
}
你需要两个析构函数:
Tree::~Tree()
{
delete Root;
}
和
Node::~Node()
{
delete Left;
delete Right;
}
但是这里你真的不需要两个 类。每个 Node
都是一棵树。
当您调用 delete
或您的 Tree
生命周期结束时(从块中退出,就像最后的示例一样),您必须 delete
Tree
children Node
和 delete
运算符将调用析构函数,请参阅最后的示例。
这将使 Tree 在调用 Tree 析构函数时从内存中完全消失。
试试这个:
#include <iostream>
using namespace std;
class Node {
Node *left, *right;
public:
Node(Node *l, Node *r);
~Node();
};
class Tree {
Node *root;
public:
Tree(Node *rt);
~Tree();
};
Tree::Tree(Node *rt):root(rt) {
cout << "new Tree with root node at " << rt << endl;
}
Tree::~Tree() {
cout << "Destructor of Tree" << endl;
if (root) delete root;
}
Node::Node(Node *l, Node *r):left(l), right(r) {
cout << "Node@"
<< this
<< "(left:" << l
<< ", right:" << r << ")"
<< endl;
}
Node::~Node() {
cout << "~Node@" << this
<< endl;
if (left) delete left;
if (right) delete right;
}
int main() {
Tree t(
new Node(
new Node(
new Node(
new Node(0, 0),
0),
0),
new Node(0, new Node(0, 0))));
}
这是我的实现。一个树等于一个树节点。
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
~TreeNode() {
delete left;
delete right;
}
...
};
只需删除树的根节点,然后递归删除整棵树。
TreeNode* root = new TreeNode(2);
delete root;
您可能已经知道 删除 的作用。
When delete is used to deallocate memory for a C++ class object, the object's destructor is called before the object's memory is deallocated (if the object has a destructor).
所以,在一个treeNode的析构函数中,你只需要销毁你手动分配的左右指针即可。您无需担心节点本身的释放。