C++ 一次删除整个二叉搜索树
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/8062080/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Deleting the entire binary search tree at once
提问by Zohaib
I have been trying to implement the delete BST function but I don't know why it is not working, I think it's logically correct. Can any body please tell me, why I'm getting run time error and how should I correct it.
我一直在尝试实现delete BST功能，但不知道为什么它不起作用，我认为它在逻辑上是正确的。任何机构都可以告诉我，为什么我会收到运行时错误以及我应该如何纠正它。
#include <iostream>
using namespace std;
class node{
public:
int data;
node *right;
node *left;
node(){
data=0;
right=NULL;
left=NULL;
}
};
class tree{
node *head;
int maxheight;
public:
tree(){head=0;maxheight=-1;}
bool deletenode(int key,node* root);
int get_height(){return maxheight;}
void insert(int key);
void pre_display(node* root);
void delete_tree(node *root);
node* get_head(){return head;}
};
void tree::insert(int key){
node *current=head;
node *newnode=new node;
if(newnode==NULL)
throw(key);
newnode->data=key;
int height=0;
if(head==0){
head=newnode;
}
else
{
while(1){
if(current->right==NULL && current->data < newnode->data)
{
current->right=newnode;
height++;
break;
}
else if(current->left==NULL && current->data > newnode->data)
{
current->left=newnode;
height++;
break;
}
else if(current->right!=NULL && current->data < newnode->data)
{
current=current->right;
height++;
}
else if(current->left!=NULL && current->data > newnode->data)
{
current=current->left;
height++;
}
}
}
if(height>maxheight)
maxheight=height;
}
void tree::pre_display(node *root){
if(root!=NULL)
{
cout<<root->data<<" ";
pre_display(root->left);
pre_display(root->right);
}
}
void tree::delete_tree(node *root){
if(root!=NULL)
{
delete_tree(root->left);
delete_tree(root->right);
delete(root);
if(root->left!=NULL)
root->left=NULL;
if(root->right!=NULL)
root->right=NULL;
root=NULL;
}
}
int main(){
tree BST;
int arr[9]={17,9,23,5,11,21,27,20,22},i=0;
for(i=0;i<9;i++)
BST.insert(arr[i]);
BST.pre_display(BST.get_head());
cout<<endl;
BST.delete_tree(BST.get_head());
BST.pre_display(BST.get_head());
cout<<endl;
system("pause");
return 0;
}
All the other functions are working correctly, you just need to check the delete_treefunction, the other code is provided to give the idea of the structure of my BST.
所有其他功能都正常工作，您只需要检查该delete_tree功能，其他代码提供了我的BST结构的想法。
回答by parapura rajkumar
In your delete_tree
在您的 delete_tree 中
void tree::delete_tree(node *root){
if(root!=NULL)
{
delete_tree(root->left);
delete_tree(root->right);
delete(root);
if(root->left!=NULL)
root->left=NULL;
if(root->right!=NULL)
root->right=NULL;
root=NULL;
}
}
you are accessing rootvariable after you have deleted it
您在删除根变量后正在访问它
Also you call
你也叫
BST.delete_tree(BST.get_head());
BST.pre_display(BST.get_head());
pre_display after deleting tree. delete_treeafter deleting the tree should also set the BST.head to NULL
删除树后的 pre_display。delete_tree删除树后也应该设置 BST.head 为 NULL
Also a critique. BST is of type tree. It already has a head member variable indicating the root node. So delete_tree/pre_display do not need any parameters at all.
也是一种批判。BST 是树类型。它已经有一个指示根节点的头成员变量。所以 delete_tree/pre_display 根本不需要任何参数。
回答by Turdubek Joldoshov
You can delete by: //This is function of cleaning:
您可以通过以下方式删除： //这是清理功能：
void cleantree(tree *root){
if(root->left!=NULL)cleantree(root->left);
if(root->right!=NULL)cleantree(root->right);
delete root;}
//This is where we call the cleaning function:
//这里是我们调用清洗函数的地方：
cleantree(a);
a=NULL;
//Where "a" is pointer to root of the tree.
//其中“a”是指向树根的指针。
回答by Luchian Grigore
The problem is here:
问题在这里：
delete_tree(root->left);
delete_tree(root->right);
delete(root);
if(root->left!=NULL)
root->left=NULL;
if(root->right!=NULL)
root->right=NULL;
root=NULL;
You're trying to assign NULL to a member of root:
您正在尝试将 NULL 分配给 root 的成员：
root->left=NULL;
which was already deleted. There's no need to do that since you're already freeing the memory in delete_tree(root->left);
这已经被删除了。没有必要这样做，因为您已经在释放内存delete_tree(root->left);
回答by kalimba
Recursively delete left and right sub tree and your tree will be deleted as simple as:
递归删除左右子树，您的树将被删除，就像：
void delete(node *root){
// If node is empty, don't bother
if (root == NULL) { return; }
// Delete subtrees
delete(root->left);
delete(root->right);
// Delete current node
free(root);
root = NULL;
}
回答by David Grayson
You should not read from root after deleting it. Move the delete(root)line down.
删除后不应从 root 读取。将delete(root)线向下移动。
回答by damirlj
Short answer: your implementation of the node descriptor missing the correct explicit destructor implementation (the default generated by the compiler will be used by calling the delete operator:calling destructor and releasing the allocated space on the heap)-the one that clear references to the siblings
简短回答：您的节点描述符实现缺少正确的显式析构函数实现（编译器生成的默认值将通过调用删除运算符使用：调用析构函数并释放堆上分配的空间）-清除对兄弟姐妹
回答by Brahim KHOUY
here is my suggestion using recursivity..
这是我使用递归的建议..
template <class T> void Tree<T>::destroy(Noeud<T> ** r){
if(*r){
if(!(*r)->left && !(*r)->right){ //a node having no child
delete *r; *r=NULL;
}else if((*r)->left && (*r)->right){ //a node having two childs
destroy(&(*r)->left); //destroy the left tree
destroy(&(*r)->right); //destroy the right tree
destroy(r); //destroy the node
}else if((*r)->left){ //a node has only left child
destroy(&(*r)->left); //destroy the left tree
destroy(r); //destroy the node
}else if((*r)->right){ //a node has only right child
destroy(&(*r)->right); //destroy the right tree
destroy(r); //destroy the node
}
}
}
//in function main()
int main(){
Tree<int> a(5); // 'a' is a tree of int type with a root value equal 5
a.add(2);a.add(7);a.add(6);a.add(-1);a.add(10); // insert values into the tree
a.destroy(&a.root); //destroy the tree
}
