Jump to content
  • Advertisement
Sign in to follow this  

Building a binary search tree with a special condition at leaves.

This topic is 2223 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am having trouble with finding a way to go about building a binary search tree where all the leaves contain letters and are on the same level/height of the tree or one level up if there isn't enough letters to finish a level. But the inner nodes contain no letters, only int labels to hold the binary search tree structure. For example:

45 level 3 - root node
25 65 level 2 - two nodes
15 35 55 75 level 1 - four nodes
10 20 30 40 50 60 70 80 level 0 - eight nodes

EDIT- sorry, the tree spacing structure didn't stay after hitting post.

So the values 10,20,30,40,50,60,70,80 would contain something like a,b,c,d,e,f,g,h respectively.
(every node has left,right,parent pointers and a int label and string for holding the char(this string is only used for the leaf nodes))

mine is going to be five levels but this is just an example of one. the inner nodes' labels are just the average of its children's labels.
Currently, I am trying to build the tree in a left to right iterative way(pretty much a double linked list going across every node in a level) but am having trouble thinking of a way to do the next few levels up after I have the base level. The way i'm doing it, all the children end up being connected to eachother, so the left and right points don't end up pointing to that node's children but to its siblings. I am eventually going to have to do rotations on this tree so I'm assuming I need the children pointing to the parent and the parent pointing to the children, not just one direction. I was wondering if anyone knows of a recursive way to do this or a more efficient way, like building the tree child to parent instead of child to child. Going at the rate I am right now, my code is going to be a huge mess.


right now my code for level 0 generates:
NULL<--10--><--20--><--30..><--40--><--50--><--60--><--70--><--80-->NULL
I haven't made any use of the parent pointers for each node yet, so it's pretty much just a double linked list.
(--><-- means they are pointing to eachother)

Share this post


Link to post
Share on other sites
Advertisement
Why does it need to meet those criteria? What is your actual problem you are trying to solve?

You may be able to get the needed functionality out of a built-in data structure that gives tree performance (such as set or map), or you may be able to use the various heap functions to manage your own tree. The c++ heap functions are easily customized to handle a wide range of tree-based needs.

Share this post


Link to post
Share on other sites
It is for a class project, so I can't deviate from the binary search tree. We are learning how to rotate portions of a tree but I am having trouble getting the tree built. Once my tree is built i'm going to have to perform rotations on it and use a huffman tree style of method to keep track of the letters at the leaves of the tree. This will be used to encode messages to a binary looking message of 1's and 0's and also decode messages in that format.


EDIT - nevermind, I believe i have a decent method now. I am creating an array that holds an entire row's pointers at a time instead of a linked list, that way I have access to them all at any time.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!