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

Re: fatal error c1083 in C#

26-Mar-10 9:44

damn... that works

I see what I did wrong now.

Thanks a lot for your help.

fatal error c1083 in C#

sindhumahe26-Mar-10 4:13

sindhumahe

26-Mar-10 4:13

hi i am tryingto build astatic library. and while i build i get this fatal error, kindly help me rectify this.

fatal error C1083: Cannot open include file: 'BasicHashTable.hh': No such file or directory

C^hris L^osinger26-Mar-10 4:17

C^hris L^osinger

26-Mar-10 4:17

if this is a C# question, it's in the wrong forum.

if it's a C++ question, then you have to either tell the compiler where to find BasicHashTable.hh or, put BasicHashTable.hh in a place where the compiler is already looking.

image processing toolkits | batch image processing

Button Caption

shiv@nand26-Mar-10 3:13

shiv@nand

26-Mar-10 3:13

i have created a 5 Buttons dynamically.
eg :
2) Button 1 contol id :5000
1) Button 2 contol id :5001
1) Button 3 contol id :5002
1) Button 4 contol id :5003
1) Button 5 contol id :5003,

i need to select caption name "Button 1" using its control id 5000;
i used RButtonup and i got control id. But i dont know how to get the caption of Button .Please help.

CPallini26-Mar-10 3:21

CPallini

26-Mar-10 3:21

Assuming your controls are in a dialog box: If you are using Win32 then you may call SendDlgItemMessage (with WM_GETTEXT or WM_SETTEXT, depending on your needs).
In a similar way you may use MFC's CWnd::SendDlgItemMessage.
Smile | :)

If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.

This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
-- Iain Clarke

[My articles]

shiv@nand26-Mar-10 3:31

shiv@nand

26-Mar-10 3:31

CWnd::SendDlgItemMessage,
i have no idia if you give example, it is very helpful to me.

CPallini26-Mar-10 3:39

CPallini

26-Mar-10 3:39

Inside a method of your window class (the parent window of your buttons) call, for instance:

SendDlgItemMessage(5000, WM_SETTEXT, 0 , (LPARAM) _T("BUTTON 0"));