470,591 Members | 1,484 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 470,591 developers. It's quick & easy.

begging for a tree implementation

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

Apr 26 '06 #1
11 5258
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
Apr 26 '06 #2

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

Apr 27 '06 #3
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
Apr 27 '06 #4
Micah:
I'd like a full-featured tree


What features?

--
René Pijlman
Apr 27 '06 #5
Ant
Did you not read the first post?
All the nice methods would be appreciated (getLeaves, isLeaf, isRoot,
depthfirst, breadthfirst,...)


Apr 27 '06 #6
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!

Apr 27 '06 #7
> 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
Apr 27 '06 #8
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>

Apr 27 '06 #9
Ant
Damn! Missed the boat ;-)

Apr 27 '06 #10
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
Apr 27 '06 #11
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

Apr 27 '06 #12

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

3 posts views Thread by Steve Johnson | last post: by
12 posts views Thread by pillepop2003 | last post: by
5 posts views Thread by nandor.sieben | last post: by
4 posts views Thread by Tarique Jawed | last post: by
5 posts views Thread by Mike | last post: by
25 posts views Thread by prabhat143 | last post: by
3 posts views Thread by asianmuscle | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.