[Tutor] How to create a binary tree hierarchy given a list of elements as its leaves

[ThreeBlindQuarks]

I too am not clear on exactly what is wanted and just want to say that you need to come up first with which of the many ways you can construct a binary tree of sorts in a way that makes the rest of what you want straightforward or at least doable.

Numpy does not come to mind as a way to do a binary tree. I am sure it can be used in some way to get a result but my first thoughts include using nested lists that contain no more than two items at each level. But that can have some issues if you also want to store labels in some way so I would suspect using a customized object, or some module that already supplies what you want, as easier.

If using objects, you might have an object that points to or contains two similar objects with a name like left/right and when one is not is use, puts in a stub like a null instead. You can have other contents to hold names, or how many time sit has been visited, maybe pointers back up the tree and so on and add the member functions needed to do additions or deletions or searches or whatever makes sense, and some may best be written in a sort of recursive way.

Of course, if your other functionality wants results in another format, such as a nested tuple implementation, you may want functions that take a root pointing to the binary tree parts and traverse them while building the tuple or list or vice versa. You need not use one fixed structure for every kind of calculation if they are inter-convertible. It depends on your needs, such as will you ever be asked to identify and return a sub-tree rather than a leaf?

If this is akin to homework, you may want to design your own version from scratch. If not, this is a very common thing often used and often traversed. You need to decide if it has to be very fast or just easier to construct and use and so on.

Note another of many possibilities could be using nested dictionaries with each containing a left and a right. It may make sense to experiment with which data structure you feel a bit more comfortable.

And, as Alan pointed out, binary trees tend to not be at all balanced if the data fed is is already in order. There are algorithms people use to take a bad tree and rebalance it better so it can be accessed and manipulated faster on average.





Sent with Proton Mail secure email.

On Sunday, January 28th, 2024 at 6:11 PM, marc nicole <mk1853387 at gmail.com> wrote:

> Here's the tree example I attached earlier which shows how to go from leaf
> nodes (0,1,2,3) to the root node (the range[0,3]) my problem (bug) in the
> code is that the generated intermediate intervals for the nodes don't fit
> each other because of the way I binary split the input array
> 
> C1[0,3]
> ├── B1[0,1]
> │ ├── A0(0)
> │ └── A1(1)
> └── B2[2,3]
> ├── A2(2)
> └── A3(3)
> 
> Le dim. 28 janv. 2024 à 20:12, Alan Gauld via Tutor tutor at python.org a
> 
> écrit :
> 
> > On 28/01/2024 18:16, marc nicole via Python-list wrote:
> > 
> > > So I am trying to build a binary tree hierarchy given numerical elements
> > > serving for its leaves (last level of the tree to build). From the
> > > leaves I
> > > want to randomly create a name for the higher level of the hierarchy and
> > > assign it to the children elements. For example: if the elements inputted
> > > are `0,1,2,3` then I would like to create firstly 4 elements (say by
> > > random
> > > giving them a label composed of a letter and a number) then for the
> > > second
> > > level (iteration) I assign each of 0,1 to a random name label (e.g. `b1`)
> > > and `2,3` to another label (`b2`) then for the third level I assign a
> > > parent label to each of `b1` and `b2` as `c1`.
> > > 
> > > An illustation of the example is the following tree:
> > > 
> > > [image: tree_exp.PNG]
> > 
> > Unfortunately the Python mail servers strip out binary
> > attachments so we can't see the example.
> > 
> > Which is a pity because I don't really understand your
> > explanation, particularly about the random labelling
> > of parents.
> > 
> > Also you are using an ordered set of inputs which is usually
> > a bad case for a binary tree - it turns into a linear list...
> > 
> > However, I notice you've included several other mailing
> > lists so maybe someone else will comprehend your intention.
> > 
> > Meanwhile, for a basic Python binary tree implementation
> > example you could try here:
> > 
> > https://www.askpython.com/python/examples/binary-tree-implementation
> > 
> > That may or may not help!
> > 
> > I'm actually surprised it's not already in the standard
> > library somewhere, but I couldn't find one.
> > 
> > --
> > Alan G
> > Author of the Learn to Program web site
> > http://www.alan-g.me.uk/
> > http://www.amazon.com/author/alan_gauld
> > Follow my photo-blog on Flickr at:
> > http://www.flickr.com/photos/alangauldphotos
> > 
> > _______________________________________________
> > Tutor maillist - Tutor at python.org
> > To unsubscribe or change subscription options:
> > https://mail.python.org/mailman/listinfo/tutor
> 
> _______________________________________________
> Tutor maillist - Tutor at python.org
> To unsubscribe or change subscription options:
> https://mail.python.org/mailman/listinfo/tutor