Come aggirare la mancanza di puntatori di Java verso i puntatori quando si lavora con strutture dati collegate? [chiuso]

Una parte del problema è che non stai seguendo i buoni principi OO.

In questo caso, quello che probabilmente è più applicabile è " Dillo, non chiedere ": se vuoi un Node per aggiungere un bambino, dovresti dire per aggiungere un bambino, non dovresti chiedergli per esporre tutte le informazioni rilevanti di cui hai bisogno, quindi andare avanti e aggiungere il bambino per esso. Allo stesso modo, se (perché stai facendo una soluzione iterativa), devi attraversare un livello lungo l'albero, dire il Node che vuoi attraversare al bambino appropriato, non chiedi per tutto ciò che devi sapere per eseguire autonomamente il calcolo.

Si consideri:

private class Node {
    int key;
    int val;
    Node left = null;
    Node right = null;
    Node (int k, int v) {
        key = k; val = v;
    }

   public Node traverseNext(int targetKey) {
       if (key==target) {
           return null;
       }
       return key < target ? left : right;
   }

   public void setChild(int key, int value) {
       if (key == this.key) {
           return;
       }
       if (key < this.key) {
           left = new Node(key, value);
       }
       else {
           right = new Node(key, value);
       }
   }

Quindi un chiamante che desidera aggiungere un figlio dovrebbe solo fare:

Node node;
Node nextNode = root;

while(nextNode != null) {
    node = next;
    nextNode = node.traverseNext(key);
}

node.setChild(key, value);

(Scusa eventuali errori, Java non è la mia lingua madre)

Questo non è esattamente il codice stellare perché ho dovuto fare di tutto per ovviare all'ovvia soluzione ricorsiva. Ad esempio, non si vorrebbe realisticamente esporre un metodo che sostituisce allegramente un bambino con un altro, se richiesto. Ma dovrebbe dare l'idea di base.

Nota: mi rendo conto che ciò non affronta molto direttamente il problema che ha causato la differenza tra questi due esempi di codice: la capacità che un puntatore ha che un riferimento non ha. Ma sono anche dell'opinione che non è una coincidenza che non appena risolvi questo problema in modo idiomatico Java, quella differenza cessa di essere rilevante.

Puoi evitare la ripetizione creando il nuovo child Node s in precedenza e impostandoli come predefiniti a vuoto, invece di usare null per rappresentare un Node vuoto. Il corpo del tuo ciclo while potrebbe essere simile a:

Node child = node.right;
if (k < node.key)
    child = node.left;
if (child.isEmpty()) {
    child.set(k, v);
    child.left  = new Node();  //Could be done inside set
    child.right = new Node();
    return;
} else {
    node = child;
}

Questo sostanzialmente prealloca il prossimo livello di foglie, ma non dovrebbe essere troppo pesante. Un'altra opzione potrebbe sostituire left e right con children[2] , quindi puoi utilizzare l'indice di array per evitare la ripetizione.

Non c'è modo di fare ciò che vuoi fare in Java. Java non offre la libertà di C quando si tratta di puntatori. Gli unici riferimenti a Java sono i riferimenti a oggetti.

Il tuo primo tentativo è quindi buono come puoi fare in Java. Devi distinguere il caso di inserimento a sinistra, a destra e alla radice. Se la creazione e l'inizializzazione del nodo sono complesse, è possibile spostare il codice di creazione del nodo in una procedura.

L'aggiunta di un oggetto Link è un'idea intelligente, ma complica la struttura dei dati come hai notato. Influisce anche su tutti gli altri metodi che manipolano o attraversano l'albero, e questo solo per rendere più elegante il metodo di inserimento. Un po 'sciocco se ci pensi.

Quindi la risposta è che non puoi. Detto questo, sono sicuro che è solo un esercizio, quindi sperimenta come vuoi. Ma nella vita reale, prima di scrivere il tuo albero di ordinamento binario, assicurati che nessuna raccolta Java soddisfi le tue esigenze. E se non lo fanno, controlla framework open source come Google guava.

La risposta di Ben Aaronson è molto meglio di entrambi i miei tentativi, ma penso che la ragione principale sia la tecnica che usa per scorrere l'albero, usando due% puntatori di% di enunciazione anziché uno, piuttosto che lo stile più orientato agli oggetti . L'intera faccenda può essere sottolineata, il che consente un confronto diretto con la mia versione e mostra che è effettivamente più elegante, separando nettamente l'attraversamento dell'albero dalla creazione del nodo (anche se richiede ancora il doppio del codice della versione C ++):

void insert(int k, int v) {
    if (root == null) {
        root = new Node(k, v);
        return;
    }

    Node node = root;
    Node next = root;

    while (next != null) {
        node = next;
        if (k == node.key) 
            next = null;
        else
            next = k < node.key ? node.left : node.right;
    }

    if (k == node.key)
        node.val = v;
    else if (k < node.key)
        node.left = new Node(k, v);
    else if (k > node.key)
        node.right = new Node(k, v);
}

Accolgo i punti più ampi di Ben sul valore dell'utilizzo dei principi OO, e chiaramente il codice viene ulteriormente migliorato dividendolo in metodi separati come ha fatto lui.