Go Premium for a chance to win a PS4. Enter to Win

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 234
  • Last Modified:

Help on BST

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
templeavenue
Asked:
templeavenue
1 Solution
 
bcladdCommented:
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
 
travdCommented:
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
 
jhshuklaCommented:
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

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now