Below is the code that is developed in this lesson's videos. I strongly recommend that you watch the videos.
Unfortunately, the name of the class used here and in the videos is "binarytree" even though it should be "BinarySearchTree". I'm keeping the name the same here to avoid confusion between the code below and the code developed in the videos.
Note that a major difference between this code and that developed in the text is that this code represents the treenode with a simple struct nested inside the binaryTree class. This makes the code in the text far more complex. There's no problem with making the data inside the treenode struct public, because that struct is in the private area of the class. In fact, we could safely keep the data public even if the treenode struct was not nested inside the binarytree class, because these treenode objects will be fully protected by their being private members of the tree class in which they are used. (The Loceff lesson uses this approach of declaring a treenode class with all public data members but OUTSIDE of the tree class.)
// Here is the file binarytree.h
#ifndef BINARYTREE_H
#define BINARYTREE_H
#include <cstdlib> // for size_t
class binarytree {
public:
typedef std::size_t size_type;
binarytree();
void insert(int item);
void print() const;
size_type size() const;
int find(int target, bool& found) const;
void del(int target, bool& found);
private:
struct treenode {
int data;
treenode* left;
treenode* right;
};
treenode* root;
static void insert_aux(treenode*& root, int item);
static void print_aux(const treenode* root);
static size_type size_aux(const treenode* root);
static int find_aux(const treenode* root, int target, bool& found);
static void del_aux(treenode*& root, int target, bool& found);
static void remove_max(treenode*& root, int& max);
};
#endif
// Here is the file binarytree.cpp
#include <iostream>
#include "binarytree.h"
using namespace std;
binarytree::binarytree() {
root = nullptr;
}
void binarytree::print() const {
print_aux(root);
}
void binarytree::insert(int item) {
insert_aux(root, item);
}
binarytree::size_type binarytree::size() const {
return size_aux(root);
}
int binarytree::find(int target, bool& found) const {
return find_aux(root, target, found);
}
void binarytree::del(int target, bool& found) {
del_aux(root, target, found);
}
void binarytree::del_aux(treenode*& root,
int target,
bool& found) {
if (root == nullptr) {
found = false;
} else if (target < root -> data) {
del_aux(root -> left, target, found);
} else if (target > root -> data) {
del_aux(root -> right, target, found);
} else if (root -> left == nullptr) {
treenode* tempptr = root;
root = root -> right;
delete tempptr;
found = true;
} else {
int max;
remove_max(root -> left, max);
root -> data = max;
found = true;
}
}
// pre: root != nullptr
void binarytree::remove_max(treenode*& root, int& max) {
if (root -> right == nullptr) {
max = root -> data;
treenode* tempptr = root;
root = root -> left;
delete tempptr;
} else {
remove_max(root -> right, max);
}
}
int binarytree::find_aux(const treenode* root,
int target,
bool& found) {
if (root == nullptr) {
found = false;
return 0;
} else if (target == root -> data) {
found = true;
return root -> data;
} else if (target < root -> data) {
return find_aux(root -> left, target, found);
} else {
return find_aux(root -> right, target, found);
}
}
binarytree::size_type binarytree::size_aux(const treenode* root){
if (root == nullptr) {
return 0;
} else {
return size_aux(root -> left)
+ size_aux(root -> right)
+ 1;
}
}
void binarytree::insert_aux(treenode*& root, int item) {
if (root == nullptr) {
root = new treenode;
root -> data = item;
root -> left = nullptr;
root -> right = nullptr;
} else if (item <= root -> data) {
insert_aux(root -> left, item);
} else {
insert_aux(root -> right, item);
}
}
void binarytree::print_aux(const treenode* root) {
if (root != nullptr) {
print_aux(root -> left);
cout << root -> data << " ";
print_aux(root -> right);
}
}
// Here is the file binarytree-client.cpp
#include <iostream>
#include "binarytree.h"
using namespace std;
int main() {
binarytree list;
int num;
bool found;
cout << "enter number to insert (negative to quit): ";
cin >> num;
while (num >= 0){
list.insert(num);
cout << "enter number to insert (negative to quit): ";
cin >> num;
}
list.print();
cout << endl;
binarytree::size_type numItems;
numItems = list.size();
cout << "There are " << numItems << " items." << endl;
cout << "enter a number to find (negative to quit): ";
cin >> num;
while (num >= 0) {
int result = list.find(num, found);
if (!found) {
cout << "not found" << endl;
} else {
cout << "found. The data is " << result << endl;
}
cout << "enter a number to find (negative to quit): ";
cin >> num;
}
cout << "enter a number to delete (negative to quit): ";
cin >> num;
while (num >= 0) {
list.del(num, found);
if (found) {
cout << "the list is now ";
list.print();
cout << endl;
} else {
cout << num << " is not in the list." << endl;
}
cout << "enter a number to delete (negative to quit): ";
cin >> num;
}
binarytree list2(list);
cout << "Now list 2 should be a copy of list. Here it is: ";
list2.print();
cout << endl;
list2.del(3, found);
cout << "After deleting a 3 from list2, list2 is now: ";
list2.print();
cout << endl << "list should be unchanged. Here it is: ";
list.print();
cout << endl;
list = list2;
cout << "Now list has been assigned list2 so it should match list2. Here it is: ";
list.print();
cout << endl;
list.del(4, found);
cout << "After deleting a 4 from list, list is now: ";
list.print();
cout << endl << "list2 should be unchanged. Here it is: ";
list2.print();
cout << endl;
}