I might suggest changing btree_node to bst_node or some such. There is a structure called a
B-tree, which is quite different from a BST, and I was confused when I first read your post.
@csharp100
oogabooga's struct names are still more descriptive than yours, however, so I would adopt them. It will also make it more clear the relationship between your two data structures. He's also right about the regex, it's overkill.
From your example, it appears that the node_num/key in the binary tree is the length of the strings. Given that you only allow for 9 characters in the list node, you only have room for 8 characters (remember, +1 for the NULL), which means you will only have at most 8 nodes in your binary tree. Binary trees are generally better suited for larger sets of data, otherwise the overhead of managing the tree outweighs the benefit of fast inserts, lookups and deletes. If you have such a small, fixed maximum string length, you would be better off with an array of 8 lists. And by the way, you should make that a #define, no
magic numbers!
However, if you really want to use a BST, then my first sugggestion is to stop thinking of this as some bastard hybrid data structure. There is a BST, and it has some arbitrary data stored in each node. Whether that data is an int, a float, a string or a linked list or strings is irrelevant to finding the correct place to insert or lookup a node. Same goes for your list. Work out your BST and list and test them separately, then write a function that combines bst_insert and list_insert. Also, I suggest you read up on BST tutorials. The recursive approach to insert and lookup are much simpler than the iterative one.
Start by building a simpler BST, don't worry about the list part yet. Add a member to the tree node called count, make it an int. When you "insert" a string into the tree, if a node for that string length exists, simply increment count. Otherwise, create a new node, set count to 1 and insert that node in the tree. Something like:
Code:
bst_node *bst_insert(bst_node *root, const char *data, int len)
{
if root is NULL
// create new node and set count to 1
if len < root->key
// recursively insert into left sub-tree
else if len > root->key
// recursively insert into right sub-tree
else
// increment count
}
Write similar bst_lookup, bst_delete and bst_print functions as needed. The print function is probably best done as an in-order traversal, which prints out the key/strlen of each node, and the count of how many strings of that length have been "inserted". This will be useful for testing. Write little bits at a time, testing as you go. When your BST code is done, you can move on to the list, knowing it works.
Your list might need the following functions:
Code:
list_node *list_insert(list_node *head, const char *data) // insert data into list, returning the new head
list_node *list_find(list_node *head, const char *key) // find key in list, returning pointer to the node
list_node *list_delete(list_node *head, const char *key) // delete node containing key from list, returning new head
void list_print(list_node *head) // print list
Take the same approach as the BST. Keep it simple to start, and pretend the other half of your data structure doesn't exist. Write little bits at a time, testing as you go. Once you have that finished, you know the list half of your data structure will work. Not only that, you are keeping things loosely coupled. You may find later that you want a BST of BSTs, or of hash tables, or whatever. This way it will be much easier to swap out the list in each tree node for something else should you want to.
All that's left is putting them together. So, in your tree, when you inserted, all you were doing was incrementing a count variable. Now, instead of that (or in conjunction with that), you just need your one-line call to your list_insert function, and you have a tree of lists.
Originally Posted by oogabooga
