Двоичного дерево в заказовМой массив

Question

Довольно простой вопрос:

Рекурсивных как я могу создать массив двоичного дерева поиска (в порядке), который использует этот конструктор:

public class OrderedSet<E extends Comparable<E>> { 
    private class TreeNode { 
    private E data; 
    private TreeNode left, right; 

    public TreeNode(E el) { 
     data = el; 
     left = null; 
     right = null; 
    } 
} 

    private TreeNode root; 
    public int size = 0; 

    public OrderedSet() { 
    root = null; 
    } 

Answer 1

В-заказ означает, что вы сначала нужно пройти через левую часть дерева, так:

TreeNode tree // this is your tree you want to traverse 
E[] array = new E[tree.size]; // the arrays length must be equivalent to the number of Nodes in the tree 
int index = 0; // when adding something to the array we need an index 
inOrder(tree, array, index); // thats the call for the method you'll create 

сам метод может выглядеть примерно так:

public void inOrder(TreeNode node, E[] array, int index){ 
    if(node == null){ // recursion anchor: when the node is null an empty leaf was reached (doesn't matter if it is left or right, just end the method call 
     return; 
    } 
    inOrder(node.getLeft(), array, index); // first do every left child tree 
    array[index++]= node.getData();   // then write the data in the array 
    inOrder(node.getRight(), array, index); // do the same with the right child 
} 

В некотором роде. Я просто не уверен в индексе и там, где его нужно увеличивать. Если вы не хотите беспокоиться об индексе, или если вы не знаете, сколько узлов находится в дереве, используйте вместо него ArrayList и преобразуйте его в конец в массив.

Обычно уборщик вызов метода строится вокруг рекурсивного метода, как это:

public E[] inOrderSort(TreeNode tree){ 
    E[] array = new E[tree.size]; 
    inOrder(tree, array, 0); 
    return array; 
} 

Answer 2

Спасибо, что хорошо работали. Java не позволит мне создавать массив дженериков, поэтому, используя ваш алгоритм, я заставил его работать с ArrayList (как и вы предложили). Вот этот метод (с использованием указанного выше конструктора) просто заставляет кого-то другого задавать тот же вопрос. (Ref - моя ссылка на текущий узел дерева)

public ArrayList<E> toArray() { 
    ArrayList<E> result = new ArrayList<E>(); 
    toArrayHelp(root, result); 
    return result; 
} 

private void toArrayHelp(TreeNode ref, ArrayList<E> result) { 
    if (ref == null) { 
     return; 
    } 
    toArrayHelp(ref.left, result); 
    result.add(ref.data); 
    toArrayHelp(ref.right, result); 
}