实现一个子节点和父节点可以相互引用的树

Question

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

我们来创建一个Python类，用来表示一棵树。我们需要一种方法来在节点中存储数据，还有一种方法来指示任何子节点或子树。

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")])
    ]);

我希望能够获取每个node实例的孩子和父母，所以我想我需要同时定义它的父节点和孩子节点。

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

但问题是，每个节点在它的每个孩子和父母中都会有一个副本。如果我改变了它的值，我就得把所有副本中的值都改了。在C++中就没有这个问题，因为我们可以通过仅在节点中存储指向它的孩子和父母的指针来引用它们。我想知道在Python中如何实现这样的树？谢谢。

Answer 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)

在Python中，除非你明确地复制对象，否则不会有对象的副本。

Answer 2

你可以在节点构造函数里给孩子节点指定父节点：

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