By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
445,928 Members | 1,842 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 445,928 IT Pros & Developers. It's quick & easy.

Binary Trees in Python

P: n/a
Hello!!!

I want know if python have binary trees and more?
Aug 20 '05 #1
Share this Question
Share on Google+
8 Replies


P: n/a
In article <ma***************************************@python. org>,
[diegueus9] Diego Andrés Sanabria <ze****@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/Coo.../Recipe/286239
Aug 20 '05 #2

P: n/a
[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
Aug 20 '05 #3

P: n/a

[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

Aug 20 '05 #4

P: n/a
On Sat, 20 Aug 2005 15:19:55 -0400, Roy Smith <ro*@panix.com> wrote:
In article <ma***************************************@python. org>,
[diegueus9] Diego Andrés Sanabria <ze****@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!
Aug 21 '05 #5

P: n/a
[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
Aug 21 '05 #6

P: n/a
Jorgen Grahn wrote:
On Sat, 20 Aug 2005 15:19:55 -0400, Roy Smith <ro*@panix.com> wrote:
In article <ma***************************************@python. org>,
[diegueus9] Diego Andrés Sanabria <ze****@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. :)
Aug 21 '05 #7

P: n/a
>>>>> "[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
Aug 24 '05 #8

P: n/a
On Sun, 21 Aug 2005 08:52:10 -0400, François Pinard <pi****@iro.umontreal.ca> wrote:
[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?


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

/Jorgen

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

This discussion thread is closed

Replies have been disabled for this discussion.