我创建了一个名为BST的类,它具有成员根。我知道当我向BST类调用解构函数时,它将删除root并释放该类占用的内存。
我想知道,解构函数将解构所有与BST对象相关联的节点。就是根的左子和右子以及它们的左和右子,依此类推。
我的猜测是,在这种情况下,我认为我将必须进行后遍历并手动删除每个节点。有什么办法可以一次完成。无需在树节点周围走动
#ifndef BST_H
#define BST_H
#include "bst.h"
#include <stdio.h>
#include<iostream>
class bst
{
protected:
struct node{
node* p;
node* lc;
node* rc;
int key;
node(int x,node* p=nullptr,node* lc=nullptr,node* rc=nullptr):key(x){
}
~node(){
std::cout<<"decontrucotr node";
}
};
node* nil=new node(0);
node* root;
public:
bst();
virtual ~bst();
void put(int x);
void in_order(node* x);
void in_order();
void pre_order(node* x);
void pre_order();
private:
};
#endif // BST_H
功能在此定义
#include "bst.h"
#include <stdio.h>
#include<iostream>
bst::bst():root(nil)
{
}
bst::~bst()
{
std::cout<<"deconstructor tree"<<'\n';
}
void bst::put(int x)
{
node* k=new node(x,this->nil,this->nil,this->nil);
node* y=this->root;
node* p=y;
while (y != nil){
p=y;
if (y->key>x){
y=y->lc;
}
else{
y=y->rc;
}
}
if (p==nil){
this->root=k;
k->lc=this->nil;
k->rc=this->nil;
k->p=this->nil;
}
else if(p->key>x){
p->lc=k;
p->lc->p=p;
k=p->lc;
k->lc=this->nil;
k->rc=this->nil;
}
else{
p->rc=k;
p->rc->p=p;
k=p->rc;
k->lc=this->nil;
k->rc=this->nil;
}
}
void bst::in_order(node* x){
if(x != nil){
this->in_order(x->lc);
printf("%d%c",x->key,'\t');
this->in_order(x->rc);
}
}
void bst :: in_order(){
this->in_order(this->root);
printf("%c",'\n');
}
void bst::pre_order(node* x){
if(x!=this->nil){
printf("%d%c",x->key,'\t');
pre_order(x->lc);
pre_order(x->rc);
}
}
void bst::pre_order(){
pre_order(this->root);
printf("%c",'\n');
}
最佳答案
我创建了一个名为BST的类,它具有成员根。我知道当我向BST类调用解构函数时,它将删除root并释放该类占用的内存。
在所示的实现中,~bst
析构函数本质上是空的(记录不计入),它根本没有释放任何节点。
我想知道,解构函数将解构所有与BST对象相关联的节点。bst
对象本身被破坏。它的子节点不是,不是。
就是根的左子和右子以及它们的左和右子,依此类推。
不在当前的实现中。您需要对该逻辑进行编码。
在那种情况下,我认为我将必须进行后遍历并手动删除每个节点。
在当前的实现中,是的。
有什么办法可以一次完成。无需在树节点周围走动
要么:
对~node
析构函数进行编码以删除其直接子节点。然后,~bst
析构函数可以删除其root
节点,并且其下的所有其他节点将被递归删除。
使用智能指针(例如std::unique_ptr
)代替原始指针。让编译器为您完成所有工作。