[TheExitWound]

Here's the assignment:

Quote

Write a program that:
-reads a sentence from cin
-separates words and inserts them in BST
-prints the tree (inorder traversal)
-prompts for a word to be deleted from BST
-prints the tree (inorder traversal)
-Write a template Insert function for inserting new words into the tree.
-Write a template Delete function for deleting words from the tree.

I don't really know how to continue. I'm attempting to write the INSERT function that will insert the string into the tree at the correct point using recursion. However, I cannot get the data types to match up. I don't know how to compare the values in the TreeNode->Left with the data or completely set up the insertion recursion.

...snippet (eliminating includes)....

template <typename T>
class TreeNode
{
public:
	//init-constructor
	TreeNode(const T& value, TreeNode<T>* left = NULL, TreeNode<T>* right = NULL)
	{
		Value = value;
		Left = left;
		Right = right;
	}

	//get value
	const T GetValue() const
	{
		return Value;
	}
	//get Left
	TreeNode<T>* GetLeft() const
	{
		return Left;
	}
	//get Right
	TreeNode<T>* GetRight() const
	{
		return Right;
	}

private:
	T Value;
	TreeNode<T>* Left;
	TreeNode<T>* Right;
};



//insert a leaf
template <typename T>
void Insert(TreeNode<T>*& root, const T& data)
{
	if (root == NULL)
	{
		root = new TreeNode<T>(data);
	}
	else
	{
		if (root->GetValue() == data)
		{
			return;
		}//end if CNV==data
		else 
		{
			if (root->GetValue() > data)
			{
				
			}
		}//end if CNV>data
	} //end else
}



void main()
{

	//string
	string myString;
	//set root to null
	TreeNode<string>* treeRoot = NULL;



	cout << "Enter a string.  " << endl;
	while (cin.peek() != '\n')
	{
		cin >> myString;
		Insert(treeRoot, myString);
	}

	system("pause");
}

[hatt]

Here's some pseudo-code for an insert

if ( the inserted value compared to the data is < 0 )
   if ( left node is null )
      then create the node and insert value
   else
       insert into the tree, sending leftNode and the value //(this is where you call insert for recursion)

else if ( the inserted value compared to the data is > 0 )
     if ( right node is null )
        then create the node and insert value
     else
         insert into the tree, sending rightNode and value //(this is where you call insert for recursion)

I, personally, would have two functions. One you initially call (insertItem or something) that would check if root is null, and if it's not, it will then call insert and send the root and the inserted value. Once inside insert, you need to compare the value to that of the right side and the left side, checking if null, and percolate down.

This post has been edited by hatt: 23 March 2010 - 04:38 PM

[KYA]

Sha zam!

[TheExitWound]

We're a second semester class so efficiency and such is overlooked (for the most part). For instance, we don't have to destroy any memory allocated by the 'new' operator in this case.

*I don't know why you'd check for isNull first to call insert instead of putting the check inside the Insert function.

*Also, I don't know how to compare the inserted value with the value inside the current node you're pointing to. I end up with "unable to convert <blah> to <blah>" because they're different data types.

I understand the logic behind binary search trees. I simply cannot implement them. I don't know what I'm doing wrong.

[KYA]

TheExitWound, on 23 March 2010 - 05:10 PM, said:

We're a second semester class so efficiency and such is overlooked (for the most part). For instance, we don't have to destroy any memory allocated by the 'new' operator in this case.

Holy crap. That's not efficiency, that's terrible guidance/instruction.

[TheExitWound]

KYA, on 23 March 2010 - 04:18 PM, said:

Holy crap. That's not efficiency, that's terrible guidance/instruction.

I think it's temporary to show us how the the trees and crap work before getting too detailed. We KNOW we have to take care of the memory, but as i look at this code, it's big and obnoxious and scary and way too complicated for me to grasp in one lesson anyway, let alone having to worry about destructors atop it.

I simply cannot code a BST. I can't follow all of the ifs and elses and flow.

[TheExitWound]

When I attempt to do this, I end up with:

Quote

'Insert' : cannot convert parameter 1 from 'TreeNode<T> *' to 'TreeNode<T> *&'

. I don't know how to avoid this. (the insert is incomplete so far)

	//set Left
	void SetLeft(TreeNode<T>* newLeft) 
	{
		Left = newLeft;
	}


template <typename T>
void Insert(TreeNode<T>*& root, const T& data)
{
	//if tree is empty
	if (root == NULL)
		root = new TreeNode<T>(data);
	//if tree is not empty
	else {
		//if root value > inserting data
		if (root->GetValue() > data)
		{
			//if left child is empty, create the new leaf
			if (root->GetLeft() == NULL)
				root->SetLeft(new TreeNode<T>(data));
			//if not empty, traverse left
			else {
				Insert(root->GetLeft(),data);
			}
		}//end if >

	}//end not empty tree
}

[TheExitWound]

Anyone offer some help?

[KYA]

Did you read my link?

template<class T>
void BinarySearchTree<T>::addNode(T element){
        if (root == NULL){
                root = new Node<T>(element);
                size++;
                return;
        }
        else if (containsElement(element)){
                cout << "Tree already has value [" << element << "], insertion aborted." << endl;
                return;
        }
        else{
                add(root, element);
        }
}

template<class T>
bool BinarySearchTree<T>::containsElement(T element){
        curNode = root;
        while(curNode != NULL){
                if(curNode->getData() == element){
                        return true;
                }
                else {
                        if(element > curNode->getData())        curNode = curNode->getRightChild();
                        else curNode = curNode->getLeftChild();
                }
        }
        return false;
}

template<class T>
void BinarySearchTree<T>::add(Node<T>* root, T element){
        //we want to maintain a somewhat balanced tree
        //so we'll do a binary search tree check
        
        //lesser values to the left, greater to the right
        if (element < root->getData()){
                if(root->getLeftChild() != NULL){
                        add(root->getLeftChild(), element);
                }
                else{
                        root->setLeftChild(new Node<T>(element));
                        size++;
                }
        }
        else{
                if(root->getRightChild() != NULL){
                        add(root->getRightChild(), element);
                }
                else{
                        root->setRightChild(new Node<T>(element));
                        size++;
                }
        }
}