|
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
|
|
|
|
|
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:
#include "TreeException.h"
#include "TreeNode.h"
typedef void (*FunctionType)(TreeItemType& anItem);
class BinarySearchTree
{
public:
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);
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:
TreeNode *root;
};
in TreeNode.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 BinarySearchTree;
};
in keyeditem.h
typedef int KeyType;
class KeyedItem
{
public:
KeyedItem() {}
KeyedItem(const KeyType& keyValue)
: searchKey(keyValue) {}
KeyType getKey() const
{ return searchKey;
}
private:
KeyType searchKey;
};
Thanks again for the quick response.
|
|
|
|
|
While not complete, I came up with something like:
void MyCallback( TreeItemType& anItem )
{
cout << anItem.getKey();
}
void main( void )
{
BinarySearchTree bst;
TreeItemType key(1);
bst.searchTreeInsert(key);
bst.preorderTraverse(MyCallback);
}
"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
|
|
|
|
|
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);
}
^^That function calls this function below(still in bst.cpp):
void BinarySearchTree::insertItem(TreeNode *& treePtr,
const TreeItemType& newItem)
throw(TreeException)
{
if (treePtr == NULL)
{
try
{
treePtr = new TreeNode(newItem, NULL, NULL);
}
catch (bad_alloc e)
{
throw TreeException(
"TreeException: insertItem cannot allocate memory");
}
}
else if (newItem.getKey() < treePtr->item.getKey())
insertItem(treePtr->leftChildPtr, newItem);
else
insertItem(treePtr->rightChildPtr, newItem);
}
|
|
|
|
|
the code you just posted:
void MyCallback( TreeItemType& anItem )
{
}
void main( void )
{
BinarySearchTree bst;
TreeItemType key(1);
bst.searchTreeInsert(key);
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.
|
|
|
|
|
According to the function's signature that you initially posted, it should return a void .
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?
"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
|
|
|
|
|
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.
|
|
|
|
|
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?
"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
|
|
|
|
|
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.
|
|
|
|
|
It should be:
void showNumber( TreeItemType& iTreeNumber )
{
cout << iTreeNumber.getKey();
}
"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
|
|
|
|
|
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.
|
|
|
|
|
Then the problem is with code you've not shown. I've taken each of your code snippets and it compiles fine.
"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
|
|
|
|
|
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.
|
|
|
|
|
Member 3822532 wrote: So you were able to call the BST's preorder traversal in main?
Exactly like this.
"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
|
|
|
|
|
damn... that works
I see what I did wrong now.
Thanks a lot for your help.
|
|
|
|
|
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
|
|
|
|
|
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.
|
|
|
|
|
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.
|
|
|
|
|
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 .
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]
|
|
|
|
|
CWnd::SendDlgItemMessage,
i have no idia if you give example, it is very helpful to me.
|
|
|
|
|
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"));
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]
|
|
|
|
|
no i am not getting, please is there any sample code.
|
|
|
|
|
If you post your (relevant) code may be I can tell you how to modify it.
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]
|
|
|
|
|
ON_COMMAND_RANGE(5000,5100,OnButtonRange)
void CTest::OnShowWindow(BOOL bShow, UINT nStatus)
{
CDialog::OnShowWindow(bShow, nStatus);
CButton* m_btDynamic;
CString csText;
int k=0;
for(int i=0;i<5;i++)
{
m_btDynamic = new CButton();
csText.Format(L"Button %d",i+1);
m_btDynamic->Create(csText, BS_FLAT|WS_VISIBLE|WS_CHILD|BS_PUSHBUTTON|BS_ICON,
CRect(10+k ,10+k,60+k,60+k),this, 5000+i);
k=k+30;
}
}
void CTest::OnButtonRange(UINT nIDforControl)
{
int iSelectedControlID;
iSelectedControlID = nIDforControl;
// here i want button caption
}
Where i should use SendDlgItemMessage()
|
|
|
|
|
Well, you already set the caption for you button with known values, so what's your need now?
BTW I suggest you to maintain the CButton pointers in a member variable:
in class declaration:
CButton * m_btDynamic[5];
then, in you function you may do
void CTest::OnShowWindow(BOOL bShow, UINT nStatus)
{
CDialog::OnShowWindow(bShow, nStatus);
CString csText;
int k=0;
for(int i=0;i<5;i++)
{
m_btDynamic[i] = new CButton();
csText.Format(L"Button %d",i+1);
m_btDynamic[i]->Create(csText,BS_FLAT|WS_VISIBLE|WS_CHILD|BS_PUSHBUTTON|BS_ICON,
CRect(10+k ,10+k,60+k,60+k),this, 5000+i);
k=k+30;
}
}
so that whenever you need to access the caption of, say, third button, you may call
m_btDynamic[2]->GetWindowText();
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]
|
|
|
|