不幸的是，您不提供我们的 Tree class，但是让我们假设它是这样的：

  class Tree（object） b $ b def __init __（self）：
 self.data = None 
 self.nextkey = 0 
 self.thedict = {} 
 

当插入新节点时，各种属性正在更新。现在，当你谈到保存在字典中的地址时，很明显，dict的值不是一个地址 - 而是一个Node对象（如果你定义一个特殊的方法 __ repr __ 在您的节点中，您可能能够以更清晰的方式看到;您所看到的是默认表示，用于所有类型不定义或继承的Python对象__repr __ ）。

所以，在两个不同的树之间交换随机子树只需要小心更新所有很多冗余的信息，重新保持（并且必须全部同步）。顺便说一下，如果这样的更新是Tree和/或Node的方法，那么这样更简单，因此可以用于各种编辑（插入，删除等）中的任何一种，而不是深入执行更新的函数作为随机互换的一部分 - 这是很好的OO实践。但是，这有点是一个侧面问题。

你也不会告诉我们分支属性的工作原理，我会假设它是一个字符串，左或对（如果没有父，即根节点，则为无）。

要删除一个子树，你需要更新：父节点，设置为无其适当的属性;子树的根，设置为无其父和分支属性;和树，从树的 thedict 属性中删除该条目。您还需要记住父母和分支是为了能够在该位置插入一些其他子树。因此...：

  def removeSubtreeFromTree（tree，keyindict）：
 subtreenode = tree.thedict.pop（keyindict ）
 parent，branch = subtreenode.parent，subtreenode.branch 
＃a sanity chech不能伤害... ;-) 
 assert getattr（parent，branch）是subtreenode 
 subtreenode.parent，subtreenode.branch =无，无
 setattr（父，分支，无）
返回subtreenode，父，分支
 

现在添加一个新的子树给一个给定的父和树中的分支更简单：

  def addNewSubtree（tree，subtreenode，parent，branch）：
＃sanity check R us 
 assert getattr（parent，branch）为无
 assert subtreenode.parent为无
 assert subtreenode.branch是无
 setattr（parent，branch，subtreenode）
 subtreenode.parent = parent 
 subtreenode.branch = branch 
 tree.thedict [tree.nextkey ] = subtreenode 
 tree.nextkey + = 1 
 

N ote你不能只是重复使用以前的键：可能会有一个冲突（假设键仅在一个给定的树中是唯一的...如果你使它们全局唯一，那么你可以重用它们）。 p>

最后，将这两个操作和更多的一起放在一起可以完成。如果你永远不需要交换一棵树的根源，那就更简单（没有特殊情况需要处理一个无父子的子树...），所以我暂时假定（如果你想要更一般性，你将需要代码***的特殊情况 - 理想的是重构事情就像以前建议的方法一样; - ）...：

  def randomNonrootSubtree （树）：
＃我们遇到麻烦，如果树只有一个根没有真正的SUB树;-) 
 assert len（tree.thedict）> 1 
 while True：
 thekey = random.choice（tree.thedict.keys（））
 subtree = tree.thedict [thekey] 
如果subtree.parent：返回thekey 
 

最后...：

  def theSwapper（t1，t2）：
 k1 = randomNonrootSubtree（t1）
 k2 = randomNonrootSubtree（t2）
 st1，p1，b1 = removeSubtreeFromTree ，k1）
 st2，p2，b2 = removeSubtreeFromTree（t2，k2）
 addNewSubtree（t1，st2，p1，b1）
 addNewSubtree（t2，st1，p2，b2）
 

I'm a nooby. I'd like to acknowledge Allen Downey, Jeffrey Elkner and Chris Meyers and 'How to think like a computer scientist' for what I know.

I'm building a genetics inspired program to generate equations that match some provided problem.

The node class looks like this:

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)

I have a Tree class that contains an attribute: self.data which is a linked series of nodes forming a tree which I can traverse to produce an equation.

To perform crossover, I'd like to be able to swap subtrees chosen at random from two instances of Tree.

As self.data is being constructed, it builds a dictionary with a sequential key holding each node as a value. One such record looks like this:

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

I thought I'd be clever and simply choose a node each from two tree instances and exchange their respective parents node.left or node.right values. Each node records if it is a left or right in its node.branch attribute.

I don't know how to reference self.data(subnode) to change it.

And both tree instances would have to have access to each other's nodes by the address saved in the dictionary.

I fear I shall have to copy and replace each subtree.

Any comments would be appreciated.

Thanks,

Peter Stewart

Nanaimo, Canada

Unfortunately you don't provide us with the Tree class, but let's assume it's something like:

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

with the various attributes being updated accurately when new nodes are inserted. Now, while you talk about "the address saved in the dictionary", it's clear that the dict's value is NOT "an address" -- rather, it's a Node object (if you define a special method __repr__ in your node you may be able to see that in a clearer way; what you're seeing is the default representation, used for all Python objects whose type don't define or inherit __repr__).

So, swapping random subtree between two different trees only requires care in updating all of the many redundant pieces of information that you're keeping (and that must ALL be in sync). By the way, it would be simpler if such updates were methods of Tree and/or Node and so usable for any of various kinds of "edit" (insertion, removal, etc), rather than buried deep in a function that performs the updates as part of a random swap -- that's good OO practice. But, that's somewhat of a side issue.

You also don't tell us exactly how the branch attribute works, I'll assume it's a string, 'left' or 'right' as appropriate (or None if there's no parent, i.e., a root node).

To remove a subtree, you need to update: the parent node, setting to None its appropriate attribute; the root of the subtree, setting to None its parent and branch attributes; AND the Tree, removing that entry from the Tree's thedict attribute. You will also need to remember what the parent and branch were in order to be able to insert some other subtree at that spot. Therefore...:

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

Now to ADD a new subtree to a given parent and branch in a Tree is simpler:

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

Note you can't just reuse the previous keys: there might be a "conflict" (assuming keys are unique only within a single given Tree... if you made them globally unique instead, then you could indeed reuse them).

Finally, putting these two operations and a little more together can be done. If you never need to "swap" a tree's very root, it's simpler (no special case needed to deal with a parentless subtree...) so I'm temporarily going to assume that (if you want more generality you WILL have to code the finicky special cases -- ideally after refactoring things to be methods as I previously suggested;-)...:

   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

and at last...:

   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)