Ecco un altro post sulle Strutture Dati, come da programma passiamo agli Alberi e gli Alberi Binari, non posto anche le implementazioni di EulerTour dato che si possono copiare dalle slides del prof, e inoltre ho dovuto rallentare il ritmo perché il tempo è sempre meno.
public class LinkedTree<E> implements Tree<E>
{
protected TreePosition<E> root;
protected int size;
public LinkedTree()
{
root = new TreeNode<E>();
size = 0;
}
public LinkedTree(E rootElement)
{
addRoot(rootElement);
}
public LinkedTree(TreePosition<E> r)
{
root = r;
if (root != null)
size = r.getChildren().size()+1;
else
size = 1;
}
public Iterator<E> iterator()
{
Iterable<Position<E>> positions = positions();
PositionList<E> elements = new NodePositionList<E>();
for(Position<E> pos: positions)
elements.addLast(pos.element());
return elements.iterator();
}
public int size()
{
return size;
}
public boolean isEmpty()
{
return (size == 0);
}
public Iterable<Position<E>> positions()
{
PositionList<Position<E>> lista = new NodePositionList<Position<E>>();
if (size != 0)
preorderPosition(root(), lista);
return lista;
}
public E replace(Position<E> p, E e) throws InvalidPositionException
{
TreeNode<E> nodo = (TreeNode<E>) checkPosition(p);
E tmp = nodo.element();
nodo.setElement(e);
return tmp;
}
public Position<E> root() throws EmptyTreeException
{
if (isEmpty())
throw new EmptyTreeException();
return root;
}
public Position<E> parent(Position<E> p) throws InvalidPositionException, BoundaryViolationException
{
TreeNode<E> tmp = (TreeNode<E>) checkPosition(p);
if (tmp == root)
throw new BoundaryViolationException("Root has no parent!");
return tmp.parent;
}
public Iterable<Position<E>> children(Position<E> p) throws InvalidPositionException
{
TreeNode<E> nodo = (TreeNode<E>) checkPosition(p);
if(isExternal(nodo))
throw new InvalidPositionException("External nodes do not have children!");
return nodo.getChildren();
}
public boolean isInternal(Position<E> p) throws InvalidPositionException
{
return (!isExternal(p));
}
public boolean isExternal(Position<E> p) throws InvalidPositionException
{
TreeNode<E> nodo = (TreeNode<E>) checkPosition(p);
return (nodo.getChildren() == null);
}
public boolean isRoot(Position<E> p) throws InvalidPositionException
{
TreeNode<E> nodo = (TreeNode<E>) checkPosition(p);
return (nodo.equals(root()));
}
public TreePosition<E> checkPosition(Position<E> p)throws InvalidPositionException
{
if (p == null || !(p instanceof TreePosition))
throw new InvalidPositionException();
return (TreePosition<E>) p;
}
protected void preorderPosition(Position<E> p, PositionList<Position<E>> pos) throws InvalidPositionException
{
pos.addLast(p);
if (isExternal(p))
return;
Iterator<Position<E>> it = children(p).iterator();
while(it.hasNext())
preorderPosition(it.next(),pos);
}
protected void postorderPosition(Position<E> p, PositionList<Position<E>> pos) throws InvalidPositionException
{
if (isInternal(p))
{
Iterator<Position<E>> it = children(p).iterator();
while(it.hasNext())
postorderPosition(it.next(),pos);
}
pos.addLast(p);
}
public String printPreOrder()
{
String s ="[ ";
NodePositionList<Position<E>> lista = new NodePositionList<Position<E>>();
preorderPosition(root, lista);
Iterator<Position<E>> it = lista.iterator();
while(it.hasNext())
s += it.next().element() + " ";
return s + "]";
}
public String printPostOrder()
{
String s ="[ ";
NodePositionList<Position<E>> lista = new NodePositionList<Position<E>>();
postorderPosition(root, lista);
Iterator<Position<E>> it = lista.iterator();
while(it.hasNext())
s += it.next().element() + " ";
return s + "]";
}
//metodo personale che stampa un nodo e il suo eventuale sottoalbero
private String stampaNodo(Position<E> p)
{
String s = "";
for(int i=0; i<depth(p); i++)
s += " ";
s += p.element().toString();
TreeNode<E> n = (TreeNode<E>) checkPosition (p);
if (isExternal(n))
return s +="\n";
else
s += "->\n";
Iterator<Position<E>> it = n.getChildren().iterator();
while (it.hasNext())
{
s += stampaNodo(it.next());
}
return s;
}
public String toString()
{
if (isEmpty())
return "EmptyTree";
return stampaNodo((TreeNode<E>) root())+" size:"+size;
}
public Position<E> addChild(E e, Position<E> p)
{
TreeNode<E> padre = (TreeNode<E>) checkPosition(p);
TreeNode<E> newNode = new TreeNode<E>(e,padre,null);
if (isExternal(padre))
{
PositionList<Position<E>> figli = new NodePositionList<Position<E>>();
figli.addLast(newNode);
padre.setChildren(figli);
}
else
{
padre.getChildren().addLast(newNode);
}
size++;
return newNode;
}
public Position<E> removeChild(Position<E> p) throws InvalidPositionException
{
TreeNode<E> nodo = (TreeNode<E>) checkPosition(p);
if (isExternal(nodo))
throw new InvalidPositionException("This Node has no children to remove");
TreeNode<E> childToRemove = (TreeNode<E>) nodo.getChildren().first().element();
int numFigli = childCounter(childToRemove);
nodo.getChildren().remove(nodo.getChildren().first());
size -= numFigli;
if (nodo.getChildren().size() == 0)
nodo.setChildren(null);
return childToRemove;
}
//conta il numero di figli +1 di un nodo
protected int childCounter(Position<E>p)
{
TreeNode<E> nodo = (TreeNode<E>) checkPosition(p);
if (isExternal(nodo))
return 1;
else
{
int numFigli = 0;
for(Position<E> figlio : children(nodo))
{
numFigli += childCounter(figlio);
}
return 1 + numFigli;
}
}
public Position<E> addRoot(E e) throws NonEmptyTreeException
{
if (!isEmpty())
throw new NonEmptyTreeException("Root exists already!");
TreeNode<E> newRoot = new TreeNode<E>(e,null,null);
size = 1;
root = newRoot;
return root;
}
public int depth(Position<E> p) throws InvalidPositionException
{
/*//ricorsivo
if (isRoot(p)) return 0;
return 1+depth(parent(p));
*/
TreePosition<E> nodo = checkPosition(p);
if(isRoot(nodo))
return 0;
int depth=1;
TreePosition<E> par = nodo.getParent();
while(!isRoot(par))
{
par=par.getParent();
depth++;
}
return depth;
}
/*
//metodo ricorsivo
public int height(Position<E> p)
if (isExternal(p) return 0;
else
{
int max = 0;
for(Position<E> child : children(p))
{
max = Math.max(max, height(child));
}
return max+1;
}
*/
public int height()
{
return altezza(root());
}
protected int altezza(Position<E> p)
{
if (isExternal(p))
return 0;
else
{
int h = 0;
Iterator<Position<E>> children = children(p).iterator();
while(children.hasNext())
{
h = Math.max(h, altezza(children.next()));
}
return (1 + h);
}
}
}
//computa la somma degli elementi di un albero di interi
public static <E> int sum(LinkedTree<Integer> t)
{
if (t.isEmpty())
throw new EmptyTreeException();
return sum(t.root(),t);
}
/*
* postSum mi calcola la somma del nodo p + tutti i suoi figli
* */
public static int sum(Position<Integer> p, LinkedTree<Integer> t)
{
TreeNode<Integer> nodo = (TreeNode<Integer>) t.checkPosition(p);
int sum = 0;
if (t.isInternal(p))
for(Position<Integer> pos : nodo.getChildren())
sum += sum( pos,t);
return (sum + p.element());
}
//restituisce la Position dell'elemento x se è presente nell'albero t
//null altrimenti
public static <E> Position<E> findElt(Tree<E> t, E x)
{
if (t.isEmpty())
throw new EmptyTreeException();
return find(t,t.root(),x);
}
public static <E> Position<E> find(Tree<E> t, Position<E> p, E x)
{
if (p.element().equals(x))
return p;
else
{
if (t.isExternal(p))
return null;
for(Position<E> pos : t.children(p))
{
Position<E> ris = find(t,pos,x);
if (ris != null)
{
return ris;
}
}
return null;
}
}
public class LinkedBinaryTree<E> implements BinaryTree<E>
{
private int size;
private BTNode<E> root;
public LinkedBinaryTree()
{
root = null;
size = 0;
}
public LinkedBinaryTree(E e)
{
addRoot(e);
}
public int size()
{
return size;
}
public boolean isEmpty()
{
return (size==0);
}
public Iterable<Position<E>> positions()
{
PositionList<Position<E>> lista = new NodePositionList<Position<E>>();
if (size != 0)
preorderPositions(root(), lista);
return lista;
}
public E replace(Position<E> p, E e) throws InvalidPositionException
{
BTNode<E> nodo = (BTNode<E>) checkPosition(p);
E tmp = nodo.element();
nodo.setElement(e);
return tmp;
}
public Position<E> root() throws EmptyTreeException
{
if (isEmpty())
throw new EmptyTreeException();
return root;
}
public Position<E> parent(Position<E> p) throws InvalidPositionException, BoundaryViolationException
{
BTNode<E> tmp = (BTNode<E>) checkPosition(p);
if (tmp.equals(root))
throw new BoundaryViolationException("Root has no parent!");
return tmp.getParent();
}
public Iterable<Position<E>> children(Position<E> p) throws InvalidPositionException
{
BTNode<E> nodo = (BTNode<E>) checkPosition(p);
if(isExternal(nodo))
throw new InvalidPositionException("External nodes do not have children!");
PositionList<Position<E>> figli = new NodePositionList<Position<E>>();
figli.addFirst(nodo.getLeft());
figli.addLast(nodo.getRight());
return figli;
}
public boolean isInternal(Position<E> p) throws InvalidPositionException
{
return (!isExternal(p));
}
public boolean isExternal(Position<E> p) throws InvalidPositionException
{
BTNode<E> nodo = (BTNode<E>) checkPosition(p);
return (nodo.getLeft()==null && nodo.getRight()==null);
}
public boolean isRoot(Position<E> p) throws InvalidPositionException
{
BTNode<E> nodo = (BTNode<E>) checkPosition(p);
return (nodo.equals(root));
}
public Iterator<E> iterator()
{
Iterable<Position<E>> positions = positions();
PositionList<E> elements = new NodePositionList<E>();
Iterator<Position<E>> it = positions.iterator();
while(it.hasNext())
elements.addLast(it.next().element());
return elements.iterator();
}
public Position<E> left(Position<E> v) throws InvalidPositionException, BoundaryViolationException
{
BTPosition<E> nodo = checkPosition(v);
if(isExternal(v))
throw new InvalidPositionException("External nodes have no children");
if(!hasLeft(v))
throw new BoundaryViolationException("This node has not a left chlid");
return nodo.getLeft();
}
public Position<E> right(Position<E> v) throws InvalidPositionException, BoundaryViolationException
{
BTPosition<E> nodo = checkPosition(v);
if(isExternal(v))
throw new InvalidPositionException("External nodes have no children");
if(!hasRight(v))
throw new BoundaryViolationException("This node has not a right chlid");
return nodo.getRight();
}
public boolean hasLeft(Position<E> v) throws InvalidPositionException
{
BTPosition<E> nodo = checkPosition(v);
if(nodo.getLeft()==null)
return false;
else
return true;
}
public boolean hasRight(Position<E> v) throws InvalidPositionException
{
BTPosition<E> nodo = checkPosition(v);
if(nodo.getRight()==null)
return false;
else
return true;
}
protected void preorderPositions(Position<E> v, PositionList<Position<E>> pos) throws InvalidPositionException
{
pos.addLast(v);
if (hasLeft(v))
preorderPositions(left(v), pos);
if (hasRight(v))
preorderPositions(right(v), pos);
}
public BTPosition<E> checkPosition(Position<E> p)throws InvalidPositionException
{
if (p == null || !(p instanceof BTPosition))
throw new InvalidPositionException();
return (BTPosition<E>) p;
}
public BTPosition<E> addRoot(E e) throws NonEmptyTreeException
{
if(!isEmpty())
throw new NonEmptyTreeException("Root exists already");
BTNode<E>nodo = new BTNode<E>(e,null,null,null);
root = nodo;
size = 1;
return root;
}
//metodo personale che stampa un nodo e il suo eventuale sottoalbero
private String stampaNodo(Position<E> p)
{
String s = "";
for(int i=0; i<depth(p); i++)
s += " ";
s += p.element().toString();
BTNode<E> n = (BTNode<E>) checkPosition (p);
if (isExternal(n))
return s +="\n";
else
s += "->\n";
NodePositionList<Position<E>> figli = new NodePositionList<Position<E>>();
if (hasLeft(n))
figli.addFirst(n.getLeft());
if(hasRight(n))
figli.addLast(n.getRight());
Iterator<Position<E>> it = figli.iterator();
while (it.hasNext())
{
s += stampaNodo(it.next());
}
return s;
}
public String toString()
{
if (isEmpty())
return "EmptyTree";
return stampaNodo((BTNode<E>) root())+" size: "+size;
}
public int depth(Position<E> p) throws InvalidPositionException
{
BTPosition<E> nodo = checkPosition(p);
if(isRoot(nodo))
return 0;
int prof=1;
BTPosition<E> par = nodo.getParent();
while(!isRoot(par))
{
par=par.getParent();
prof++;
}
return prof;
}
/*
* Scrivere un metodo InsertLeft che prende in input
* un elemento e e una position p,
* inserisce il figlio sinistro di p con elemento
* e restituisce il riferimento alla nuova position inserita
* (se figlio sx esiste, lancia eccezione)*/
public Position<E> insertLeft(E e, Position<E> p)
{
BTNode<E> nodo = (BTNode<E>) checkPosition(p);
if (hasLeft(nodo))
throw new InvalidPositionException("The node already has a left child.");
BTNode<E> newNode = new BTNode<E>(e,nodo,null,null);
nodo.setLeft(newNode);
size++;
return newNode;
}
public Position<E> insertRight(E e, Position<E> p)
{
BTNode<E> nodo = (BTNode<E>) checkPosition(p);
if (hasRight(nodo))
throw new InvalidPositionException("The node already has a right child.");
BTNode<E> newNode = new BTNode<E>(e,nodo,null,null);
nodo.setRight(newNode);
size++;
return newNode;
}
public int height()
{
return altezza(root());
}
protected int altezza(Position<E> p)
{
if (isExternal(p))
{
return 0;
}
else
{
int h = 0;
BTNode<E> nodo = (BTNode<E>) checkPosition(p);
h = Math.max(altezza(nodo.getLeft()), altezza(nodo.getRight()));
return (1 + h);
}
}
//rimuove il figlio sinistro di p
public Position<E> removeLeft(Position<E> p) throws InvalidPositionException
{
BTNode<E> nodo = (BTNode<E>)checkPosition(p);
if (!hasLeft(nodo))
throw new InvalidPositionException("The node has not a left child.");
BTNode<E> childToRemove = (BTNode<E>) nodo.getLeft();
size -= childCounter(childToRemove);
nodo.setLeft(null);
return childToRemove;
}
//rimuove il figlio destro di p
public Position<E> removeRight(Position<E> p) throws InvalidPositionException
{
BTNode<E> nodo = (BTNode<E>)checkPosition(p);
if (!hasRight(nodo))
throw new InvalidPositionException("The node has not a right child.");
BTNode<E> childToRemove = (BTNode<E>) nodo.getRight();
size -= childCounter(childToRemove);
nodo.setLeft(null);
return childToRemove;
}
//conta il numero di figli +1 di un nodo
protected int childCounter(Position<E>p)
{
BTNode<E> nodo = (BTNode<E>) checkPosition(p);
if (isExternal(nodo))
return 1;
else
{
int numFigli = 0;
for(Position<E> figlio : children(nodo))
{
numFigli += childCounter(figlio);
}
return 1 + numFigli;
}
}
}
public static int sum(LinkedBinaryTree<Integer> t)
{
return sum(t.root(),t);
}
public static int sum(Position<Integer> p, LinkedBinaryTree<Integer> t)
{
int sum = p.element();
if (t.isInternal(p))
{
if (t.hasLeft(p))
sum += sum(t.left(p), t);
if (t.hasRight(p))
sum += sum(t.right(p), t);
}
return sum;
}
//verifica che l'ordine degli elementi dell'albero visitati inorder
//rispecchia l'ordine degli elementi della sequence
public static <E> boolean checkOrder(BinaryTree<E>t, Sequence<E> s)
{
if (t.isEmpty())
throw new EmptyTreeException();
if(s.isEmpty())
throw new EmptySequenceException();
if (t.size() != s.size())
throw new NotEnoughElements("Tree and Sequence are different");
return f(t,s,t.root());
}
public static <E> boolean f (BinaryTree<E>t, Sequence<E>s, Position<E> p)
{
if (t.hasLeft(p))
if (!f(t, s, t.left(p)))
return false;
if (!p.element().equals(s.first().element()))
return false;
s.removeFirst();
if (t.hasRight(p))
if (!f(t, s, t.right(p)))
return false;
return true;
}
Post
il tempo è sempre meno e la roba da implementare è sempre di più...
RispondiEliminastavo scrivendo la classe di test quando ho notato che il applico removeChild su un nodo interno giustamente mi cancella il nodo e tutto il suo sottoalbero ma la size non viene aggiornata correttamente:
RispondiEliminaPreorder Tree = [ 1 2 4 5 3 ] altezza: 2 size: 5
Preorder Tree = [ 1 3 ] altezza: 1 size: 4
l'albero dovrebbe essere:
.....1
..../.\
..2....3
./.\
4...5
allora c'è un doppio errore, perchè removechild(Position p) dovrebbe rimuvere soltanto il primo figlio di p. appena posso correggo, tnx Gianluca
RispondiEliminaahhh ecco sta parte mi mancava. E il sottoalbero dove lo attacca? al padre del nodo rimosso? in quale posizione rispetto ai suoi figli?
RispondiEliminano vabbè, cmq tutti i nodi che stanno eventualmente sotto al primo figlio della posizione p passata a removeChild vanno rimossi anch'essi. sono gli altri figli di p che non vanno cancellati
RispondiEliminaho corretto il metodo removeChild su indicazione di Gianluca:
RispondiEliminapublic Position removeChild(Position p) throws InvalidPositionException
{
TreeNode nodo = (TreeNode) checkPosition(p);
if (isExternal(nodo))
throw new InvalidPositionException("This Node has no children to remove");
TreeNode childToRemove = (TreeNode) nodo.getChildren().first().element();
if (isInternal(childToRemove))
{
for (Position child : children(childToRemove))
size--;
}
nodo.getChildren().remove(nodo.getChildren().first());
size--;
if (nodo.getChildren().size() == 0)
nodo.setChildren(null);
return childToRemove;
}
Ci siamo quasi ma ancora non va. siccone non ho niente da fare mi sono costruito quest'albero. la visita preorder è:
RispondiEliminaPreorder Tree = [ 1 2 5 10 6 7 3 4 8 9 ] altezza: 3 size: 10
........1
...../..|..\
..2.....3....4
/.|.\....../..\
5.6.7.....8....9
|
10
se faccio removeChild(root) mi cancella tutto il sottoalbero con radice 2. se rifaccio la visita:
Preorder Tree = [ 1 3 4 8 9 ] altezza: 2 size: 6
size 6 e non 5 perchè non ha contato 10 figlio di 5
ci vorrebbe qualcosa che conta tutti i nodi del sottoalbero e li sottrae a size
così dovrebbe andare: public Position removeChild(Position p) throws InvalidPositionException
RispondiElimina{
TreeNode nodo = (TreeNode) checkPosition(p);
if (isExternal(nodo))
throw new InvalidPositionException("This Node has no children to remove");
TreeNode childToRemove = (TreeNode) nodo.getChildren().first().element();
int numFigli = childCounter(childToRemove);
nodo.getChildren().remove(nodo.getChildren().first());
size -= numFigli;
if (nodo.getChildren().size() == 0)
nodo.setChildren(null);
return childToRemove;
}
//conta il numero di figli +1 di un nodo
public int childCounter(Positionp)
{
TreeNode nodo = (TreeNode) checkPosition(p);
if (isExternal(nodo))
return 1;
else
{
int numFigli = 0;
for(Position figlio : children(nodo))
{
numFigli += childCounter(figlio);
}
return 1 + numFigli;
}
}
ma come fai... funziona grazie!
RispondiEliminastavo già pensando di impiccarmi alla root di un Albero o di buttarmi giù dalLa Torre
Sull'onda dei suggerimenti di Gianluca ho modificato il metodo removeChild della classe LinkedTree, e ho aggiunto removeLeft e removeRight a LinkedBinaryTree.
RispondiEliminaHo poi aggiunto anche la visita postorder a LinkedTree e due metodi che stampano la sequenza degli elementi dell'albero in pre/post order.
problema con l'implementazione di LinkedBinaryTree:
RispondiEliminase faccio un setLeft o un setRight sulla radice di un nuovo albero, la size non viene incrementata, perchè aggiungo dei nodi all'albero tramite i metodi di BTNode anzicchè di LinkedBinaryTree! Inoltre in questo modo si corre il rischio di aggiungere dei nodi che non hanno i giusti collegamenti agli altri nodi dell'albero!
LinkedBinaryTree<Integer> a = new LinkedBinaryTree<Integer>();
BTNode<Integer> pos = (BTNode<Integer>) a.addRoot(100);
pos.setLeft(new BTNode<Integer>(90,pos,null,null));
pos.setRight(new BTNode<Integer>(80,pos,null,null));
any suggestions?
ho capito. io userei setLeft/Right solo nel costruire nodi poi userei i metodi insertLeft/Right oppure replace di linkedBinaryTree
RispondiElimina