A prefix tree is a data structure with many uses. I won't go into details about this data structure Wikipedia does a better job than I could. What I will do is post a C# implementation of this data structure and in a following post I will show how to use this data structure when implementing an auto-complete solution.
These are the properties of a prefix tree:
- it stores strings(finite sequences of chars)
- it had nodes :) (doooooooh!)
- each node stores a character
- each node can have a number of subnodes(0,1,2, ... infinity)
- the char stored in a subnode is the one following the char stored by the node in a string
- each node has a flag which is raised if a word ends there(this doesn't mean it can't have subnodes for example a prefix tree can store the words "cat" and "catastrophy" in this case node 3 stores 't' and has a subnode that stores 'a')
The node:
The tree:
The tree:
The main program:
The AddWord and Find function seem to be incomplete. I dont understand why they have the XML nodes and the Node class ends with . Am I missing something?
RăspundețiȘtergere@Mujahid Shariff yes there seems to be some kind of an error with the code highlighting script
RăspundețiȘtergereI'll try and fix it first time I get