在 Java 中创建二叉树用于遗传编程

Question

我正在为我正在学习的软件工程课程做一个项目。目标是设计一个程序，该程序将使用遗传编程来生成适合所提供的训练数据的数学表达式。

我刚刚开始研究这个项目，我正在尝试如何创建一个二叉树，该二叉树将允许用户定义树的高度并保持每个节点独立，以便在我开始时使交叉和变异更简单实施这些流程。

这是我迄今为止创建的节点类。请原谅我显然缺乏经验。

public class Node
{
    Node parent;
    Node leftchild;
    Node rightchild;

    public void setParent(Node p)
    {
        parent = p;
    }

    public void setLeftChild(Node lc)
    {
        lc.setParent(this);
        leftchild = lc;
    }

    public void setRightChild(Node rc)
    {
        rc.setParent(this);
        rightchild = rc;
    }   
}


public class OperatorNode extends Node
{
    char operator;


    public OperatorNode()
    {
        double probability = Math.random();

        if (probability <= .25)
        {
            operator = '+';
        }
        else if (probability > .25 && probability <= .50)
        {
            operator = '-';
        }
        else if (probability > .50 && probability <= .75)
        {
            operator = '*';
        }
        else
        {
            operator = '/';
        }
    }

    public void setOperator(char op)
    {
        if (op == '+' || op == '-' || op == '*' || op == '/')
        {
            operator = op;
        }
    }


/**
 * Node that holds x variables.
 */
public class XNode extends Node
{
    char x;

    public XNode()
    {
        x = 'x';
    }    
}

import java.util.Random;


public class OperandNode extends Node
{
    int operand;

    /**
     * Initializes random number generator, sets the value of the node from zero to 9.
     */
    public OperandNode()
    {
        Random rand = new Random();
        operand = rand.nextInt(10);
    }

    /**
     * Manually changes operand.
     */
    public void setOperand(int o)
    {
        operand = o;
    }
}

这从节点本身完成了我需要的一切，但我在试图弄清楚如何将它们变成更大的树时遇到了问题。我意识到我需要使用某种集合类型，但似乎无法在库中找到适合我想做的事情的集合类型。

即使是朝着正确的方向推动，我们也会非常感激。

Answer 1

所以你想构建一棵随机树 OperatorNodes, OperandNode沙 XNode是？你说你想让树深度由用户定义？

定义一个递归函数，称为 buildRandomTree 或类似的东西。应该需要一个 int 树深度参数。如果深度参数为1，则返回一个随机叶节点（OperandNode或XNode）。如果深度参数大于1，则随机生成一个OperatorNode，并递归调用生成左右子树（深度比当前层级小1）。

根据您想要对节点执行的操作，您必须定义其他递归函数。例如，您可能想要生成表达式树的文本表示。为此，您可以定义 toString() 在每个节点类上。（OperatorNode.toString() 必须打电话 toString() 在左子树和右子树上。）

您可能还想评估表达式树（使用给定的变量值）。为此，您可以定义另一个递归函数，可能称为 evaluate(). 。它必须采用一个参数，可能是一个 Map, ，这将给出您想要用来评估表达式的变量值（或“绑定”）。（现在你的表达式树只能包含一个变量“x”，但我想你可能想添加更多。如果您确定只会使用单个变量，那么 evaluate 可以采用单个数字参数作为“x”的值。）

实施 evaluate 你的 3 个节点类都会非常简单。 OperandNode 和 VariableNode 直接返回一个值； OperatorNode 必须打电话 evaluate 在左子树和右子树上，使用适当的操作组合值，然后返回结果。

Answer 2

也许看这个将帮助您。