Java

Question

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

我尝试过自己设计这个。我首先创建了一个时间数组，在这些时间中，单个分支会分裂成它的子分支。

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);
    }
}

Brancher方法实现如下：

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 的函数生成的，它很长，对这个问题没有影响。

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

当Brancher检测到每次循环后以1为增量更新的时间等于指定的分支次数之一，则取ArrayList中的最后一个Array并添加该数组的副本到数组列表。如果模拟就此停止，阵列将与复制它的阵列相同。但是，现在它在 ArrayList 中，它受制于 evolvesequence 方法。由于 evolvesequence 是一种 stochastic/probabilistic 方法，因此对于给定的输入，不能保证两个输出是相同的。因此，在模拟循环的几次迭代之后，复制的数组将与原始数组有很大不同。

Answer 1

从孤立的角度看待您的特定任务，为您非常特殊的树实施非常特殊的算法可能会有所帮助。

但是，正如您在评论中看到的那样，这使得外人更难理解您的代码，但独自帮助您。因此，我建议你使用这种结构：Java tree data-structure?.

好处是这是一个 well-known 结构，任何对数据结构有一定了解的人都应该能够帮助你。该结构足够通用，应该能够反映您尝试构建的树的所有变体。

此外，您似乎在构建树的同时用数据填充它，对吗？这是我刚才想到的。看起来这两个步骤并不相互依赖，所以您可以先创建树，然后在第二个循环中遍历它以便用数据填充它？如果你能把这两个步骤分开，你的代码会变得更加清晰易懂。

如果你只想要一棵二叉树（即每个节点最多有两个 children 的树），你甚至可以通过不使用 ArrayList<Node<T>> 作为 [=28] 来简化结构=]，但是 leftChild 和 rightChild.

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

Java - 沿二叉树评估节点值

Java - Evaluating Node Values along a Binary Tree

tree

binary-tree

tree-traversal

编辑