Создание дерева в Java

Question

Я написал следующий класс дерево:

public class Tree { 

    private TreeNode root; 


    private static class TreeNode { 
     private Pair<String, Float> data; 
     private TreeNode leftNode; 
     private TreeNode rightNode; 

     private TreeNode(Pair<String, Float> data, TreeNode left, TreeNode right) { 
      this.data = data; 
      this.leftNode = left; 
      this. rightNode = right; 
     } 
    } 
} 

Следующий вход:

"<Hello, 123>" 
"<Hi, 1234>" 
"<John, 42142>" 
"null" 
"<Chris, null>" 
"<Peter, null>" 
"null" 

А теперь я хочу, чтобы написать функцию, которая принимает этот вход как ArrayList, как это:

ArrayList<Pair<String,Float> input = {"<Hello, 123>", "<Hi, 1234>", "<John, 42142>", "null", "Chris, null", "Peter, null", "null"}; 

и создает Tree с использованием описанного выше типа.

ПРИМЕЧАНИЕ: если в каком-либо положении массива значение равно null, это означает, что там не должно быть узлов.

Вот что я сделал до сих пор:

public createTree(ArrayList<Pair<String, Float>> treeAsVector) { 

    int nodes = treeAsVector.size(); 

    root = new TreeNode(treeAsVector.get(0), null,null); 

    for (int i = 1; i < treeAsVector.size(); i++) { 

     if(treeAsVector.get(i) == null) 
      i++;//skips the node 
     else 
      //not sure what to do here 

} 

} 

мне нужна помощь, потому что я не очень хорошо понимая, как я должен создать дерево, потому что каждый TreeNode потребуется две дополнительные TreeNode's , то есть я всегда видеть один шаг впереди ...

UPDATE:

отображение в дерево должно быть сделано в уровнях, как это:

     TreeNode 
         (root) 
      TreeNode    TreeNode 
      2      3 
TreeNode  TreeNode 
    4    5  

если значение в ArrayList равно null, оно не отображается.

Answer 1

public void generateTree(ArrayList<Pair<String , Float>> vector){ 
    //todo holds all nodes that haven't yet had their children assigned 
    ArrayList<TreeNode> todo = new ArrayList<>(); 
    todo.add(new TreeNode(vector.remove(0) , null , null)); 
    TreeNode root = todo.get(0); 

    while(!todo.isEmpty() && !vector.isEmpty()) 
    { 
     TreeNode node = todo.remove(0); 

     if(node == null) 
      continue; 

     //generate the children for the current node 
     TreeNode left = vector.get(0) == null ? null : new TreeNode(vector.get(0) , null , null); 
     TreeNode right = vector.get(1) == null ? null : new TreeNode(vector.get(1) , null , null); 

     vector.remove(0); 
     vector.remove(0); 

     node.leftNode = left; 
     node.rightNode = right; 

     //left and right haven't yet had their children assigned 
     //queue them, so that they will be processed as soon as the 
     //rest of the queue before them has been processed 
     todo.add(left); 
     todo.add(right); 
    } 
} 

Во время этого процесса vector будет опорожнен !!! Этого можно избежать, используя счетчик вместо удаления содержимого. Этот алгоритм также должен работать и для несбалансированных деревьев. Основная идея - добавить все узлы в очередь. Таким образом, все узлы могут обрабатываться по их уровню.