Binary Search Tree Help

[toonhead85]

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."

 #include <iostream>
#include <string>

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:

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

which is a pointer to:

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

[JockX]

If such shape is good enough, there's an example - just add extra argument to printing function:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

// 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

[toonhead85]

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

Thanks JockX.

ToonHead