A general tree implementation? [closed]
Want to improve this question? Update the question so it focuses on one problem only by editing this post.
Closed 5 years ago.
开发者_如何学JAVA Improve this questionI want to build a general tree whose root node contains 'n' children, and those children may contain other children.....
A tree in Python is quite simple. Make a class that has data and a list of children. Each child is an instance of the same class. This is a general n-nary tree.
class Node(object):
def __init__(self, data):
self.data = data
self.children = []
def add_child(self, obj):
self.children.append(obj)
Then interact:
>>> n = Node(5)
>>> p = Node(6)
>>> q = Node(7)
>>> n.add_child(p)
>>> n.add_child(q)
>>> n.children
[<__main__.Node object at 0x02877FF0>, <__main__.Node object at 0x02877F90>]
>>> for c in n.children:
... print c.data
...
6
7
>>>
This is a very basic skeleton, not abstracted or anything. The actual code will depend on your specific needs - I'm just trying to show that this is very simple in Python.
I've published a Python [3] tree implementation on my site: http://www.quesucede.com/page/show/id/python_3_tree_implementation.
Hope it is of use,
Ok, here's the code:
import uuid
def sanitize_id(id):
return id.strip().replace(" ", "")
(_ADD, _DELETE, _INSERT) = range(3)
(_ROOT, _DEPTH, _WIDTH) = range(3)
class Node:
def __init__(self, name, identifier=None, expanded=True):
self.__identifier = (str(uuid.uuid1()) if identifier is None else
sanitize_id(str(identifier)))
self.name = name
self.expanded = expanded
self.__bpointer = None
self.__fpointer = []
@property
def identifier(self):
return self.__identifier
@property
def bpointer(self):
return self.__bpointer
@bpointer.setter
def bpointer(self, value):
if value is not None:
self.__bpointer = sanitize_id(value)
@property
def fpointer(self):
return self.__fpointer
def update_fpointer(self, identifier, mode=_ADD):
if mode is _ADD:
self.__fpointer.append(sanitize_id(identifier))
elif mode is _DELETE:
self.__fpointer.remove(sanitize_id(identifier))
elif mode is _INSERT:
self.__fpointer = [sanitize_id(identifier)]
class Tree:
def __init__(self):
self.nodes = []
def get_index(self, position):
for index, node in enumerate(self.nodes):
if node.identifier == position:
break
return index
def create_node(self, name, identifier=None, parent=None):
node = Node(name, identifier)
self.nodes.append(node)
self.__update_fpointer(parent, node.identifier, _ADD)
node.bpointer = parent
return node
def show(self, position, level=_ROOT):
queue = self[position].fpointer
if level == _ROOT:
print("{0} [{1}]".format(self[position].name, self[position].identifier))
else:
print("\t"*level, "{0} [{1}]".format(self[position].name, self[position].identifier))
if self[position].expanded:
level += 1
for element in queue:
self.show(element, level) # recursive call
def expand_tree(self, position, mode=_DEPTH):
# Python generator. Loosly based on an algorithm from 'Essential LISP' by
# John R. Anderson, Albert T. Corbett, and Brian J. Reiser, page 239-241
yield position
queue = self[position].fpointer
while queue:
yield queue[0]
expansion = self[queue[0]].fpointer
if mode is _DEPTH:
queue = expansion + queue[1:] # depth-first
elif mode is _WIDTH:
queue = queue[1:] + expansion # width-first
def is_branch(self, position):
return self[position].fpointer
def __update_fpointer(self, position, identifier, mode):
if position is None:
return
else:
self[position].update_fpointer(identifier, mode)
def __update_bpointer(self, position, identifier):
self[position].bpointer = identifier
def __getitem__(self, key):
return self.nodes[self.get_index(key)]
def __setitem__(self, key, item):
self.nodes[self.get_index(key)] = item
def __len__(self):
return len(self.nodes)
def __contains__(self, identifier):
return [node.identifier for node in self.nodes if node.identifier is identifier]
if __name__ == "__main__":
tree = Tree()
tree.create_node("Harry", "harry") # root node
tree.create_node("Jane", "jane", parent = "harry")
tree.create_node("Bill", "bill", parent = "harry")
tree.create_node("Joe", "joe", parent = "jane")
tree.create_node("Diane", "diane", parent = "jane")
tree.create_node("George", "george", parent = "diane")
tree.create_node("Mary", "mary", parent = "diane")
tree.create_node("Jill", "jill", parent = "george")
tree.create_node("Carol", "carol", parent = "jill")
tree.create_node("Grace", "grace", parent = "bill")
tree.create_node("Mark", "mark", parent = "jane")
print("="*80)
tree.show("harry")
print("="*80)
for node in tree.expand_tree("harry", mode=_WIDTH):
print(node)
print("="*80)
anytree
I recommend https://pypi.python.org/pypi/anytree
Example
from anytree import Node, RenderTree
udo = Node("Udo")
marc = Node("Marc", parent=udo)
lian = Node("Lian", parent=marc)
dan = Node("Dan", parent=udo)
jet = Node("Jet", parent=dan)
jan = Node("Jan", parent=dan)
joe = Node("Joe", parent=dan)
print(udo)
Node('/Udo')
print(joe)
Node('/Udo/Dan/Joe')
for pre, fill, node in RenderTree(udo):
print("%s%s" % (pre, node.name))
Udo
├── Marc
│ └── Lian
└── Dan
├── Jet
├── Jan
└── Joe
print(dan.children)
(Node('/Udo/Dan/Jet'), Node('/Udo/Dan/Jan'), Node('/Udo/Dan/Joe'))
Features
anytree has also a powerful API with:
- simple tree creation
- simple tree modification
- pre-order tree iteration
- post-order tree iteration
- resolve relative and absolute node paths
- walking from one node to an other.
- tree rendering (see example above)
- node attach/detach hookups
node = { 'parent':0, 'left':0, 'right':0 }
import copy
root = copy.deepcopy(node)
root['parent'] = -1
left = copy
just to show another thought on implementation if you stick to the "OOP"
class Node:
def __init__(self,data):
self.data = data
self.child = {}
def append(self, title, child):
self.child[title] = child
CEO = Node( ('ceo', 1000) )
CTO = ('cto',100)
CFO = ('cfo', 10)
CEO.append('left child', CTO)
CEO.append('right child', CFO)
print CEO.data
print ' ', CEO.child['left child']
print ' ', CEO.child['right child']
精彩评论