Aboles NArios - Código fuente para la implementación de un árbol N-Ario en Netbeans. PDF

Preview

Summary

// Creación de los Nodos package arbolesnarios; import java.util; import java.util; public class Nodo<T> { private T dato; private List<Nodo<T>> hijos; private Nodo<T> padre; publi...

Description

// Creación de los Nodos package arbolesnarios;

import java.util.ArrayList; import java.util.List;

public class Nodo { private T dato; private List hijos; private Nodo padre;

public Nodo(T dato) { this.dato = dato; this.hijos = new ArrayList(); }

public Nodo(Nodo nodo) { this.dato = (T) nodo.getDato(); hijos = new ArrayList(); }

public void agregarHijo(Nodo hijo) { hijo.setPadre(this); hijos.add(hijo); }

public void agregarHijoEn(int posicion, Nodo hijo) { hijo.setPadre(this); this.hijos.add(posicion, hijo);

}

public void setHijos(List hijos) { for (Nodo hijo : hijos) hijo.setPadre(this);

this.hijos = hijos; }

public void eliminarHijos() { this.hijos.clear(); }

public Nodo eliminarHijoEn(int posicion) { return hijos.remove(posicion); }

public void eliminarHijo(Nodo hijoABorrar) { List list = getHijos(); list.remove(hijoABorrar); }

public T getDato() { return this.dato; }

public void setDato(T dato) { this.dato = dato;

}

public Nodo getPadre() { return this.padre; }

public void setPadre(Nodo padre) { this.padre = padre; }

public List getHijos() { return this.hijos; }

public Nodo getHijoEn(int posicion) { return hijos.get(posicion); }

@Override public boolean equals(Object obj) { if (null == obj) return false;

if (obj instanceof Nodo) { if (((Nodo) obj).getDato().equals(this.dato)) return true; }

return false; }

@Override public String toString() { return this.dato.toString(); }

}

// Creación del ArbolNArio package arbolesnarios;

import java.util.ArrayList;

public class ArbolNArio {

private Nodo raiz;

public ArbolNArio(Nodo raiz) { this.raiz = raiz; }

public boolean vacio() { return raiz == null; }

public Nodo getRaiz() { return raiz; }

public void setRaiz(Nodo raiz) { this.raiz = raiz; }

public boolean existe(T clave) { return encontrar(raiz, clave); }

public int getNumeroNodos() { return getNumeroDescendientes(raiz) + 1; }

public int getNumeroDescendientes(Nodo nodo) { int n = nodo.getHijos().size(); for (Nodo hijo : nodo.getHijos()) n += getNumeroDescendientes(hijo);

return n;

}

private boolean encontrar(Nodo nodo, T nodoClave) { boolean res = false; if (nodo.getDato().equals(nodoClave)) return true;

else { for (Nodo hijo : nodo.getHijos()) if (encontrar(hijo, nodoClave)) res = true; }

return res; }

private Nodo encontrarNodo(Nodo nodo, T nodoClave) { if(nodo == null) return null; if(nodo.getDato().equals(nodoClave)) return nodo; else { Nodo cnodo = null; for (Nodo hijo : nodo.getHijos()) if ((cnodo = encontrarNodo(hijo, nodoClave)) != null) return cnodo; } return null; }

public ArrayList getPreOrder() { ArrayList preOrder = new ArrayList(); construirPreOrder(raiz, preOrder); return preOrder; }

public ArrayList getPostOrder() { ArrayList postOrder = new ArrayList(); construirPostOrder(raiz, postOrder); return postOrder; }

private void construirPreOrder(Nodo nodo, ArrayList preOrder) { preOrder.add(nodo); for (Nodo hijo : nodo.getHijos()) { construirPreOrder(hijo, preOrder); } }

private void construirPostOrder(Nodo nodo, ArrayList postOrder) { for (Nodo hijo : nodo.getHijos()) { construirPostOrder(hijo, postOrder); } postOrder.add(nodo); }

public ArrayList caminoMasLargo() { ArrayList camino = null; int max = 0; for (ArrayList ruta : getRamas()) { if (ruta.size() > max) { max = ruta.size(); camino = ruta; } }

return camino; }

public int getCaminoMasLargo() { return caminoMasLargo().size(); }

public ArrayList getRamas() { ArrayList rutas = new ArrayList(); ArrayList camino = new ArrayList(); getPath(raiz, camino, rutas);

return rutas; }

private void getPath(Nodo nodo, ArrayList camino, ArrayList rutas) { if (camino == null) return;

camino.add(nodo);

if (nodo.getHijos().size() == 0) { rutas.add(clone(camino)); } for (Nodo hijo : nodo.getHijos()) getPath(hijo, camino, rutas);

int index = camino.indexOf(nodo); for (int i = index; i < camino.size(); i++) camino.remove(index); }

private ArrayList clone(ArrayList list) { ArrayList lista = new ArrayList(); for (Nodo nodo : list) lista.add(new Nodo(nodo));

return lista; } }

//Creación AbolesNArios package arbolesnarios;

public class ArbolesNArios {

public static void main(String[] args) { // TODO code application logic here }

}...