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
