Dictionary search in binary search tree

2007-09-01 4:58 am

how to search the bstree so that it gives all the word within the sorted tree start with the same input prefix? (like dictionary search), you type in the prefix, it returns all the word in a list which start with the prefix input...

What's the algorithm ??

更新1:

you are not answering my question. My question is, for example , all the words are already stored in the bstree, now i enter a prefix, it should return all the phrases which start with the prefix.

更新2:

e.g. I enter : vat it should gives (if they are in the tree) vata vatkb vatrke vatlslei vatkewjo vatkdow ---- there is no more phrases start with vat ;

更新3:

YOU ARE RIGHT! I don't know how to search a substring within a string !

回答 (1)

garlic2010

2007-09-01 10:52 pm

✔ 最佳答案

To search a tree and its branches, the common way is to call a recursive function that searches a lower level of the branch. At each branch level, the recursive function is called so that a lower level is searched until there is no further lower level.

Visit this answer for reference:
http://hk.knowledge.yahoo.com/question/?qid=7007060801276

and take note of the TraverseFolders function.

2007-09-02 06:29:30 補充：
I am telling you how to navigate through a tree and its branches by calling a recursive function. I don't know that you do not know the easy stuff like finding a substring within a string.Search for VB's Instr(), java's substring(), strstr(), strchr(), strrchr(), SubString() in C.

2007-09-02 06:31:44 補充：
The answer link I showed you displays only names that ended with ".txt". Isn't that SIMILAR to what you want?

2007-09-02 06:33:15 補充：
It is not my fault if I am not answering your question. It is YOU not stating your question properly.

2007-09-05 04:15:43 補充：
I am sorry If I sounded too harsh to you. Nobody is perfect. Let us hope all will benefit from this forum.

👍 0 👎 0