Python：操作子树

Question

我还是个新手。我要感谢Allen Downey、Jeffrey Elkner和Chris Meyers，还有《如何像计算机科学家一样思考》这本书，让我学到了这些知识。

我正在开发一个受遗传学启发的程序，目的是生成一些与给定问题相匹配的方程。

我的节点类看起来是这样的：

class Node(object):
    '''
    '''
    def __init__(self, cargo, left=None, right=None):
        self.cargo = cargo
        self.left  = left
        self.right = right
        self.parent = None
        self.branch = None
        self.seq = 0

    def __str__(self):
        return str(self.cargo)

    def copy(self):
        return copy.deepcopy(self)

我有一个Tree类，它里面有一个属性：self.data，这个属性是一个链接的节点系列，形成了一棵树，我可以遍历这棵树来生成方程。

为了进行交叉操作，我想从两个Tree实例中随机选择子树并进行交换。

在构建self.data的时候，它会建立一个字典，字典的键是顺序的，每个节点作为值存储。这样的记录看起来是这样的：

    3: <__main__.Node object at 0x0167B6B0>} 

我想得很聪明，简单地从两个树实例中各选择一个节点，然后交换它们各自父节点的node.left或node.right值。每个节点会在它的node.branch属性中记录自己是左节点还是右节点。

但我不知道怎么引用self.data(subnode)来进行更改。

而且两个树实例必须通过字典中保存的地址互相访问对方的节点。

我担心我可能需要复制并替换每个子树。

任何建议都非常感谢。

谢谢，

彼得·斯图尔特

加拿大纳奈莫

Answer 1

如果我理解得没错的话，你是在寻找类似这样的东西...

（我还没有测试过这个。）

def swap_nodes(dict_1, key_1, dict_2, key_2):
    node_1 = dict_1[key_1]
    node_2 = dict_2[key_2]

    # Update dicts and seq fields for the two nodes...
    dict_1[key_1] = node_2
    node_2.seq = key_1
    dict_2[key_2] = node_1
    node_1.seq = key_2

    # Update the parents...
    if node_1.branch == "left":
        node_1.parent.left = node_2
    else:
        node_1.parent.right = node_2

    if node_2.branch == "left":
        node_2.parent.left = node_1
    else:
        node_2.parent.right = node_1

    # Now update the branch and parent fields of the nodes...
    node_1.branch, node_2.branch = node_2.branch, node_1.branch
    node_1.parent, node_2.parent = node_2.parent, node_1.parent

Answer 2

很遗憾，你没有提供 Tree 类的具体内容，但我们可以假设它大概是这样的：

class Tree(object):
  def __init__(self):
    self.data = None
    self.nextkey = 0
    self.thedict = {}

当插入新节点时，各种属性会被准确更新。现在，虽然你提到“字典中保存的地址”，但很明显，字典的值并不是“一个地址”——而是一个节点对象（如果你在节点中定义一个特殊的方法 __repr__，你可能会更清楚地看到这一点；你现在看到的是默认的表示方式，适用于所有没有定义或继承 __repr__ 的 Python 对象）。

所以，在两棵不同的树之间交换随机子树，只需要小心更新你所保存的许多冗余信息（这些信息必须保持同步）。顺便说一下，如果这些更新是树和/或节点的方法，这样就可以用于各种“编辑”（插入、删除等），而不是埋在一个执行随机交换的函数中，那会更简单——这也是良好的面向对象编程实践。不过，这算是一个次要问题。

你也没有告诉我们 branch 属性具体是怎么工作的，我假设它是一个字符串，可能是 'left' 或 'right'（如果没有父节点，即根节点，则为 None）。

要删除一个子树，你需要更新：父节点，将其相应的属性设置为 None；子树的根节点，将其父节点和分支属性都设置为 None；还有树本身，从树的 thedict 属性中移除该条目。你还需要记住之前的父节点和分支，以便能够在那个位置插入其他子树。因此……：

def removeSubtreeFromTree(tree, keyindict):
  subtreenode = tree.thedict.pop(keyindict)
  parent, branch = subtreenode.parent, subtreenode.branch
  # a sanity chech can't hurt...;-)
  assert getattr(parent, branch) is subtreenode
  subtreenode.parent, subtreenode.branch = None, None
  setattr(parent, branch, None)
  return subtreenode, parent, branch

现在要在树中给定的父节点和分支添加一个新的子树就简单多了：

def addNewSubtree(tree, subtreenode, parent, branch):
  # sanity checks R us
  assert getattr(parent, branch) is None
  assert subtreenode.parent is None
  assert subtreenode.branch is None
  setattr(parent, branch, subtreenode)
  subtreenode.parent = parent
  subtreenode.branch = branch
  tree.thedict[tree.nextkey] = subtreenode
  tree.nextkey += 1

注意，你不能直接重用之前的键：可能会出现“冲突”（假设键在单棵树中是唯一的……如果你让它们在全局范围内唯一，那你确实可以重用它们）。

最后，把这两个操作和更多内容结合起来是可行的。如果你从来不需要“交换”树的根节点，那就简单多了（不需要处理没有父节点的子树的特殊情况……）所以我暂时假设这一点（如果你想要更通用的功能，你确实需要编写一些麻烦的特殊情况——理想情况下在我之前建议的基础上将其重构为方法；-）……：

   def randomNonrootSubtree(tree):
     # we're in trouble if the tree ONLY has a root w/no really SUB trees;-)
     assert len(tree.thedict) > 1
     while True:
       thekey = random.choice(tree.thedict.keys())
       subtree = tree.thedict[thekey]
       if subtree.parent: return thekey

最后……：

   def theSwapper(t1, t2):
     k1 = randomNonrootSubtree(t1)
     k2 = randomNonrootSubtree(t2)
     st1, p1, b1 = removeSubtreeFromTree(t1, k1)
     st2, p2, b2 = removeSubtreeFromTree(t2, k2)
     addNewSubtree(t1, st2, p1, b1)
     addNewSubtree(t2, st1, p2, b2)