I'm creating a python class for a tree in which each node has a number of children given by "order" (but each child only has one node). I have a method, children(self,i), which returns the children of a node at index i. I need to implement parent(self, i) which will get the parent of a child at index i.
Here's what I have so far:
class Tree:
def __init__(self, order=2, l=[]):
self._tree = l
self._order = order
def children(self, i):
left = self._tree[(i+1)*self._order-1]
right = self._tree[(i+1)*self._order]
return [left, right]
def parent(self, i):
if i>len(self._tree):
return ValueError
elif i==0:
return None
else:
#get parent of node i
An example tree represented by order=2 and list [45, 2, 123, 1, 8, 40, 456] would look like this:
45
/ \
2 123
/ \ / \
1 8 40 456
I know that there's probably a way I can reverse the method I used for children(self, i) but I'm not sure how.
You would do the inverse operation:
else:
#get parent of node i
return self._tree[(i-1)//self._order]
Note that your implementation is only working for binary trees (you return two children, not n). Correct it like this:
def children(self, i):
return self._tree[(i*self._order+1):((i+1)*self._order+1)]