RBX
In the zone
This was the code to be prefixed, I had to design methods around it. Although recursive methods could be designed, I decided to make iterative ones.
Code:
#include <iostream>
using namespace std;
class binarySearchTree;
class treeNode{
/*
*with the following friend declaration
*binarySearchTree class can also access private members of treeNode
*/
friend class binarySearchTree;
private:
int data;
treeNode * left;
treeNode * right;
public:
treeNode(){
left=right=NULL;
//parent = NULL;
}
treeNode(int key){
data=key;
left=right=NULL ;
//parent=NULL;
}
int getData(){ return data;}
void setData(int key){data=key;}
};
class binarySearchTree{
private:
treeNode * root;
public:
binarySearchTree(){root=NULL;}
/*THE ABOVE CODE WILL BE ADDED AS PREFIX TO YOUR CODE**/
/*Finish The Implementation of the binarySearchTree Class*/This is how I implemented delete (seems to be quite a bad implementation, I'll try to improve it).
Code:
void binarySearchTree::remove(int val) {
treeNode* temp = root;
treeNode* tempParent = NULL; //needs to be tracked so that parent doesn't point to a deleted node
//find the node to be deleted
if (temp != NULL) {
while (temp->data != val) {
if (val < temp->data) {
tempParent = temp; //new changes for parent
temp = temp->left;
} else if (val > temp->data) {
tempParent = temp; //new changes for parent
temp = temp->right;
}
}
}
//if leaf node
if (temp->left == NULL && temp->right == NULL) {
if (tempParent != NULL) {
if (temp->data < tempParent->data) tempParent->left = NULL;
else if (temp->data > tempParent->data) tempParent->right = NULL;
}
[B] if (temp == root) root = NULL;
delete(temp);
temp = NULL;[/B]
return;
}
//if not a leaf node
//find the replacement node
treeNode* replace = temp;
treeNode* replaceParent = NULL; //needs to be tracked so that childen of replacement can be attached to it
if (temp->left != NULL) { //find largest element in left subtree
replaceParent = replace;
replace = replace->left;
while (replace->right != NULL) {
replaceParent = replace;
replace = replace->right;
}
temp->data = replace->data; //make replacement
//test
if (replaceParent != temp) {
if (replace->left != NULL) //if replacement is not a leaf node
replaceParent->right = replace->left; //attach left-children of replacement to its parent
else
replaceParent->right = NULL; //now parent won't point to the deleted child(replace)
}
////if replacement is a leaf node, replace->left is NULL, so this *should* work in both cases(leaf/non-leaf)
//replaceParent->right = replace->left;
if (replaceParent->left == replace) replaceParent->left = replace->left;
delete(replace);
replace = NULL;
} else if (temp->right != NULL) { //find smallest element in right subtree
replaceParent = replace;
replace = replace->right;
while (replace->left != NULL) {
replaceParent = replace;
replace = replace->left;
}
temp->data = replace->data;
if (replaceParent != temp) {
if (replace->right != NULL) //if replacement is not a leaf node
replaceParent->left = replace->right; //attach right-children of replacement to its parent
else
replaceParent->left = NULL; //now parent won't point to the deleted child(replace)
}
////if replacement is a leaf node, replace->right is NULL, so this *should* work in both cases(leaf/non-leaf)
//replaceParent->right = replace->left;
if (replaceParent->right == replace) replaceParent->right = replace->right;
//replaceParent->left = replace->right;
delete(replace);
replace = NULL;
}
/**abandoned**/
/*
//replace
if (replace == temp) { //No replacement found //leaf node
free(temp);
free(replace);
} else {
if (replace->data > temp->data) { //largest in left subtree
temp->data = replace->data;
if (replace->left != NULL) { //if the replacement had left children
}
}
}
*/
}As can be seen root is a member of BST class, so delete(temp) would just set root to some garbage value, and then if I do temp = NULL, it would just make temp point to NULL, not set root to NULL, so I have to set root to NULL in this dirty way.
Last edited:
