Solved

Help on BST

Posted on 2003-12-01
3
225 Views
Last Modified: 2010-04-01
I'm writing a program using BST.  The program stores city code, city name, its crime rate, and its state which the city is located.  I can serach the database by citycode(unique key), but I do not know how to handle to search by its city name as well.  It must be able to search both either by the city code or city name. Any idea???

Thanks,
Raymond
0
Comment
Question by:templeavenue
3 Comments
 
LVL 11

Accepted Solution

by:
bcladd earned 25 total points
Comment Utility
Can you traverse the entire tree? That is, can you write a function that visits every node in the tree? Perhaps a pre-order traversal? Imagine looking for the non-key data using a  traversal function that returns a pointer to the matching node (if found) and NULL otherwise. Then, instead of ALWAYS visiting current and then calling traverse left and then traverse right you will check if current is the one you want. If so, return the pointer; else, traverse left and if it returns non-NULL, return that value; else traverse right and return that value.

Hope this helps, -bcl
0
 
LVL 1

Expert Comment

by:travd
Comment Utility
If you need to have fast search for both the citycode and the cityname, consider a secondary BST that will have city name as the key, and the value is a pointer to the relevant node in the first tree.  You would also need to have a pointer in the primary tree so that if you delete a node, for example, you can delete the secondary node also.
0
 
LVL 9

Expert Comment

by:jhshukla
Comment Utility
make two BST's _sharing_ the same nodes.
class Node{
  //data
  Node *codeLeft, *codeRight;
  Node *nameLeft, *NameRight;
};

one BST uses code pointers while the other uses name pointers. Note that a given node's children may be different in different BST's. For Example:
codeBST has:
         A
       /   \
     B      C

nameBST has:
         C
       /   \
     B      A

As in the example above, even the roots may differ. Be careful with pointers.

Good luck
Jaydutt
0

Featured Post

IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

Suggested Solutions

Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…

763 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now