Nwlapcug.com


Come Postorder l'attraversamento in un albero binario in Java

Se Java non fornisce una classe di albero binario in librerie predefinite, una classe di base albero binario è abbastanza semplice da essere presentato. Un "attraversamento" di una struttura di dati è un algoritmo che visita una volta ogni nodo. Questo è spesso implementato come una sorta di iteratore (molto simile a un iteratore elenco) o metodo che verrà chiamato un metodo di callback per ogni nodo. In Java, per fare un attraversamento "postorder" che visiterà il nodo radice ultima, nessun callback o gli iteratori sono necessari. La funzione di attraversamento semplicemente stamperà ogni nodo visita alla console.

Istruzioni

1

Scrivere una classe di albero binario di ricerca base. Esistono solo due metodi che devono essere supportate in questa fase: un costruttore di base che inizializza il valore del nodo e un metodo di inserimento. Il metodo insert sarà attraversare un albero e creare un nuovo nodo nella posizione corretta.""public class BinaryTree {
BinaryTree left;
BinaryTree right;
int value;

public BinaryTree(int v) {
value = v;
}

// Insert a value into the tree
public void insert(int v) {
if(v < value) {
if(left == null)
left = new BinaryTree(v);
else
left.insert(v);
}

else if(v > value) {
if(right == null)
right = new BinaryTree(v);
else
right.insert(v);
}
}""

2

Creare un'istanza di albero binario che sarà il nodo radice. Ogni nodo, anche il nodo radice, deve avere un valore.

3

Scegliere un valore per il nodo radice che è da qualche parte nel mezzo, gli oggetti si potrà essere la memorizzazione. Ad esempio, se si sta archiviando una distribuzione uniforme di numeri da 1 a 100, 50 è una buona scelta per il nodo radice. Alberi binari devono essere più equilibrato possibile, poiché squilibrati alberi crescono estremamente alti e non sono molto efficaci.""BinaryTree b = new BinaryTree(50);""

4

Inserire alcuni nodi nell'albero. Poiché questo albero non è auto-bilanciamento, per mantenere l'equilibrio, i nodi devono essere inseriti in un ordine specifico. L'ordine in questo codice di esempio è realizzato per rendere l'albero più breve e più efficiente possibile.""b.insert(20);
b.insert(40);
b.insert(10);
b.insert(5);
b.insert(45);

b.insert(70);
b.insert(60);
b.insert(80);
b.insert(55);
b.insert(85);""

5

Attraversare l'albero, attraversare l'albero di sinistra in primo luogo, seguito dall'albero giusto e poi finalmente il nodo radice. Se la ricorsione è utilizzata per fare l'attraversamento postorder, il metodo è lunga solo tre righe. In questo caso, lo stack potrà solo crescere fino all'altezza dell'albero. Dal momento che l'albero è equilibrato e piccolo, ricorsione non supererà lo stack.

6

Aggiungere nuovo metodo alla classe BinaryTree chiamata postorder. Qui, viene stampato solo il valore di ciascun nodo visita.""public void postorder() {
if(left != null) left.postorder();
if(right != null) right.postorder();
System.out.println(value);
}""

7

Stampare i nodi in postorder chiamando il metodo b.postorder dopo gli inserti.

""b.postorder();"

Consigli & Avvertenze

  • Poiché la ricorsione richiede spazio dello stack, deve essere usato con attenzione. Se il vostro albero binario è molto grande, la funzione di attraversamento deve essere implementata in modo iterativo.
  • Il metodo più complicato "Elimina nodo" non è supportato da questa classe di esempio.