Return to Answer

• 1

• 97.7k
• 5
• 126
• 341

In Addition to what @Mast said.

You DON'T implement the rule of three.
This needs to be fixed (especially since you have resource ownership).

Missing Destructor.

I think you can simplify some of your code by moving it from btree into node and using some simpler functions that do specific parts of the task.

There is an extra default constructor in node that I think is superfluous. When are you going to create a node with the value undefined?

You should be using nullptr rather than NULL. Its 2015 the standard has been out 4 years and every modern compiler now supports it.

It is more standard to use an initial capitol letter for types (to help spot them). And use an initial lower case letter for objects (this includes functions and methods).

Thus node => Node and btree => BTree

I don't like your delete it is overly complex. You should never need to find the parent of a node when doing tree manipulation. You had to pass it to get to the current node.

As a side note. This can be trivially templatized to handle any type.

###insert

You don't check for equivalence. I presume this is bug (because the second one will never be found anyway).

Can be simplified like this:

void bTree::insert(int newVal){
 if(!root){
 root = new node(newVal);
 return;
 }
 root.insert(newVal);
}
void node::insert(newVal) {
 if (val == newVal) {
 return;
 }
 if (newVal < val) {
 left = insertNext(left, newVal);
 } else {
 right = insertNext(right, newVal);
 }
}
node* node::insertNext(Node* next, int newValue) {
 if (next == nullptr) {
 return new node(newValue);
 }
 next.insert(newValue);
}

deleteVal

void bTree::deleteVal(int delVal){
 if (!root) {
 return;
 }
 node* bad = nullptr;
 root = root.deleteVal(bad, delVal);
 // This assumes node does not own its left/right members.
 delete bad;
}
node* node::deleteVal(node*& bad, int delVal) {
 /*
 * Note: If this function does not return this.
 * Then we have removed it from the tree.
 * we will return one of the subtrees instead
 * potentially modified.
 */
 if (val == delVal) {
 bad = this;
 if (left == nullptr) {
 // If the left subtree is null then the right is the one we want (even if null)
 return right;
 } else if (right == nullptr) {
 // If the right subtree is null then the left is the one we want
 return left;
 } else {
 // Otherwise both subtrees are not null.
 // Now we must do some work.
 // Rotate the right sub tree up into this place.
 // Thus move the left subtree to the leftmost node in the right subtree.
 addLefttoRightSubTree(left, right);
 return right;
 }
 // Otherwise ask the next node to do the work.
 } else if (delVal < val) {
 left = deleteValNext(left, bad, delVal);
 } else
 right = deleteValNext(right, bad, delVal);
 }
 return this;
}
node* node::deleteValNext(node* next, node*& bad, int delVal) {
 if (next != nullptr) {
 return next.deleteVal(bad, delValue);
 }
 return nullptr;
}