begging for a tree implementation

[Micah]

I'm looking for a simple tree implementation: 0-n children, 1 root.
All the nice methods would be appreciated (getLeaves, isLeaf, isRoot,
depthfirst, breadthfirst,...) That's really all I need. I could code
one up, but it would take time to debug, and i'm really short on time
right now.

Thanks!
Micah

[Sybren Stuvel]

Micah enlightened us with:

I'm looking for a simple tree implementation: 0-n children, 1 root.
All the nice methods would be appreciated (getLeaves, isLeaf,
isRoot, depthfirst, breadthfirst,...) That's really all I need. I
could code one up, but it would take time to debug, and i'm really
short on time right now.

What kind of tree do you want? B+-tree? Black/Red tree? Binary search
tree?

Sybren
--
The problem with the world is stupidity. Not saying there should be a
capital punishment for stupidity, but why don't we just take the
safety labels off of everything and let the problem solve itself?
Frank Zappa

[Micah]

Sybren Stuvel wrote:

Micah enlightened us with:

I'm looking for a simple tree implementation: 0-n children, 1 root.
All the nice methods would be appreciated (getLeaves, isLeaf,
isRoot, depthfirst, breadthfirst,...) That's really all I need. I
could code one up, but it would take time to debug, and i'm really
short on time right now.

What kind of tree do you want? B+-tree? Black/Red tree? Binary search
tree?

Sybren
--
The problem with the world is stupidity. Not saying there should be a
capital punishment for stupidity, but why don't we just take the
safety labels off of everything and let the problem solve itself?
Frank Zappa

I'm looking for a simple abstract-data-type tree. I would have thought
there would be a built-in type, but I can't find one. I just need to
be able to start from a root node and attach children from there. I
could jury-rig one using a dict or some tuples, but I'd like a
full-featured tree if someone has one implemented.

Thanks for the reply!
Micah

[Sybren Stuvel]

Micah enlightened us with:

I'm looking for a simple abstract-data-type tree. I would have thought
there would be a built-in type, but I can't find one. I just need to
be able to start from a root node and attach children from there. I
could jury-rig one using a dict or some tuples, but I'd like a
full-featured tree if someone has one implemented.

If you keep things that vague: use a list. See the first element as
the root node. Every node has only one child.

Sybren
--
The problem with the world is stupidity. Not saying there should be a
capital punishment for stupidity, but why don't we just take the
safety labels off of everything and let the problem solve itself?
Frank Zappa

[Rene Pijlman]

Micah:

I'd like a full-featured tree

What features?

--
René Pijlman

[Ant]

Did you not read the first post?

All the nice methods would be appreciated (getLeaves, isLeaf, isRoot,
depthfirst, breadthfirst,...)

[Ant]

I was looking for a tree implementation a while back, but got no real
pointers. Seems that there are no tree data model modules out there -
which surprises me, since it is such a fundamental data structure.

I ended up using a very basic tree data class - I didn't need all of
the methods you mentioned. Here it is in case that helps at all:

class Node (object):
def __init__(self, data, parent=None):
self.data = data
self.parent = parent
self.children = []

def add_child(self, child):
self.children.append(child)
child.parent = self

Some of those methods you mentioned would be trivial to implement:

def is_root(self):
return not self.parent
def is_leaf(self):
return not self.children

It may also be more pythonic to have 'walk' methods for traversing
trees.

I may start a tree data structure project - it's something I've been
thinking about for a while, and now it's clear that it's not just me
who uses trees as data structures!

[Diez B. Roggisch]

> I may start a tree data structure project - it's something I've been

thinking about for a while, and now it's clear that it's not just me
who uses trees as data structures!

Oh, people do use them. It's just to easy to cough one up when you need it -
either as nested tuples, lists, dicts or a simple class like yours - which
I needed yesterday and wrote in 2 minutes. And that is tailored to the
needs at hand and not some abstraction that might prevent you from e.g.
using methods like __iter__ or the like with your own semantics.

This is not to discourage you - just don't expect people to greet you as the
next messiah who finally brought one of CS most fundamental data structures
to Python... :)

Diez

[Fredrik Lundh]

Diez B. Roggisch wrote:

This is not to discourage you - just don't expect people to greet you as the
next messiah who finally brought one of CS most fundamental data structures
to Python... :)

xml.etree was added to Python 2.5 before christmas :-)

</F>

[Ant]

Damn! Missed the boat ;-)

[Diez B. Roggisch]

Fredrik Lundh wrote:

Diez B. Roggisch wrote:

This is not to discourage you - just don't expect people to greet you as
the next messiah who finally brought one of CS most fundamental data
structures to Python... :)

xml.etree was added to Python 2.5 before christmas :-)

Can't wait until etree grows some tree optimization algorithms like AVL or
red-black. Those degenerated XML-documents of mine always annoyed me.. :)

Diez

[DogWalker]

Micah wrote:

I'm looking for a simple tree implementation: 0-n children, 1 root.
All the nice methods would be appreciated (getLeaves, isLeaf, isRoot,
depthfirst, breadthfirst,...) That's really all I need. I could code
one up, but it would take time to debug, and i'm really short on time
right now.

Thanks!
Micah

http://aspn.activestate.com/ASPN/Coo.../Recipe/136529