2015-10-30 4 views
2

Мне нужно создать дерево из массива после обработки элементов по следующему алгоритму:Создание бинарного дерева из массива

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 

Заранее спасибо

+1

Q: Есть ли что я могу сделать, чтобы получить Whol e древовидная структура?A: Всякий раз, когда вы создаете такое дерево, вы почти всегда сохраняете исходный узел в отдельной переменной, например. «Корень». ПРИМЕР: 'Node root = null;'. – paulsm4

+0

@ paulsm4: Вы имеете в виду создать ArrayList или что-то типа Node и сохранить предыдущий узел в ArrayList всякий раз, когда я создаю новое дерево? – OptimusPrime

+0

Нет. Я имею в виду, что «дерево» состоит из «узлов». Каждый узел содержит 1) данные и 2) ссылки на соседние узлы. «Прилегающие узлы» будут меняться по мере вашего дерева. Но вы всегда хотите сохранить ссылку на первый, «корневой» узел. – paulsm4

ответ

1

Я думаю, что сам нашел ответ на свою проблему, поэтому просто хочу поделиться им. Это своего рода комплексное решение, но он отлично работает, и я пробовал с 10-100 входными штырьками, он дает мне правильное дерево. Я разделяю код JAVA.

Main.java

public class Main { 

private static int GATE_COST = 1; 
private static BinaryTree bt; 
private static ArrayList<Node> arrNodes; 
private static int currDepth = 0; 

public static void main(String[] args) throws IOException { 
    File filePin = new File("C:/Users/Arindam/workspace/TreeSynthesis/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()); 
    } 
    arrNodes = new ArrayList<Node>(); 
    bt = new BinaryTree(); 
    String arrival = sysnthesis(data); 
    System.out.println("Arrival: " + arrival); 
    System.out.println("Topology: "); 
    bt.printPostorder(); 
} 

private static String sysnthesis(float[] data) { 
    ArrayList<Node> dataNodes = convertArraytoNode(data); 
    while (dataNodes.size() > 1) { 
     for (int i = 0; i < dataNodes.size(); i++) { 
      System.out.print(dataNodes.get(i).getData() + " "); 
     } 
     float[] cost = getCost(dataNodes); 

     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(dataNodes, minValue, minIndex); 
     dataNodes = getNewDataNodes(dataNodes, minValue, minIndex); 
     //bt.printPostorder(); 
     System.out.println(); 
    } 
    System.out.print(dataNodes.get(0).getData()+ "\n"); 
    return dataNodes.get(0).getData(); 
} 

private static ArrayList<Node> convertArraytoNode(float[] data) { 
    ArrayList<Node> dataNodes = new ArrayList<Node>(); 
    for (int i = 0; i < data.length; i++) { 
     dataNodes.add(new Node(Float.toString(data[i]), 0)); 
    } 
    return dataNodes; 
} 

private static float[] getCost(ArrayList<Node> dataNodes) { 
    float[] cost = new float[dataNodes.size() - 1]; 
    for (int i = 0; i < dataNodes.size() - 1; i++) { 
     cost[i] = Math.max(Float.parseFloat(dataNodes.get(i).getData()), 
       Float.parseFloat(dataNodes.get(i+1).getData())) + GATE_COST; 
    } 
    return cost; 
} 

private static ArrayList<Node> getNewDataNodes(ArrayList<Node> dataNodes, float minValue, int minIndex) { 
    dataNodes.get(minIndex).setData(Float.toString(minValue)); 
    dataNodes.get(minIndex).setDepth(currDepth); 
    dataNodes.remove(minIndex + 1); 
    return dataNodes; 
} 


private static void createTree(ArrayList<Node> dataNodes, float minValue, int minIndex) { 
    Node root = null, lChild = null, rChild = null; 
    root = new Node(Float.toString(minValue), ++currDepth); 
    int flag = 0; 
    ArrayList<Integer> deleteIndex = new ArrayList<Integer>(); 
    if (!arrNodes.isEmpty()) { 
     for (int i = 0; i < arrNodes.size(); i++) { 
      if (arrNodes.get(i).getData().equals(dataNodes.get(minIndex).getData()) && 
        dataNodes.get(minIndex).getDepth() == currDepth - arrNodes.size() + i) { 
       flag++; 
       lChild = arrNodes.get(i); 
       deleteIndex.add(i); 
      } 
      else if (arrNodes.get(i).getData().equals(dataNodes.get(minIndex + 1).getData()) && 
        dataNodes.get(minIndex + 1).getDepth() == currDepth - arrNodes.size() + i) { 
       flag++; 
       rChild = arrNodes.get(i); 
       deleteIndex.add(i); 
      } 
     } 
     if (flag == 0) { 
      lChild = new Node(dataNodes.get(minIndex).getData(), 0); 
      rChild = new Node(dataNodes.get(minIndex + 1).getData(), 0); 
     } else if (flag == 1 && null == rChild){ 
      rChild = new Node(dataNodes.get(minIndex + 1).getData(), 0); 
     } else if (flag == 1 && null == lChild) { 
      lChild = new Node(dataNodes.get(minIndex).getData(), 0); 
     } 
     for (int i = deleteIndex.size() - 1; i > 0; i--) { 
      dataNodes.remove(deleteIndex.get(i)); 
     } 
    } else { 
     lChild = new Node(dataNodes.get(minIndex).getData(), 0); 
     rChild = new Node(dataNodes.get(minIndex + 1).getData(), 0); 
    } 
    bt.buildTree(root, lChild, rChild); 
    arrNodes.add(bt.getRootNode()); 
} 
} 

BinaryTree.java

public class BinaryTree { 

private Node root; 

public BinaryTree() { 
    root = null; 
} 


public void buildTree(Node rt, Node lChild, Node rChild) { 
    root = rt; 
    root.left = lChild; 
    root.right = rChild; 
} 

public int size() { 
    return(size(root)); 
} 
private int size(Node node) { 
    if (node == null) return(0); 
    else { 
     return(size(node.left) + 1 + size(node.right)); 
    } 
} 

public int maxDepth() { 
    return(maxDepth(root)); 
} 
private int maxDepth(Node node) { 
    if (node==null) { 
     return(0); 
    } 
    else { 
     int lDepth = maxDepth(node.left); 
     int rDepth = maxDepth(node.right); 

     // use the larger + 1 
     return(Math.max(lDepth, rDepth) + 1); 
    } 
} 

public void printTree() { 
    printTree(root); 
    System.out.println(); 
} 
private void printTree(Node node) { 
    if (node == null) return; 
    printTree(node.left); 
    System.out.print(node.data + " "); 
    printTree(node.right); 
} 

public void printPostorder() { 
    printPostorder(root); 
    System.out.println(); 
} 

public void printPostorder(Node node) { 
    if (node == null) return; 

    printPostorder(node.left); 
    printPostorder(node.right); 

    System.out.print(node.data + " "); 
} 

public Node getRootNode() { 
    return root; 
} 

public int getNodeDepth() { 
    return root.depth; 
} 

public Node getRChildNode() { 
    return root.right; 
} 

public Node getLChildNode() { 
    return root.left; 
} 
} 

Node.java

public class Node { 
Node left; 
Node right; 
String data; 
int depth; 

Node(String newData, int depth) { 
    this.left = null; 
    this.right = null; 
    this.data = newData; 
    this.depth = depth; 
} 

public Node getLeft() { 
    return left; 
} 

public void setLeft(Node left) { 
    this.left = left; 
} 

public Node getRight() { 
    return right; 
} 

public void setRight(Node right) { 
    this.right = right; 
} 

public String getData() { 
    return data; 
} 

public void setData(String data) { 
    this.data = data; 
} 

public int getDepth() { 
    return depth; 
} 

public void setDepth(int depth) { 
    this.depth = depth; 
} 
} 
0

Ваше дерево выглядит странно - как ребенок родительского узла 11 является 10. В чем смысл? Разве они не должны сливаться в одну? В любом случае, пожалуйста, проверьте параллельные ветви дерева. Java tree data-structure?

Это должно помочь.

В целом вам необходимо создать класс Node, который содержит idx \ значение точного узла и ссылки на два дочерних узла. Рекурсивно вы сможете построить такую ​​структуру данных.

+0

Не имеет значения, каковы значения. Он может быть равен. Это не BST. – OptimusPrime

+0

Я могу создать узел и связать два дочерних узла и все. Но реальная проблема заключается в том, что если вы посмотрите в итерации 5. до итерации 4, предыдущий узел был одним из дочерних элементов нового родительского узла. Но в итерации 5, minValue - это что-то еще и, наконец, в итерации 6 эти два значения являются дочерними элементами нового родительского узла. Моя проблема в том, что я должен хранить все дерево в некоторой временной переменной. Но заранее я не знаю, сколько таких переменных temp мне нужно. Поэтому я искал способ обхода этого дерева. – OptimusPrime

Смежные вопросы