C / C++ / MFC

26-Mar-10 4:52

Hi everyone, I was wondering if you guys could help
me out on how I should go about building this function in main
to be able to search through binary tree class(it's actually called
BinarySearchTree and is virtual from a TreeNode class, but that isn't really important).

So here is the code for BST.h that I'm trying to build the function for:

in BST.H:

typedef void (*FunctionType)(TreeItemType& anItem);

some ways BST.h uses FunctionType are...

virtual void preorderTraverse(FunctionType visit);

TreeItemType is a ADT from another class called keyeditem who's node is
of the int datatype.

I need to write a function in main to be able to work with the BST traversals.
I'm using Microsoft visual studio for the solution.

Thanks in advance!

David Crow26-Mar-10 5:28

26-Mar-10 5:28

To my knowledge, a binary search tree (BST) can be traversed (e.g., searched) in four different ways: pre-oder, in-order, post-order, and level-order. Other ways may exist but these are at least the most popular.

While not a direct answer to your question, I'll offer this just in case it may help. I have a very basic "binary tree" project that I refer to on occasion. Its preorder() traversal function looks like:

void preorder( node *n )
{
    cout << n->data << endl;
    
    if (n->left != 0)
        preorder(n->left);
  
    if (n->right != 0)
        preorder(n->right);
}

It is called from main() and is passed the address of the root node.

"One man's wage rise is another man's price increase." - Harold Wilson

"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons

"Man who follows car will be exhausted." - Confucius

Member 382253226-Mar-10 6:45

26-Mar-10 6:45

Thanks for your quick response.
Unfortunately, I don't think that your solution works with mine.
I tried implementing it, but the your node(in your code) behaves differently from mine.
Mine is actually called a TreeNode, and its members are private, so I can't access them.

Here, I'm going to post all of the code:

IN BST.H:

/** @file BST.h */
#include "TreeException.h"
#include "TreeNode.h"

typedef void (*FunctionType)(TreeItemType& anItem);


class BinarySearchTree
{
public:
// constructors and destructor:
   BinarySearchTree();
   BinarySearchTree(const BinarySearchTree& tree)
      throw(TreeException);
   virtual ~BinarySearchTree();


   virtual bool isEmpty() const;


   virtual void searchTreeInsert(const TreeItemType& newItem)
      throw(TreeException);

  
   virtual void searchTreeDelete(KeyType searchKey)
      throw(TreeException);

 
   virtual void searchTreeRetrieve(KeyType searchKey,
				   TreeItemType& treeItem) const
      throw(TreeException);

   virtual void preorderTraverse(FunctionType visit);


   virtual void inorderTraverse(FunctionType visit);

  
   virtual void postorderTraverse(FunctionType visit);

// overloaded operator:
   virtual BinarySearchTree& operator=(const BinarySearchTree& rhs)
      throw(TreeException);

protected:

   void insertItem(TreeNode *& treePtr,
                   const TreeItemType& newItem)
      throw(TreeException);

   void deleteItem(TreeNode *& treePtr, KeyType searchKey)
      throw(TreeException);


   void deleteNodeItem(TreeNode *& nodePtr);

   
   void processLeftmost(TreeNode *& nodePtr,
                        TreeItemType& treeItem);


   void retrieveItem(TreeNode *treePtr, KeyType searchKey,
                     TreeItemType& treeItem) const
      throw(TreeException);


   void copyTree(TreeNode *treePtr, TreeNode *& newTreePtr) const
      throw(TreeException);
   void destroyTree(TreeNode *& treePtr);

   void preorder(TreeNode *treePtr, FunctionType visit);
   void inorder(TreeNode *treePtr, FunctionType visit);
   void postorder(TreeNode *treePtr, FunctionType visit);

   TreeNode *rootPtr() const;
   void setRootPtr(TreeNode *newRoot);

   void getChildPtrs(TreeNode *nodePtr,
                     TreeNode *& leftChildPtr,
                     TreeNode *& rightChildPtr) const;
   void setChildPtrs(TreeNode *nodePtr,
                     TreeNode *leftChildPtr,
                     TreeNode *rightChildPtr);

private:
   /** Pointer to root of tree. */
   TreeNode *root;
}; // end BinarySearchTree
// End of header file.

in TreeNode.h:

/** @file TreeNode.h */
//TreeNode559.h
#include "KeyedItem.h"

typedef KeyedItem TreeItemType;


class TreeNode
{
private:
   TreeNode() {}
   TreeNode(const TreeItemType& nodeItem,
            TreeNode *left = NULL, TreeNode *right = NULL)
      : item(nodeItem), leftChildPtr(left),
      rightChildPtr(right) {}

   
   TreeItemType item;
   
   TreeNode *leftChildPtr, *rightChildPtr;

   // friend class - can access private parts
   friend class BinarySearchTree;
}; // end TreeNode

in keyeditem.h

/** @file KeyedItem.h */
//KeyedItem559.h

typedef int KeyType;


class KeyedItem
{
public:
   KeyedItem() {}
   KeyedItem(const KeyType& keyValue)
      : searchKey(keyValue) {}
   KeyType getKey() const
   {  return searchKey;
   }  // end getKey
private:
   KeyType searchKey;
}; // end KeyedItem

Thanks again for the quick response.

David Crow26-Mar-10 7:35

26-Mar-10 7:35

While not complete, I came up with something like:

// presumably gets called for each node in the tree
void MyCallback( TreeItemType& anItem )
{
    cout << anItem.getKey();
}
  
void main( void )
{
    BinarySearchTree bst;
    TreeItemType key(1);
  
    bst.searchTreeInsert(key);
    bst.preorderTraverse(MyCallback);
}

Member 382253226-Mar-10 8:03

26-Mar-10 8:03

Yes I thought so too, that I had to "friend" the BST class.
But my instructions are to implement the function in main.

here's the insert function in bst.cpp:

void BinarySearchTree::searchTreeInsert(const TreeItemType& newItem)
   throw(TreeException)
{
   insertItem(root, newItem);
}  // end searchTreeInsert

^^That function calls this function below(still in bst.cpp):

void BinarySearchTree::insertItem(TreeNode *& treePtr,
				  const TreeItemType& newItem)
   throw(TreeException)
{
   if (treePtr == NULL)
   {  // position of insertion found; insert after leaf

      // create a new node
      try
      {
	 treePtr = new TreeNode(newItem, NULL, NULL);
      }
      catch (bad_alloc e)
      {
	 throw TreeException(
	 "TreeException: insertItem cannot allocate memory");
      }  // end try
   }
   // else search for the insertion position
   else if (newItem.getKey() < treePtr->item.getKey())
      // search the left subtree
      insertItem(treePtr->leftChildPtr, newItem);

   else  // search the right subtree
      insertItem(treePtr->rightChildPtr, newItem);
}  // end insertItem

Member 382253226-Mar-10 8:09

26-Mar-10 8:09

the code you just posted:

// presumably gets called for each node in the tree
void MyCallback( TreeItemType& anItem )
{
    // getting access to a TreeNode object here is still in question
}
  
void main( void )
{
    BinarySearchTree bst;
    TreeItemType key(1);
  
    bst.searchTreeInsert(key); // should be adding a TreeNode object ??
    bst.preorderTraverse(MyCallback);
}

Its what I tried first, but i kept getting an error saying the the function MyCallBack(in your case) needs to return a FunctionType value.

David Crow26-Mar-10 8:11

26-Mar-10 8:11

According to the function's signature that you initially posted, it should return a void. Confused | :confused:

Member 3822532 wrote:
Its what I tried first, but i kept getting an error saying the the function MyCallBack(in your case) needs to return a FunctionType value.

What line is the compiler complaining about?

Member 382253226-Mar-10 8:24

26-Mar-10 8:24

Yes, exactly! And that's why I'm frustrated!

the typedef definition in BST.h:

typedef void (*FunctionType)(TreeItemType& anItem);

That means the function FunctionType is void right?
or does it mean that it is of FunctionType value and thus needs to return that value?

I know that my misunderstanding of that one line of code is what is causing me all the problems.

David Crow26-Mar-10 8:36

26-Mar-10 8:36

Member 3822532 wrote:
That means the function FunctionType is void right?

It means that it returns a void.

What does your implementation of this function look like?

Member 382253226-Mar-10 8:55

26-Mar-10 8:55

Sorry that's what I meant to say.
It returns void, but I keep getting the error that it needs to return the value FunctionType.

So here is the implementation.
This is what I did in response to the error.
I don't think this is right, but I got no error when I tried compiling the code.

FunctionType showNumber(TreeItemType& iTreeNumber)
{


return showNumber(iTreeNumber);
}

This causes a recursive error.

David Crow26-Mar-10 8:58

26-Mar-10 8:58

It should be:

void showNumber( TreeItemType& iTreeNumber )
{
    cout << iTreeNumber.getKey();
}

Member 382253226-Mar-10 9:15

26-Mar-10 9:15

yeah.

Before posting this problem on the boards, I had tried attaching void as the function sig:

void showNumber( TreeItemType& iTreeNumber )
{
    cout << iTreeNumber.getKey();
}

and this is error i get:

"cpp(74) : error C2664: 'BinarySearchTree::preorderTraverse' : cannot convert parameter 1 from 'void' to 'FunctionType'"

then i tried this.

FunctionType showNumber( TreeItemType& iTreeNumber )
{
    return showNumber(iTreeNumber);
}

for no error, but not the correct solution.

David Crow26-Mar-10 9:29

26-Mar-10 9:29

Then the problem is with code you've not shown. I've taken each of your code snippets and it compiles fine.

Member 382253226-Mar-10 9:34

26-Mar-10 9:34

Wow, I wonder what it is then.

So you were able to call the BST's preorder traversal in main?

like so:

cTree1.preorderTraverse(showNumber(iFromTree));

By the way, thanks for all your quick responses.

David Crow26-Mar-10 9:36

26-Mar-10 9:36

Member 3822532 wrote:
So you were able to call the BST's preorder traversal in main?

Exactly like this.

Member 382253226-Mar-10 9:44