Binary Search Tree - create new node

[tones1986]

Hey All - i working on a assignment for school. Given that, i would like to say i have attempted numerous ways to get this working, and its a simple part of teh assignment. Basically i am having problems with my 'insert node' method. I am unsure how i have to declare the new node... example of my problem below:

BSTNode<T> * newNode;
newNode->data = newitem; (new item is the informaiton passed to the Insert method)

My class for a node is as follows:

template <class T>
class BSTNode
   {
   friend class BSTree<T>;

   private:
      T data;

      BSTNode<T>* left;
      BSTNode<T>* right;

   public:
      BSTNode(const T&);
   };

So i should be able to make a call to the constructor passing in the newitem argument as the data member... my constructor looks like:

template <class T>
BSTNode<T>::BSTNode(const T& item)
{
  data = item;
  left = right = NULL;
}

I was trying things such as:

BSTNode<T>(newItem);

But, as you can probably tell, i dont have a way to reference this new node that would be created, plus its not a pointer - so i wont have access via nodeName->data; right?

Sorry if this seems slow, or very easy ... but this is brand new to me, and im just trying to get my mind around it.

PS. I know the code for the insert is pretty much correct, as this was taken from in class notes from my professor, (i had to add code where he basically told us ... you need a to do b in this part, and c to do d in this area etc etc)

Hope this makes sense to someone!

Thank you in advance

[tones1986]

Well, i think i have sorted it out just now on my own, but maybe someone could confirm ...

I used the new keyword to make this work...

BSNode<T> * mynwenode;
mynewnode = new BSNode<T>(newdata);

This should do what i want correct? As it creates new dynamically allocated memory as a pointer to the new node?!?

Thanks again

[Radical Edward]

> This should do what i want correct?
That's it. :) If you declare a pointer to BSNode<T>, that's all you have, a pointer. You can't reliably use that pointer until you set it to point to null or an address that reserves enough memory to hold an actual BSNode<T> object.

[tones1986]

Thank you for your response - good to know im on the right track.

Another thing has popped up for me. I am attempting to print my binary tree in preorder traversal way... and i have to use 2 functions, one which is private (recursive - calls itself to continally print current->left/rigth etc) while the public print method calls the recursive function... as follows:

template <class T>
void BSTree<T>::printPreorder() const
{
  preTrav(root);        
}
   
template <class T>
void BSTree<T>::preTrav(BSTNode<T> * current)
{
 if (current != NULL)
    {
    cout << current->data << " ";
    preTrav(current->left);
    preTrav(current->right);
    }
}

The calling code is:

cout << "Preorder:  ";  t1.printPreorder();  cout << endl;

I get the following error:
259 \assign8\BSTree.h passing `const BSTree<int>' as `this' argument of `void BSTree<T>::preTrav(BSTNode<T>*) [with T = int]' discards qualifiers

Im assuming this basically means that when i call this function, nothing is being passed, so when i attempt to pass root to preTrav i get this error... but i was also thinking that as im calling the function as t1. this should give me access to the root of the t1 binary tree correct?

Am i mistaking this for somethign else? Do i have to reference the 'root' different in the call within the printPreorder() function?

Hope you can help me out once again!

Thanks in advance as always

[Radical Edward]

The public method is const but the private method is not const. Edward's recommendation is to make everything const right away and then remove the ones that give a compiler error:

void BSTree<T>::preTrav(const BSTNode<T> * current) const

[tones1986]

Thanks for all of the help - i have come across another issue with this program. I have most of the code done, besides a function called copyTree()

Here is the prototype:
BSTNode<T>* copyTree(BSTNode<T>*);

And the function needs to:
It needs to be recursive - copying the nodes of a tree. If the pointer is null, return NULL. otherwise - create a new node and copy data from the node to copy into it. set the new nodes left link to the result of copyTree() for the node to copy the left subtree....and the same for the right hand side.

So i have the logic down...but im unsure how to get this into words. I tried this sort of:

template <class T>
BSTNode<T> * BSTree<T>::copyTree(BSTNode<T> * copyRoot)
{  
if (copyRoot == NULL)
   return NULL;
else
{
BSTNode<T> * newNode;
 newNode = new BSTNode<T>;
newNode->data = copyRoot->data;
newNode->left = copyTree(copyRoot->left);
newNode->right = copyTree(copyRoot->right);
return newNode;
}
}

Does this seem like it would work?

Could i get some input please?

Thanks in advance!

[Radical Edward]

Edward is guessing about how your tree interface is, but something like this makes sense if you're making a copy of the current tree and need a full tree in return:

//
// Non-recursive user interface
//
template <typename T>
BSTree<T> BSTree<T>::copyTree() const
{
  BSTree<T> result;

  copyTree(_root, result);

  return result;
}

//
// Recursive copy helper
//
template <typename T>
void BSTree<T>::copyTree(BSTNode<T> *root, BSTree<T>& newTree)
{
  if (root != NULL) {
    newTree.AddNode(root->data);
    copyTree(root->left, newTree);
    copyTree(root->right, newTree);
  }
}