我需要从处理数组元素后创建一棵树,遵循以下算法:
逻辑是获取
编辑: 在 JAVA 中有没有一种创建树的方式是从底部(即叶节点)开始的。比如首先创建一个具有两个孩子的父节点,然后将该父节点作为另一个节点的子节点,并逐步达到顶部。因此,在考虑上述示例的情况下,是否有人可以帮助我编写代码。以下是我的代码,我只是无法从叶子创建树。
1. let A[n] be the array
2. while lenght(A) > 1
3. for i = 0 to lenght(A)-2
4. new_A[i] = max(A[i], A[i+1]) + 1
5. end for
6. [minValue, minIndex] = someFunction(new_A) // someFunction returns the minimum value and index of the same
7. delete A[minIndex] and A[minIndex + 1] from A and insert minValue in that place // basically A[minIndex] and A[minIndex + 1] are being replaced by minValue
8. // This is how the length of A is being decreased by 1 in each iteration
9. end while
例子:
+--------------+----------------------+-----------------+---------------+
| iteration No | Array A | Array new_A | Remarks |
+--------------+----------------------+-----------------+---------------+
| 1 | 5-9-3-2-1-6-8-3 |10-10-4-3-7-9-9 | minValue = 3 |
| | | | minIndex = 3 |
+--------------+----------------------+-----------------+---------------+
| 2 | 5-9-3-3-6-8-3 |10-10-4-7-9-9 | minValue = 4 |
| | | | minIndex = 2 |
+--------------+----------------------+-----------------+---------------+
| 3 | 5-9-4-6-8-3 |10-10-7-9-9 | minValue = 7 |
| | | | minIndex = 2 |
+--------------+----------------------+-----------------+---------------+
| 4 | 5-9-7-8-3 |10-10-9-9 | minValue = 9 |
| | | | minIndex = 2 |
+--------------+----------------------+-----------------+---------------+
| 5 | 5-9-9-3 |10-10-10 | minValue = 10 |
| | | | minIndex = 0 |
+--------------+----------------------+-----------------+---------------+
| 6 | 10-9-3 |11-10 | minValue = 10 |
| | | | minIndex = 1 |
+--------------+----------------------+-----------------+---------------+
| 7 | 10-10 |11 | minValue = 11 |
| | | | minIndex = 0 |
+--------------+----------------------+-----------------+---------------+
| 8 | 11 |-- | -- |
+--------------+----------------------+-----------------+---------------+
到目前为止一切都没问题。但我需要将这个表示成一棵树。得到的树如下所示:
iteration# 8 11
/ \
/ \
iteration# 7 / \------- 10
/ / \
iteration# 6 10 / \
/ \ / \
iteration# 5 | | 9 \
| | / \ \
iteration# 4 | | 7 \ \
| | / \ \ |
iteration# 3 | | 4 \ \ |
| | / \ \ \ |
iteration# 2 | | / 3 \ \ |
| | / / \ \ \ |
iteration# 1 5 9 3 2 1 6 8 3
逻辑是获取
minValue
并将其设置为根,将对应的数组元素(从中获取了 minValue
)作为子代。这就是我们如何构建树的过程。可以称之为二叉树,因为每个节点恰好有两个孩子。我的问题是,如果我将先前的根节点视为其中一个孩子,可能无法获得精确答案。因为在迭代 5 中,我得到的 minValue
不是上一个根的贡献。因此,我之前制作的整个树可能会丢失。是否有任何方法可以获得整个树结构?我正在使用 JAVA。编辑: 在 JAVA 中有没有一种创建树的方式是从底部(即叶节点)开始的。比如首先创建一个具有两个孩子的父节点,然后将该父节点作为另一个节点的子节点,并逐步达到顶部。因此,在考虑上述示例的情况下,是否有人可以帮助我编写代码。以下是我的代码,我只是无法从叶子创建树。
public class Main {
private static int GATE_COST = 1;
private static BinaryTree bt;
private static float num;
public static void main(String[] args) throws IOException {
File filePin = new File("C:/somePath/files/pin.txt");
BufferedReader buffer = new BufferedReader(new FileReader(filePin));
String line = buffer.readLine();
int lenData = Integer.parseInt(line.trim());
float[] data = new float[lenData];
for (int i = 0; i < lenData; i++) {
line = buffer.readLine();
data[i] = Float.parseFloat(line.trim());
}
bt = new BinaryTree();
num = sysnthesis(data);
System.out.println("\nArrival: " + num);
}
private static float sysnthesis(float[] data) {
while (data.length > 1) {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + " ");
}
float[] cost = getCost(data);
float minValue = cost[0];
int minIndex = 0;
for (int i = 0; i < cost.length; i++) {
if (cost[i] < minValue) {
minValue = cost[i];
minIndex = i;
}
}
createTree(data, minValue, minIndex); // I am not able to create its body
data = getNewData(data, minValue, minIndex);
System.out.print("\n");
}
System.out.print(data[0]);
return data[0];
}
private static float[] getCost(float[] data) {
float[] cost = new float[data.length - 1];
for (int i = 0; i < data.length - 1; i++) {
cost[i] = Math.max(data[i], data[i+1]) + GATE_COST;
}
return cost;
}
private static float[] getNewData(float[] data, float minValue, int minIndex) {
float[] newData = new float[data.length - 1];
int i = 0;
for (; i < minIndex; i++) {
newData[i] = data[i];
}
newData[i++] = minValue;
for (; i < data.length - 1; i++) {
newData[i] = data[i+1];
}
return newData;
}
private static void createTree(float[] data, float minValue, int minIndex) {
/**
My code goes here
*/
}
}
pin.txt包含以下内容:
8
5.0
9.0
3.0
2.0
1.0
6.0
8.0
3.0
Thanks in advance
Node root = null;
。 - paulsm4someFunction
的逻辑)似乎是_取两个最小最大相邻节点,将它们创建为一个新的父节点,并将该最大值的后继作为该父节点的值_。 - greybeard