Java Code Snippets: BSTNode and Graph Algorithms
private BSTNode removeLeaves (BSTNode curr){
if (curr == null)
return null;
if (curr.left == null && curr.right == null){
treeSize–;
return null;
}
curr.left = removeLeaves (curr.left);
curr.right = removeLeaves(curr.right);
return curr;
}
public String getEdges (boolean asc){
TreeMap ,>> m = null;
if (asc == true)
m = new TreeMap ,>> (new Less <><>());
else
m = new TreeMap ,>> (new Greater ());
for (Entry e1: adjacencyMap.entrySet()){
for (Entry e2: e1.getValue().entrySet()){
if (!m.containsKey(e2.getValue()))
m.put(e2.getValue(), new TreeSet ());
String cadena = e1.getKey()+”–>” + e2.getKey()+”=”+e2.getValue();
m.get(e2.getValue()).add(cadena);
}
}
return m.toString();
}
,>,>
private BSTNode removeMin (BSTNode curr){
if (curr == null)
return null;
if (curr.left == null){
treeSize–:
return curr.right;
}
curr.left = removeMin (curr.left);
return curr;
}
public String getThingsV2 (Vertex w, Comparator comp){
TreeSet set;
double suma = 0;
if (comp == null)
set = new TreeSet ();
else
set = new TreeSet (comp);
for (Entry ,>> e: adjacencyMap.entrySet()){
if (e.getValue().containsKey (w)){
set.add (e.getKey());
suma = suma + e.getValue().get (w);
}
}
return set.toString() + “–>” + suma;
}
public TreeSet getNeighbors (Vertex v){
if (! adjacencyMap.containsKey (v)) { return null; }
TreeSet set = new TreeSet (adjacencyMap.get(v).keySet());
return set; }
,>
public ArrayList toArrayDFRecursive (Vertex start){
ArrayList lista = new ArrayList ();
TreeMap visited = new TreeMap ();
for (Vertex v: adjacencyMap.keySet()){
visited.put (v, false);
}
toArrayDFAux (start, lista, visited);
return lista;
}
private void toArrayDFAux (Vertex current, ArrayList lista, TreeMap visited){
visited.put (current, true);
lista.add (current);
for (Entry e: adjacencyMap.get (current).entrySet()){
if (! visited.get(e.getKey()))
toArrayDFAux (e.getKey(), lista, visited);
}
}
public int pathHeight (T item){
return pathHeight (root, item, 1);
}
private int pathHeight (BSTNode current, T item, int height){
if (current == null){ return -1; }
if (current.nodeValue.compareTo(item) == 0)
return height;
if (current.nodeValue.compareTo(item) < 0)
return pathHeight (current.right, item, height+1);
return pathHeight (current.left, item, height+1);
}
,double>,>,>,>
public ArrayList path (T item){
ArrayList lista = new ArrayList ();
path (lista, root, item);
return lista;
}
private void path (ArrayList lista, BSTNode current, T item){
if (current == null)
return;
lista.add(current.nodeValue);
if (current.nodeValue.equals(item))
return;
if (current.nodeValue.compareTo(item) < 0)
path (lista, current.right, item);
else
path (lista, current.left, item);
}
public int count02 (){
return count02 (root);
}
private int count02 (BSTNode current){
if (current == null)
return 0;
if (current.left == null && current.right == null)
return 1;
int n1 = count02(current.left);
int n2 = count02(current.right);
if (current.left != null && current.right != null)
return 1 + n1 + n2;
return n1 +n2;
}