Java - Assessing Node Values ​​along a Binary Tree

Question

I am new to Tree structures. I am trying to develop an algorithm that takes a predefined tree as input. Then it should plant the root of the tree with an object of my own design (I don’t think it is related to the design of the algorithm, but the object is an ArrayList) and uses the “change operator” to modify the object along each tree branch. The number of passes of the change statement depends on the length of the branch. An object must be evaluated in each node of the tree, and this node value is then used to evaluate the values ​​of its child nodes. Therefore, I can’t just evaluate the value at each tip using the total length from root to tip, since the change statement that I use is stochastic, not deterministic. Therefore, the value of each child element node depends on the value of its parent node.

I tried to do it myself. I started by creating an array of times when one branch split into its children.

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

Then I created a method that took up the fork time (which I interpreted as the branch length), an ArrayList object, the current time, and the total number of branches.

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

The Brancher method is implemented as follows:

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

So, I save the current state of all objects in the tree, since arrays are stored in ArrayList sequences. Then the evolve method acts on these objects, and updated objects replace the originals in the ArrayList. When you need to add a branch, the Brancher method takes the last Array object in the ArrayList, copies it, and adds the copy to the list. This actually simulated splitting the last object into two objects. The copy is then updated and developed in the next iteration of the simulation cycle.

This way of doing things, though not very, leads to trees that look like this: http://content.science20.com/files/Tree3A.jpg . This is a relatively simple structure.

However, it is not possible to create a tree of this form: http://content.science20.com/files/Tree4.jpg . This tree has several sections in the far right corner. I do not know the exact terminology to describe the differences between the trees here, but its is reasonably obvious.

I think I'm confused here. Any advice on how to think about this issue would be greatly appreciated.

(If this helps with context, the input object is a genetic sequence (ACGT). The idea is to develop a sequence along each tree branch, with each tip representing a descendant of the original (input) sequence)

EDIT

The input object is an ArrayList containing several (nx 2) double arrays. The first column of each array contains n integers from the set {1,2,3,4} that I control. However, the order of these characters in the column is random. Each integer represents one of the characters A, C, G, T in the DNA sequence. The second column contains a double indicator of the rate of evolution for each DNA site, therefore one record of speed for each whole record. The initial array is generated using the function I call DNASEQ, it is very long and does not matter for this question.

To get started, I create one of these arrays and add it to sequences called ArrayList. Using the simulation loop shown above, I then apply the evolvesequence method to each array in the ArrayList.

When Brancher detects that the time that is updated after each cycle in steps of 1 is equal to one of the indicated branches, then it takes the last array in ArrayList and adds a copy of the array to ArrayList. If the simulation stops there, the array will be identical to the one with which it was copied. However, now that it is in an ArrayList, it is subject to the evolvesequence method. Since evolvesequence is a stochastic / probabilistic method, no two outputs are guaranteed to be the same for a given input. So, after several iterations of the simulation cycle, the copied array will be very different from the original.

Answer 1

With an isolated view of your specific task, it can be useful to implement a very special algorithm for your particular tree.

However, as you can see in the comments, this makes it more difficult for outsiders to understand your code, but one will help you. Therefore, I suggest you use this structure: Java tree data structure? .

The benefits are that it is a well-known structure, and anyone with some knowledge of data structures should be able to help you. The structure is typical enough so that it can display all the tree options that you are trying to build.

In addition, it seems that you are building a tree and at the same time you are filling it with data, is that right? This is happening to me just now. It doesn't seem like these two steps are interdependent, so can you first create your tree and then go through it in the second loop to populate it with data? If you can separate these two steps, your code will become much more understandable and understandable.

If you just need to have a binary tree (i.e. a tree with no more than two children in each node), you can even simplify the structure by not having children ArrayList<Node<T>> , but leftChild and rightChild .

After that, you set the root root data to your initial double[][] , then you traverse the tree in the order appropriate for your task and change each node information. From each node, you can access your children and parents, i.e. From each node in the tree, you can access the full information stored in the tree, which should provide you with all the necessary information to update the node data. Of course, you will need to visualize the tree and know exactly which node you are currently on, what information you need and how you can access it (for example, how to get to the information you need).