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

[marc nicole]

great comments! but could you help debug the code I provided?

Le lun. 29 janv. 2024 à 04:09, ThreeBlindQuarks <threesomequarks at proton.me>
a écrit :

> 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
>