Мне нужно создать дерево из массива после обработки элементов по следующему алгоритму:Создание бинарного дерева из массива
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
пришел) детей. Так мы можем вырастить дерево. Его можно каким-то образом назвать двоичным деревом, так как каждый узел имеет ровно 2 ребенка. Проблема, с которой я сталкиваюсь, заключается в том, что если я возьму предыдущий корень как один из детей, я не получу точный ответ. Потому что смотрите в итерации 5, minValue
Я получаю не вклад предыдущего корня. Так что теперь все мое ранее сделанное дерево может потеряться. Есть ли что-нибудь, что я могу сделать, чтобы получить всю структуру дерева? Я использую JAVA.
EDIT: Есть ли способ, чтобы создать дерево из нижней части (т.е. узел листа) в 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
Заранее спасибо
Q: Есть ли что я могу сделать, чтобы получить Whol e древовидная структура?A: Всякий раз, когда вы создаете такое дерево, вы почти всегда сохраняете исходный узел в отдельной переменной, например. «Корень». ПРИМЕР: 'Node root = null;'. – paulsm4
@ paulsm4: Вы имеете в виду создать ArrayList или что-то типа Node и сохранить предыдущий узел в ArrayList всякий раз, когда я создаю новое дерево? – OptimusPrime
Нет. Я имею в виду, что «дерево» состоит из «узлов». Каждый узел содержит 1) данные и 2) ссылки на соседние узлы. «Прилегающие узлы» будут меняться по мере вашего дерева. Но вы всегда хотите сохранить ссылку на первый, «корневой» узел. – paulsm4