# Untitled

unknown

python

2 years ago

3.5 kB

3

Indexable

Never

^{}

# Enter your code here. Read input from STDIN. Print output to STDOUT # define nodes that can point to other nodes that will build our tree class Node: def __init__(self, value, parent=None, children = None): self.data = value self.parent = parent self.children = [] # if the node already contains children, assign if children is not None: for child in children: self.add_child(child) # recurse thru the children of this node # It would make more sense to instead have another class/developer implement their own node traversals def iterate_children(self): yield self for child in self.children: for schild in child.iterate_children(): yield schild # supporting the removals of itself from the tree and reassigning its childrens parent to its parent # returning self and whoever is using this can deallocate it instead def remove_self_keep_children(self): s_parent_node = self.parent for child in self.children: child.parent = s_parent_node self.parent.children.remove(self) self.parent = None return self class Tree: def __init__(self, root_value): self.root = Node(root_value) # Since ther requirement only needs to list all nodes on the tree, you could just iterate_children on a specific node, and this to get all nodes from the tree def iterate_children(self): return self.root.iterate_children() # TODO add traversals, so we can prevent cycles during insertion def get_all_children(self, node): return node.iterate_children() # TODO satisfy being able to insert nodes put still prevent cycles def add_node(self, new_node, parent): if isinstance(new_node, Node): if not new_node.children: # if inserted node has no children, then no cycle is possible new_node.parent = Node parent.children.append(new_node) else: # but if node has children, then need to search children cannot point back to the tree and create a cycle print("traversing new node's children to prevent cycles") for nc in new_node.children: st = nc.iterate_children() if new_node not in st: # no cycle! new_node.parent = Node parent.children.append(new_node) def remove_node(self, node): if (node == self.root): raise Exception("Cannot remove the root node") else: node.parent.remove_child(node) # This implementation allows you to have your node have a child that is a node that exists elswhere in the tree # Which would be an issue if trying to recurse through that node's children which has nodes that eventually point to that node # def add_child(new_node, parent): # # to prevent cycling, check if the child to be added has already been appended # if parent is not None and new_node is not None and parent not in new_node.children: # # currently this only prevents cycles of new_node, and childs child # if parent not in new_node.iterate_children(): # new_node.children.append(parent) # parent.parent = new_node # point the added child's parents to this node