0
這是我的Binarysearchtree.h。當必須刪除的元素有一個子元素時，remove函數不起作用。從二叉搜索樹中刪除元素
#ifndef BINARYSEARCHTREE_H_INCLUDED
#define BINARYSEARCHTREE_H_INCLUDED
class BinarySearchTreeNode {
public:
int data;
BinarySearchTreeNode* left;
BinarySearchTreeNode* right;
BinarySearchTreeNode(int data):data(data), left(NULL), right(NULL) {
}
~BinarySearchTreeNode() {
if (left)
delete left;
if (right)
delete right;
}
friend class BinarySearchTree;
};
class BinarySearchTree
{
private:
int size;
public:
BinarySearchTreeNode * root;
BinarySearchTree()
{
size=0;
root= NULL;
}
private:
void insert_help(BinarySearchTreeNode*root,BinarySearchTreeNode*node)
{
if(root==NULL)
{
this->root=node;
return;
}
if(node->data>root->data and root->right==NULL)
{
root->right=node;
return;
}
if(node->data<=root->data and root->left==NULL)
{
root->left=node;
return;
}
if(node->data<=root->data)
insert_help(root->left,node);
if(node->data>root->data)
insert_help(root->right,node);
}
public:
void insert(int data)
{
BinarySearchTreeNode* newnode=new BinarySearchTreeNode(data);
size++;
insert_help(this->root,newnode);
}
void printLevelWise()
{
if(root==NULL)
return;
queue<BinarySearchTreeNode*> pending;
pending.push(root);
while(pending.empty()!=1)
{
BinarySearchTreeNode*latest=pending.front();
pending.pop();
cout<<latest->data<<": ";
if(latest->left)
{
cout<<latest->left->data<<",";
pending.push(latest->left);
}
if(latest->right)
{
cout<<latest->right->data<<",";
pending.push(latest->right);
}
cout<<"\n";
}
}
bool isEmpty()
{
if(root==NULL)
return true;
else
return false;
}
int Size()
{
return size;
}
private:
BinarySearchTreeNode* Search_help(BinarySearchTreeNode*root,int data)
{
if(root==NULL or root->data==data)
return root;
if(data>root->data)
return Search_help(root->right,data);
if(data <= root->data)
return Search_help(root->left,data);
}
public:
BinarySearchTreeNode* Search(int data)
{
return Search_help(root,data);
}
private:
BinarySearchTreeNode*return_min(BinarySearchTreeNode*root)
{
if(root->left==NULL)
return root;
return return_min(root->left);
}
/*this is my remove function*/
BinarySearchTreeNode* remove_help(BinarySearchTreeNode*root,int data)
{
if(root==NULL)
return root;
if(data>root->data)
root->right= remove_help(root->right,data);
else if(data<root->data)
root->left=remove_help(root->left,data);
else
{
//no child
if(root->left==NULL and root->right==NULL)
{
delete root;
return NULL;
}
//one child
if(root->left==NULL)
{
BinarySearchTreeNode*temp=root->right;
delete root; // when i remove this line the code works idk why
return temp;
}
if(root->right==NULL)
{
BinarySearchTreeNode*temp=root->left;
delete root;
return temp;
}
//more than one child
BinarySearchTreeNode*temp=return_min(root->right);
root->data=temp->data;
root->right=remove_help(root->right,temp->data);
}
return root;
}
public:
void Remove(int data)
{
root=remove_help(root,data);
return;
}
};
#endif // BINARYSEARCHTREE_H_INCLUDED
////////////////////////////////
該程序適用於當節點沒有孩子或多於兩個孩子但沒有一個孩子時。
/*here is my main program*/
#include<iostream>
#include"tree.h"
#include<limits.h>
#include<math.h>
#include<stack>
#include"BinaryTree.h"
#include"linked_list.h"
#include<vector>
#include"BinarySearchTree.h"
using namespace std;
int main()
{
BinarySearchTree bst;
bst.insert(6);
bst.insert(3);
bst.insert(9);
bst.insert(4);
bst.insert(8);
bst.printLevelWise();
bst.Remove(9);
bst.printLevelWise();
}
/我不知道，就像我的問題需要評論更多的上下文/