Java - 在二叉树中评估节点值

Question

我对树结构不熟悉。我正在尝试设计一个算法，该算法将预定树作为输入。 它应该使用自己设计的对象（我认为这与算法的设计无关，但该对象是ArrayList）来种子化树的根部，并使用“更改运算符”修改每个分支上的对象。更改运算符的次数取决于分支长度。 必须在树的每个节点处评估对象，然后使用该节点值来评估其子节点的值。因此，我不能简单地使用从根到末端的总长度评估每个末端处的值，因为我使用的更改运算符是随机的，而不是确定性的。因此，每个子节点的值取决于其父节点的值。

我已经尝试自行设计这个算法。我首先创建了一个时间数组，该数组表示单个分支分裂成其子级的时间。

int[] times = new int[branchnumber];
    times[0] = 1;
    times[1] = 5;

然后，我创建了一个方法，该方法需要分叉应发生的时间（我将其解释为分支长度），ArrayList对象，当前时间和总分支数。

public static void Brancher(int[] times, List<double[][]> sequences, int t){
    boolean checker = false;
    for (int i = 0; i < times.length; i++) {
        if (times[i] == t) {
            checker = true;
        }
    }
    if (checker == true) {
        double[][] seq = sequences.get(sequences.size() - 1);
        sequences.add(seq);
    }
}

分支方法的实现如下所示：

for (int j = 0; j <= loopnumber; j++) {
        MathsOperators.Brancher(times, sequences, t);

        for (int i = 0; i < sequences.size(); i++) {
            double[][] sequenceholder = sequences.get(i);
            MathsOperators.PrintOutput(sequenceholder, t);
            ComplexInput.evolvesequence(sequenceholder, frequencies, transitionrate, transversionrate, random);
            sequences.set(i, sequenceholder);
        }

        t = t + dt;
    }

因此，我将树中所有对象的当前状态保存为序列ArrayList中的数组。然后，这些对象由evolve方法处理，并且更新后的对象替换了ArrayList中的原始对象。当要添加分支时，Brancher方法获取ArrayList中的最后一个Array对象，复制它并将副本添加到列表中。这实际上模拟了将最后一个对象分成两个对象。然后更新并在模拟循环的下一次迭代中演化该副本。

这种做事情的方法虽然不太美观，但结果是看起来像这样的树：http://content.science20.com/files/Tree3A.jpg。这是一个相对简单的结构。

然而，无法创建这样形状的树：http://content.science20.com/files/Tree4.jpg。这棵树在最右边有多个分支。我不知道描述这些树之间差异的确切术语，但它们相对明显。

我想我在搞混自己。任何关于如何思考这个问题的建议将不胜感激。

（如果需要上下文帮助，输入对象是一条基因序列（ACGT）。每个末端表示原始祖先（输入）序列的后代，旨在沿树的每个分支演化序列）

编辑

输入对象是一个ArrayList，包含多个（n x 2）个双精度数组。每个数组的第一列包含来自集合{1,2,3,4}中的n个整数，其频率由我控制。但是，该列中这些字符的顺序是随机的。每个整数表示DNA序列中A、C、G、T之一的字符。第二列包含表示每个DNA位点进化速率的双精度数，因此为每个整数条目提供一个速率条目。初始数组使用我称为DNASEQ的函数生成，它非常长，并且对于这个问题没有影响。

首先，我生成其中一个数组，并将其添加到名为sequences的ArrayList中。使用上面显示的模拟循环，然后将evolvesequence方法应用于ArrayList中的每个数组。

当Brancher检测到时间（每次以1的增量更新）等于指定的分支时间之一时，它会获取ArrayList中的最后一个数组并将数组的副本添加到Arraylist中。如果模拟在那里停止，则该数组将与从中复制的数组相同。但是，现在它在ArrayList中，因此受到evolvesequence方法的影响。由于evolvesequence是一种随机/概率方法，因此对于给定的输入，没有两个输出保证相同。因此，在模拟循环的几次迭代后，复制的数组将与原始数组非常不同。

- Jake Watson

---

我不太明白你在这里尝试做什么，但是一个真正的树形数据结构会更有意义，例如在这里：https://dev59.com/5nA75IYBdhLWcg3wAUB9？我不太理解你的代码，例如，递增branchcount似乎没有任何效果...？也许你可以提供更多的代码？ - stef77

也许我没有解释清楚。树应该作为指南或路径，沿着“演化算子”运行。它获取根节点处对象的值，沿着两个分支进行演化，并在分支末端评估修改后的对象。然后，它应该获取每个节点的新值，并按照这些节点下面指定的任何分支继续，直到达到树的末端。我的分支算法只能产生这种形状的树，http://content.science20.com/files/Tree3A.jpg，而不是更复杂的形状，带有子树。 - Jake Watson

我所说的更复杂的例子：http://content.science20.com/files/Tree4.jpg。抱歉，我不知道我试图表达的确切术语。 - Jake Watson

我试图扩展我的原始帖子，并添加了另一个代码片段。这有助于您理解我的目的吗？ - Jake Watson

你能否给一个小例子，展示输入和期望的输出？输出不必包含所有数据，可以简化为一个简单的数字或字符串吗？或者你能将术语映射到你提供的Tree3A.jpg图片中吗？比如，这个图片中的times、branch、tip和node是什么意思？sequences最初是如何填充的？另外，我想试一下，但我相当确定从列表中获取一个数组并再次添加它，会导致列表中出现两个完全相同的对象，而不是它的副本 - 这真的是你想要的吗？ - stef77

Answer 1

如果您只关注特定任务，实现一个非常特殊的算法可能会很有益，但正如评论中所指出的那样，这使得外部人员理解您的代码变得更加困难，更不用说帮助您了。因此，我建议您使用这个结构： Java树数据结构？。

好处在于这是一个众所周知的结构，所有对数据结构有一定了解的人都应该能够帮助您。该结构足够通用，应该能够反映您正在构建的所有树的变体。

此外，看起来您正在构建树并同时填充它，这是正确的吗？这刚刚发生在我身上。看起来这两个步骤并不依赖于彼此，因此您可以先创建树，然后在第二次循环中遍历它以填充数据？如果您可以将这两个步骤分开，您的代码将变得更清晰，更易于理解。

如果您只需要一个二叉树（即每个节点最多有两个孩子的树），您甚至可以通过没有一个ArrayList<Node<T>>作为孩子，而是一个leftChild和rightChild来简化结构。

然后，您将根节点的数据设置为初始的double[][]，然后按照适合您任务的顺序遍历树并修改每个节点的数据。从每个节点，您都可以访问其子节点和父节点，即从树中的每个节点，您都可以访问存储在树中的完整信息，这应该为您提供更新节点数据所需的所有必要信息。当然，您必须可视化树并确切知道您现在在哪个节点上，您需要什么信息以及如何访问它（即如何导航到所需的信息）。

- stef77