CODEWITHSUNDEEP
pythontree
Tim
Tim

Reputation: 99556

Implement a tree where children and parents can refer to each other

From http://cbio.ufs.ac.za/live_docs/nbn_tut/trees.html

Let's create a python class to represent a tree. We need some way to store data in a node, and some way to indicate any child nodes, or subtrees.

class node(object):
    def __init__(self, value, children = []):
        self.value = value
        self.children = children

Whoa! That seems way too easy... but believe it or not, it does the job. Let's use our new class to store our family tree...

tree = node("grandmother", [
    node("daughter", [
        node("granddaughter"),
        node("grandson")]),
    node("son", [
        node("granddaughter"),
        node("grandson")])
    ]);

I would like to be able to get both the children and parent of each node instance, so I think I would need to define both its parent and its children

class node(object):
    def __init__(self, value, children = [], parent = []):
        self.value = value
        self.children = children
        self.parent = parent

But the problem is that there will be a copy of each node inside each of its children and parent. If I change its value, I will have to change all the values in its copies. In C++, there is no such a problem , because we can refer to the children and parent of a node by storing the pointers to its children and parent only in it. I wonder how such a tree can be implemented in Python? Thanks.

Upvotes: 3

Views: 8422

Answers (2)

Anton Savin
Anton Savin

Reputation: 41331

You can assign parents of children in the node constructor:

class node(object):
    def __init__(self, value, children = None):
        self.value = value
        self.children = children or []
        self.parent = None
        for child in self.children:
            child.parent = self

Upvotes: 9

Sebastian
Sebastian

Reputation: 11

class node(object): 
  def __init__(self, value, children = []): 
    self.value = value 
    self.children = children

tree = [node("grandmother", [ node("daughter", [ node("granddaughter"), node("grandson")]), node("son", [ node("granddaughter"), node("grandson")]) ])];

def familyValues(targetName, siblings = []):
  family = []
  for sibling in siblings:
    if sibling.value == targetName:
      family.append(sibling)
      family = family + sibling.children
      break
    else:
      children = familyValues(targetName, sibling.children)
      if len(children) > 0:
        children.append(sibling)
        family = children

  return family

myFamily = familyValues('daughter', tree)
for sibling in myFamily:
  print(sibling.value)

no copies of objects in python unless you clone them explicitly

Upvotes: 1

Related Questions