Binary Trees in Python

  • Thread starter =?ISO-8859-1?Q?=5Bdiegueus9=5D_Diego_Andr=E9s_Sana
  • Start date
?

=?ISO-8859-1?Q?=5Bdiegueus9=5D_Diego_Andr=E9s_Sana

Hello!!!

I want know if python have binary trees and more?
 
R

Roy Smith

[diegueus9] Diego Andrés Sanabria said:
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
 
J

Jorgen Grahn

[diegueus9] Diego Andrés Sanabria said:
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
 
?

=?iso-8859-1?Q?Fran=E7ois?= Pinard

[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?
 
J

Jeff Schwab

Jorgen said:
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. :)
 
C

Chris Smith

"[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
 
J

Jorgen Grahn

[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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

bench: binary trees 10
Binary search trees (AVL trees) 34
No trees in the stdlib? 66
constructin trees in python 3
binary key in dictionary 2
Binary tree implementation 0
Trees 7
trees 3

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top