Python：操纵子树 [英] Python: manipulating sub trees

问题描述

我是一个笨蛋我想承认Allen Downey，Jeffrey Elkner和Chris Meyers
以及我所知道的如何像计算机科学家一样思考。

建立一个基因启发程序来生成符合一些提供的问题的方程。

节点类看起来像这样：

  class Node（object）：
'''
'''
 def __init __（self，cargo，left = None，right = ：
 self.cargo = cargo 
 self.left = left 
 self.right = right 
 self.parent =无
 self.branch =无
 self.seq = 0 
 
 def __str __（self）：
 return str（self.cargo）
 
 def copy（self）：
 return copy .deepcopy（self）
  

我有一个树 class，它包含一个属性： self.data 它是一个链接的一系列节点，形成一个可以遍历的树，以产生一个方程。

要执行交叉，我希望能够从两个实例 Tree 中随机选择一个子树。

正在构建 self.data ，它使用一个连续的键来构建一个字典，并将每个节点保存为一个值。一个这样的记录看起来像这样：

  3：< __ main __。0x0167B6B0>上的节点对象} 
  

我以为我会聪明，只需从两个树实例中选择一个节点，并交换他们各自的父母 node.left 或 node.right 值。每个节点在其 node.branch 属性中记录是左或右。

我不知道如何引用 self.data（subnode）来更改它。

两个树实例都必须有访问权限通过保存在字典中的地址到彼此的节点。

我怕我必须复制和替换每个子树。

任何意见不胜感激。

谢谢，

Peter Stewart

加拿大纳奈莫

解决方案

不幸的是，您不提供我们的 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)

这篇关于Python：操纵子树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！