Ik wil een algemene boomstructuur bouwen waarvan het hoofdknooppunt ‘n’ kinderen bevat, en die kinderen kunnen andere kinderen bevatten…..
Antwoord 1, autoriteit 100%
Een boom in Python is vrij eenvoudig. Maak een klas met gegevens en een lijst met kinderen. Elk kind is een instantie van dezelfde klas. Dit is een algemene boom.
class Node(object):
def __init__(self, data):
self.data = data
self.children = []
def add_child(self, obj):
self.children.append(obj)
Interactie daarna:
>>> 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
>>>
Dit is een heel basaal skelet, niet geabstraheerd of zo. De daadwerkelijke code hangt af van uw specifieke behoeften – ik probeer alleen aan te tonen dat dit heel eenvoudig is in Python.
Antwoord 2, autoriteit 9%
Ik heb een Python [3] tree-implementatie op mijn site gepubliceerd: http:/ /www.quesucede.com/page/show/id/python_3_tree_implementation.
Ik hoop dat het van nut is,
Ok, hier is de 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)
Antwoord 3, Autoriteit 9%
AnyTree
Ik raad https://pypi.python.org/pypi/anytree
Voorbeeld
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'))
Functies
Anytree heeft ook een krachtige API met:
- Simple Tree Creation
- Simple Tree Modification
- pre-order tree iteration
- post-order tree iteration
- Relative en absolute knooppaden op
- lopen van het ene knooppunt naar een andere.
- Boomweergave (zie voorbeeld hierboven)
- Node Bevestig / Detach Hookups
Antwoord 4
node = { 'parent':0, 'left':0, 'right':0 }
import copy
root = copy.deepcopy(node)
root['parent'] = -1
left = copy
Gewoon om een andere gedachte aan implementatie weer te geven als u zich aan de “OOP” houdt
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']