遗传算法项目中二叉树随机选节点替换重组的实现问题

错误原因分析 #

你的两个实现都没有触达二叉树结构修改的核心：修改待替换节点的父节点的子节点指针，问题分别是：

• 第一个实现直接对getRandomNode(child)的返回值赋值，Python不允许将函数调用作为左值赋值，因此直接报错
• 第二个实现仅修改了局部变量select的引用指向，没有改变父节点中存储的子节点指针，因此原树结构没有任何变化

实现思路 #

要完成节点替换，你需要获取待替换节点的父节点，以及它是父节点的左子节点还是右子节点，再修改父节点对应的指针即可。核心步骤如下：

1. 改造随机节点获取方法，同时返回选中节点、它的父节点、以及它是否为父节点的左子节点三个值
2. 从父本(dad)树中获取待替换节点的相关信息
3. 从母本(mom)树中获取要移植的节点，建议做深拷贝避免修改原始母本树
4. 修改父本树中对应父节点的子节点指针，完成替换

完整代码实现 #

1. 改造后的随机节点获取辅助函数 #

def getRandomNodeWithParent(root, parent=None, is_left=False):
    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 (parent, root, is_left)
    randNum = random.randint(1, rootSize)
    if randNum <= leftSize:
        return getRandomNodeWithParent(root.left, root, True)
    elif randNum == leftSize + 1:
        return (parent, root, is_left)
    else:
        return getRandomNodeWithParent(root.right, root, False)

2. 重组函数实现 #

如果需要保留原始父本、母本树不被修改，需要引入深拷贝：

import copy

def recombine(dad, mom):
    # 拷贝父本作为子树基础，避免修改原始dad树
    child = copy.deepcopy(dad)
    # 获取父本中待替换节点的信息
    dad_parent, dad_target, dad_is_left = getRandomNodeWithParent(child)
    # 获取母本中要移植的节点，按需决定是否拷贝母本节点
    mom_target = copy.deepcopy(getRandomNode(mom))
    
    # 处理待替换节点是根节点的特殊情况
    if dad_parent is None:
        return mom_target
    # 替换对应子节点指针
    if dad_is_left:
        dad_parent.left = mom_target
    else:
        dad_parent.right = mom_target
    return child

如果不需要保留原始父本/母本，可以去掉copy.deepcopy调用，直接操作原节点即可，性能更高。

效果验证 #

对应你给出的示例，父本中选中节点C时，返回的dad_parent是A节点，dad_is_left为False，执行dad_parent.right = mom_target（也就是I节点）后，即可得到你展示的重组结果。

内容的提问来源于stack exchange，提问作者bread