### Binary Search Tree Help

Binary Search Tree's are one of my weak points in C++. I understand the concept but utilizing them is completely foreign to me. Below is the code from my textbook, and I have to "Change the BinarySearchTree.print member function to print the tree as a tree shape."

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185`` `````` #include #include using namespace std; class TreeNode { public: void insert_node(TreeNode* new_node); void print_nodes() const; bool find(string value) const; private: string data; TreeNode* left; TreeNode* right; friend class BinarySearchTree; }; class BinarySearchTree { public: BinarySearchTree(); void insert(string data); void erase(string data); int count(string data) const; void print() const; private: TreeNode* root; }; BinarySearchTree::BinarySearchTree() { root = NULL; } void BinarySearchTree::print() const { if (root != NULL) root->print_nodes(); } void BinarySearchTree::insert(string data) { TreeNode* new_node = new TreeNode; new_node->data = data; new_node->left = NULL; new_node->right = NULL; if (root == NULL) root = new_node; else root->insert_node(new_node); } void TreeNode::insert_node(TreeNode* new_node) { if (new_node->data < data) { if (left == NULL) left = new_node; else left->insert_node(new_node); } else if (data < new_node->data) { if (right == NULL) right = new_node; else right->insert_node(new_node); } } int BinarySearchTree::count(string data) const { if (root == NULL) return 0; else if (root->find(data)) return 1; else return 0; } void BinarySearchTree::erase(string data) { // Find node to be removed TreeNode* to_be_removed = root; TreeNode* parent = NULL; bool found = false; while (!found && to_be_removed != NULL) { if (to_be_removed->data < data) { parent = to_be_removed; to_be_removed = to_be_removed->right; } else if (data < to_be_removed->data) { parent = to_be_removed; to_be_removed = to_be_removed->left; } else found = true; } if (!found) return; // to_be_removed contains data // If one of the children is empty, use the other if (to_be_removed->left == NULL || to_be_removed->right == NULL) { TreeNode* new_child; if (to_be_removed->left == NULL) new_child = to_be_removed->right; else new_child = to_be_removed->left; if (parent == NULL) // Found in root root = new_child; else if (parent->left == to_be_removed) parent->left = new_child; else parent->right = new_child; return; } // Neither subtree is empty // Find smallest element of the right subtree TreeNode* smallest_parent = to_be_removed; TreeNode* smallest = to_be_removed->right; while (smallest->left != NULL) { smallest_parent = smallest; smallest = smallest->left; } // smallest contains smallest child in right subtree // Move contents, unlink child to_be_removed->data = smallest->data; if (smallest_parent == to_be_removed) smallest_parent->right = smallest->right; else smallest_parent->left = smallest->right; } bool TreeNode::find(string value) const { if (value < data) { if (left == NULL) return false; else return left->find(value); } else if (data < value) { if (right == NULL) return false; else return right->find(value); } else return true; } void TreeNode::print_nodes() const { if (left != NULL) left->print_nodes(); cout << data << "\n"; if (right != NULL) right->print_nodes(); } int main() { BinarySearchTree t; t.insert("D"); t.insert("B"); t.insert("A"); t.insert("C"); t.insert("F"); t.insert("E"); t.insert("I"); t.insert("G"); t.insert("H"); t.insert("J"); t.erase("A"); // Removing leaf t.erase("B"); // Removing element with one child t.erase("F"); // Removing element with two children t.erase("D"); // Removing root t.print(); cout << t.count("E") << "\n"; cout << t.count("F") << "\n"; return 0; }``````

If I understand what the question is asking, I need to change this:

 ``12345`` ``````void BinarySearchTree::print() const { if (root != NULL) root->print_nodes(); }``````

which is a pointer to:

 ``12345678`` ``````void TreeNode::print_nodes() const { if (left != NULL) left->print_nodes(); cout << data << "\n"; if (right != NULL) right->print_nodes(); }``````

From here, I get lost because pointers is also a weak spot for me.

Any help anyone could offer would be amazing!

Thanks!

ToonHead
Last edited on
If such shape is good enough, there's an example - just add extra argument to printing function:
 ``123456789101112131415161718192021`` ``````void BinarySearchTree::print() const { if (root != NULL) root->print_nodes(0); } void TreeNode::print_nodes(int level) const { string indent; for(int i = 1; i < level; i++) indent += " "; cout << "\n" << indent; if (level) cout << "|_"; cout << data; if (left != NULL){ left->print_nodes(level + 1); } if (right != NULL) { right->print_nodes(level + 1); } }`````` ```D |_B |_A |_C |_F |_E |_I |_G |_H |_J```

 ``123456789101112131415`` ``````// For things like: D // Determining at which width / \ // to start seems impossible / \ // without a node knowing B F // all it's parents and children / \ / \ A C E I / \ G J / H // ...I don't know, sorry. `````` ```or even: D |_B | |_A | |_C // These vertical lines are loosing me |_F |_E |_I |_G | |_H |_J ```

Last edited on
it makes complete sense. I don't know if I could have come up with that.

Thanks JockX.

ToonHead
Last edited on
Topic archived. No new replies allowed.