Werte aus einem BinärBaum in einem Array speichern

[dan1996]

Hallo ich habe folgende Klasse und möchte in meiner arrayStorage Methode ein Array mit allen werten im Baum returnen.
Weiß jemand wo mein Fehler ist oder welche Verbesserungen ich einbauen kann?

class Node {

    public int v;

    public Tree l, r;

    public Node(int v) {
        this.v = v;
        this.l = new Tree();
        this.r = new Tree();
    }
}

class Tree {
    public Node root = null;

    public boolean isEmpty() {
        return root == null;
    }

    public void insert(int x) {
        if (isEmpty())
            root = new Node(x);
        else if (x < root.v)
            root.l.insert(x);
        else
            root.r.insert(x);
    }

    public String toString() {
        if (isEmpty())
            return "";
        else
            return "" + root.r + root.l + ";" + root.v;
    }
    
    /**
     *
     * @return Anzahl der Knoten im Baum
     */
    public int countNode() {
        if (this.root == null) {
            return 0;
        } else {
            int count = 1;
            count += root.l.countNode();
            count += root.r.countNode();
            return count;
        }
    }
    
    
    /**
     *
     * @return alle Knoten im Baum in einem Array
     */
    public int[] arrayStorage() {
        int[] a = new int[countNode()];
        int count = 1;
        if(root != null) {
            root.l.arrayStorage();
            root.r.arrayStorage();
            a[count] = root.v;
            count++;
            return a;
        }
        else {
            a = null;
            return a;
        }
    }
}

 

[httpdigest]

Du ignorierst ja in den rekursiven Aufrufen von `root.l.arrayStorage()` und `root.r.arrayStorage()` vollkommen den Rückgabewert. Diese rekursiven Aufrufe erzeugen ihrerseits ja auch wieder Arrays für die linken und rechten Teilbäume.
Tipp: Schreibe dir eine private Hilfsmethode, die - gegeben ein int[] Array mit der erwarteten Gesamtgröße - sich selbst rekursiv für die linken und rechten Teilbäume aufruft und einen weiteren int Akkumulator als Parameter sowie als Rückgabewert hat, der angibt, wo gerade im Array als nächstes ein Eintrag einzufügen ist.
So vermeidest du, dass jeder Teilbaum selbst wieder die Knoten unter sich zählen muss und du diverse Arrays konkatenieren müsstest.

Spoiler

private int arrayStorage(int[] arr, int i) {
  if (root == null)
    return i;
  arr[i++] = root.v;
  return root.r.arrayStorage(arr, root.l.arrayStorage(arr, i));
}
public int[] arrayStorage() {
  int[] arr = new int[countNode()];
  arrayStorage(arr, 0);
  return arr;
}