import java.util.*;
public class boldTree {
private int number;
private boolean isBold;
private List children;
private boolean keep;
public boldTree(int n, boolean bold) {
number = n;
isBold = bold;
keep = true;
children = new ArrayList();
}
public static boldTree copy(boldTree node){
return new boldTree(node.number, node.isBold);
}
public void addChild(boldTree node) {
children.add(node);
}
public List getChildren() {
return children;
}
public boldTree getChild(int n) {
for (boldTree c : this.children) {
if (c.number == n)
return c;
}
return null;
}
public void removeChild(boldTree c) {
if (this.children.contains(c))
this.children.remove(c);
}
//the best, bottom-up by copying
public static boldTree boldSubTreeCopy(boldTree root) {
if (root == null)
return null;
boldTree tmp = copy(root);
for(boldTree c : root.getChildren()){
if(boldSubTreeCopy(c) != null){
tmp.addChild(c);
}
}
if(tmp.isBold ||tmp.getChildren().size() != 0)
return tmp;
else
return null;
}
// use flag, bottom-up
public static boldTree boldSubTree(boldTree root) {
if (root == null)
return null;
root.keep = root.isBold;
for(boldTree c : root.getChildren()){
if(boldSubTree(c).keep)
root.keep = true;
}
return root;
}
public static void show2(boldTree n) {
if (n == null){
System.out.println("no tree");
return;
}
Queue currentLevel = new LinkedList();
Queue nextLevel = new LinkedList();
currentLevel.add(n);
System.out.println(n.number + " ");
while (!currentLevel.isEmpty()) {
boldTree r = currentLevel.poll();
for (boldTree c : r.getChildren()) {
if (c.keep) {
if (c.isBold)
System.out.print(c.number + "(b) ");
else
System.out.print(c.number + " ");
}
nextLevel.add(c);
}
if (currentLevel.isEmpty()) {
currentLevel.addAll( nextLevel);
nextLevel.clear();
System.out.println();
}
}
}
// track non-bold node and remove, top-down approach
public static boldTree extractBoldSubTree(boldTree root) {
if (root == null) {
return null;
}
Queue currentLevel = new LinkedList();
Queue nextLevel = new LinkedList();
HashMap> nonBoldNodeList = new HashMap>();
currentLevel.add(root);
while (!currentLevel.isEmpty()) {
boldTree r = currentLevel.poll();
for (boldTree c : r.getChildren()) {
if (!hasBoldChild(c)) {
if (!nonBoldNodeList.containsKey(r))
nonBoldNodeList.put(r, new ArrayList());
nonBoldNodeList.get(r).add(c);
} else {
nextLevel.add(c);
}
}
if (currentLevel.isEmpty()) {
currentLevel.addAll(nextLevel);
nextLevel.clear();
for (boldTree k : nonBoldNodeList.keySet()) {
for (boldTree c : nonBoldNodeList.get(k)) {
k.removeChild(c);
}
}
nonBoldNodeList.clear();
}
}
return root;
}
public static boolean hasBoldChild(boldTree n) {
if(n == null)
return false;
for(boldTree c : n.getChildren()){
if(hasBoldChild(c))
return true;
}
return n.isBold;
}
public static void show(boldTree n) {
if (n == null){
System.out.println("no tree");
return;
}
Queue currentLevel = new LinkedList();
Queue nextLevel = new LinkedList();
currentLevel.add(n);
System.out.println(n.number + " ");
while (!currentLevel.isEmpty()) {
boldTree r = currentLevel.poll();
for (boldTree c : r.getChildren()) {
if (c.isBold)
System.out.print(c.number + "(b) ");
else
System.out.print(c.number + " ");
nextLevel.add(c);
}
if (currentLevel.isEmpty()) {
currentLevel = nextLevel;
nextLevel = new LinkedList();
System.out.println();
}
}
}
public static void main(String[] args) {
boldTree root = new boldTree(1, false);
boldTree c2 = new boldTree(2, false);
boldTree c3 = new boldTree(3, false);
boldTree c4 = new boldTree(4, true);
root.addChild(c2);
root.addChild(c3);
root.addChild(c4);
boldTree c22 = new boldTree(22, true);
c2.addChild(c22);
boldTree c31 = new boldTree(31, false);
boldTree c32 = new boldTree(32, true);
c3.addChild(c31);
c3.addChild(c32);
boldTree c41 = new boldTree(41, false);
boldTree c42 = new boldTree(42, false);
boldTree c43 = new boldTree(43, false);
c4.addChild(c41);
c4.addChild(c42);
c4.addChild(c43);
boldTree c221 = new boldTree(221, false);
c22.addChild(c221);
boldTree c311 = new boldTree(311, true);
c31.addChild(c311);
boldTree c421 = new boldTree(421, true);
boldTree c431 = new boldTree(431, false);
c42.addChild(c421);
c43.addChild(c431);
boldTree root2 = root;
System.out.println("source tree");
show(root);
System.out.println("bold tree");
boldTree newRoot = extractBoldSubTree(root);
show(newRoot);
// need a flag to keep if the node should be included.
System.out.println("another way to extract bold tree");
boldTree newRoot2 = boldSubTree(root2);
show2(newRoot2);
System.out.println("another way to extract bold tree by copying: ");
boldTree newRoot3 = boldSubTreeCopy(root2);
show(newRoot3);
}
}