Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Binary Trees in Python

277 views
Skip to first unread message

[diegueus9] Diego Andrés Sanabria

unread,
Aug 20, 2005, 3:09:03 PM8/20/05
to pytho...@python.org
Hello!!!

I want know if python have binary trees and more?

Roy Smith

unread,
Aug 20, 2005, 3:19:55 PM8/20/05
to
In article <mailman.3314.1124564...@python.org>,

[diegueus9] Diego Andrés Sanabria <zes...@gmail.com> wrote:

> Hello!!!
>
> I want know if python have binary trees and more?

Python does not come with a tree data structure. The basic data structures
in Python are lists, tuples, and dicts (hash tables).

People who are used to C++'s STL often feel short-changed because there's
not 47 other flavors of container, but it turns out that the three Python
gives you are pretty useful. Many people never find a need to look beyond
them.

If you do need to go beyond them, it's easy enough to build your own.
Here's one example of a binary ordered tree that you might find useful:

http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/286239

Ramza Brown

unread,
Aug 20, 2005, 3:27:16 PM8/20/05
to
[diegueus9] Diego Andrés Sanabria wrote:
> Hello!!!
>
> I want know if python have binary trees and more?
Yea, binary trees are more data structures as opposed to libraries:

Here is one approach ( remove the 'java.lang' stuff)

http://www.newspiritcompany.com/BinaryTreePyNew.html

--
Ramza from Atlanta
http://www.newspiritcompany.com

Steve M

unread,
Aug 20, 2005, 3:48:26 PM8/20/05
to

[diegueus9] Diego Andrés Sanabria <zes...@gmail.com> wrote:
> Hello!!!
>
> I want know if python have binary trees and more?

You might be interested that ZODB comes with some B-tree
implementations. They can be used alone or you can persist them in the
ZODB quite easily.

http://www.zope.org/Wikis/ZODB/FrontPage

Jorgen Grahn

unread,
Aug 21, 2005, 4:38:55 AM8/21/05
to
On Sat, 20 Aug 2005 15:19:55 -0400, Roy Smith <r...@panix.com> wrote:
> In article <mailman.3314.1124564...@python.org>,
> [diegueus9] Diego Andrés Sanabria <zes...@gmail.com> wrote:
>
>> Hello!!!
>>
>> I want know if python have binary trees and more?
>
> Python does not come with a tree data structure. The basic data structures
> in Python are lists, tuples, and dicts (hash tables).
>
> People who are used to C++'s STL often feel short-changed because there's
> not 47 other flavors of container, but it turns out that the three Python
> gives you are pretty useful. Many people never find a need to look beyond
> them.

Uh, the STL has seven flavors:
- vector
- deque
- list
- set
- map
- multimap
- multiset
so that's not too bad for a static language. Each of them
is vital for some purpose, but vector and map are by far the
most commonly used.

Neither C++ nor Python has tree structures in their standard libraries. I
assume that's because there is no single interface that is proven to suit
everybody's needs.

/Jorgen

--
// Jorgen Grahn <jgrahn@ Ph'nglui mglw'nafh Cthulhu
\X/ algonet.se> R'lyeh wgah'nagl fhtagn!

François Pinard

unread,
Aug 21, 2005, 8:52:10 AM8/21/05
to Jorgen Grahn, pytho...@python.org
[Jorgen Grahn]

> Neither C++ nor Python has tree structures in their standard
> libraries. I assume that's because there is no single interface that
> is proven to suit everybody's needs.

It is already easy writing "tree constants" using recursive tuples or
lists. To process simple trees in Python, I usually subclass some
Node type from list, and write the traversal methods that suit the
application. The sub-classing already allow for indexing sub-nodes by
"self[index]", and iterating over all by "for subnode in self:", etc.
In my experience, it all goes pretty easily, while staying simple.

However, things related to balancing, finding paths between nodes, or
searching for patterns, etc. may require more work. There are surely
a flurry of tree algorithms out there. What are the actual needs you
have, and would want to see covered by a library?

--
François Pinard http://pinard.progiciels-bpi.ca

Jeff Schwab

unread,
Aug 21, 2005, 4:20:41 PM8/21/05
to
Jorgen Grahn wrote:
> On Sat, 20 Aug 2005 15:19:55 -0400, Roy Smith <r...@panix.com> wrote:
>
>>In article <mailman.3314.1124564...@python.org>,
>> [diegueus9] Diego Andrés Sanabria <zes...@gmail.com> wrote:
>>
>>
>>>Hello!!!
>>>
>>>I want know if python have binary trees and more?
>>
>>Python does not come with a tree data structure. The basic data structures
>>in Python are lists, tuples, and dicts (hash tables).
>>
>>People who are used to C++'s STL often feel short-changed because there's
>>not 47 other flavors of container, but it turns out that the three Python
>>gives you are pretty useful. Many people never find a need to look beyond
>>them.
>
>
> Uh, the STL has seven flavors:
> - vector
> - deque
> - list
> - set
> - map
> - multimap
> - multiset

There are others, e.g. std::valarray. There are also adapters that use
the above templates to implement other structures, adding or limiting
functionality as appropriate; e.g., std::heap and std::stack.

> so that's not too bad for a static language. Each of them
> is vital for some purpose, but vector and map are by far the
> most commonly used.
>
> Neither C++ nor Python has tree structures in their standard libraries. I
> assume that's because there is no single interface that is proven to suit
> everybody's needs.

Hmmm... I guess I never noticed the lack. C++ has structures or
language features that represent most of the common things trees are
typically used to implement. Of course, a "tree" can be represented in
so many ways, it's more of a design pattern than a data structure. :)

Chris Smith

unread,
Aug 24, 2005, 3:33:38 AM8/24/05
to
>>>>> "[diegueus9]" == [diegueus9] Diego Andrés Sanabria <diegueus9> writes:

[diegueus9]> Hello!!! I want know if python have binary trees and
[diegueus9]> more?

The latest boost, 1.33, says it has a python wrapper for the boost
graph library.
Boost explicitely states that it's experimental, but my emerge was
successful.
See http://boost.org
-Chris

Jorgen Grahn

unread,
Sep 4, 2005, 1:26:10 PM9/4/05
to

I have no needs, actually ... but yes, the things you mention (balancing,
traversal ...) were the ones I was thinking about.

0 new messages