python - 随机组合两个二叉树

Question

我正在做一个关于遗传算法的项目，基因是二叉树。

现在我需要将它们重新组合，方法是在两棵树上随机选择一个节点，然后替换它们。

例如:

树1和2，从1中选择节点C，从2中选择节点I

   A           H
 B   C       I   J
D E F G     K L M N

组合后

   A
 B   I
D E K L

我的节点结构:

class Node():
    def __init__(self, element):
        self.element = element
        self.left = None
        self.right = None

我获取随机节点的方法，它将返回一个随机节点:

def getRandomNode(root):
        rootSize = treeCal.treeSize(root)
        leftSize = treeCal.treeSize(root.left) if root.left else 0
        rightSize = treeCal.treeSize(root.right) if root.right else 0
        if leftSize == rightSize == 0: 
            return root
        randNum = random.randint(1, rootSize)
        if randNum <= leftSize: 
            return treeCal.getRandomNode(root.left)
        elif randNum == leftSize + 1:
            return root
        else:
            return treeCal.getRandomNode(root.right)

我目前使用的方法，爸爸和妈妈都是树的根，第一个方法会报错(无法赋值给函数调用)，第二个方法没用:

def recombine(dad, mom):
        child = dad
        getRandomNode(child) = getRandomNode(mom)
        return child

def recombine(dad, mom):
        child = dad
        select = getRandomNode(child)
        select = getRandomNode(mom)
        return child

我在网上查了很久，也没有得到我想要的答案。大多数答案都是将第二棵树插入到第一棵树的末尾，这不符合我的要求。

Answer 1

函数 getRandomNode() 将返回您正在存储的值，函数内的值将被函数内的新值替换。 请注意，您不会以任何方式对树进行更改。您可以修改重组函数来更改随机节点的子节点之一。

def recombine(dad, mom):
    child = dad
    select = getRandomNode(child)
    select2 = getRandomNode(mom)
    if random.randint(0, 1) == 0:
        select.right = select2
    else:
        select.left = select2
    return child