3

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.

Tim
  • 1
  • 141
  • 372
  • 590

2 Answers2

8

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
Anton Savin
  • 40,838
  • 8
  • 54
  • 90
  • Thanks. Python doesn't have pointers or references. So how can we achieve the same in general? – Tim Aug 21 '14 at 23:25
  • 2
    @Tim. Every variable in Python is a reference to an object. – John La Rooy Aug 21 '14 at 23:30
  • @Tim See [this question](http://stackoverflow.com/questions/986006/how-do-i-pass-a-variable-by-reference) – dano Aug 21 '14 at 23:36
  • OK, I like this answer better than mine, so I removed my answer. – nicolas Aug 21 '14 at 23:40
  • Using `children=[]` in the constructor here is going to mean any nodes that are created without children are going to share children if they are added later. – Holloway Apr 17 '16 at 17:27
1
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

Sebastian
  • 11
  • 3