gurusamy
BAN USERpackage alg.tree.binary;
import java.util.ArrayList;
import java.util.LinkedList;
public class FullBinaryTree {
public static void main(String[] args) {
int tree[] = {1, 0, 1, -1, -1, 0, 0};
Node root = Node.constructTree(tree);
ArrayList<Integer> pre = new ArrayList<Integer>();
BinaryTreeTraversal.preorder(pre, root);
System.out.println("PreOrder: " + pre);
boolean isFull = isFullBinaryTree(root);
System.out.println("Full: " + isFull);
Node n = constructFullBinaryTree(pre);
Node.printTree(n, 1, "**");
}
private static Node constructFullBinaryTree(ArrayList<Integer> pre) {
Node root = new Node(pre.get(0));
LinkedList<String> childTypes = new LinkedList<String>();
LinkedList<Node> nodes = new LinkedList<Node>();
nodes.add(root);
childTypes.add("L");
childTypes.add("R");
for (int i = 1; i < pre.size(); i++) {
//Node.printTree(root, 0, "*");
//System.out.println("Nodes: "+nodes);
//System.out.println("ChildTypes: "+childTypes);
Node node = new Node(pre.get(i));
String childType = childTypes.pop();
if (childType.equals("L")) {
nodes.peek().left = node;
} else {
nodes.poll().right = node;
}
if (node.data == 1) {
nodes.push(node);
childTypes.offer("L");
childTypes.offer("R");
}
}
//System.out.println("FinalNodes: "+nodes);
//System.out.println("FinalChildTypes: "+childTypes);
return root;
}
private static boolean isFullBinaryTree(Node root) {
if ((root.left == null && root.right == null)) return true;
if ((root.left != null && root.right != null)) {
return isFullBinaryTree(root.left) && isFullBinaryTree(root.right);
} else {
return false;
}
}
}
//General Node
package alg.tree.binary;
import java.util.ArrayList;
import java.util.concurrent.atomic.AtomicInteger;
public class Node {
int id;
int data;
Node left, right;
boolean reverse;
public Node(int data, Node left, Node right) {
super();
this.data = data;
this.left = left;
this.right = right;
}
public Node(int data) {
super();
this.data = data;
}
@Override
public String toString() {
return "<Node " + id + ":" + data + "> ";
}
public static void printTree(Node root, int height, String type) {
if (root == null) return;
for (int i = 0; i < height; i++) {
System.out.print("\t");
}
// System.out.print("|\t");
System.out.println(type+"-"+root.id + ":" + root.data);
printTree(root.left, height + 1, "L");
printTree(root.right, height + 1, "R");
}
private static void constructTree(int[] tree, int idx, Node node, AtomicInteger count) {
if (2 * idx + 1 < tree.length) {
if (tree[2 * idx + 1] != -1) {
node.left = new Node(tree[2 * idx + 1]);
node.left.id = count.incrementAndGet();
constructTree(tree, 2 * idx + 1, node.left, count);
}
}
if (2 * idx + 2 < tree.length) {
if (tree[2 * idx + 2] != -1) {
node.right = new Node(tree[2 * idx + 2]);
node.right.id = count.incrementAndGet();
constructTree(tree, 2 * idx + 2, node.right, count);
}
}
}
public static Node constructTree(int[] tree) {
Node root = new Node(tree[0]);
root.id = 0;
Node.constructTree(tree, 0, root, new AtomicInteger(0));
printTree(root, 0, "*");
return root;
}
public static int countNodes(Node root) {
if (root == null) return 0;
return 1 + countNodes(root.left) + countNodes(root.right);
}
public static ArrayList<Node> findPath(Node root, int i, ArrayList<Node> path) {
if (root == null) return null;
if (root.id == i) {
return (ArrayList<Node>) path.clone();
} else {
path.add(root);
ArrayList<Node> p = findPath(root.left, i, path);
if (p == null) {
p = findPath(root.right, i, path);
}
path.remove(root);
return p;
}
}
}
{
- gurusamy June 18, 2011private static void alternateLevelOrder(ArrayList<Integer> list, Node root) {
LinkedList<Node> queue = new LinkedList<Node>();
LinkedList<Node> queue2 = new LinkedList<Node>();
boolean reverse = true;
queue2.add(root);
while ((queue.size() + queue2.size()) > 0) {
if (queue.size() > 0) {
Node start = queue.poll();
if (start.left != null) {
// list.add(start.left.data);
queue2.add(start.left);
}
if (start.right != null) {
// list.add(start.right.data);
queue2.add(start.right);
}
} else {
queue.addAll(queue2);
if (reverse) {
Collections.reverse(queue2);
} else {
}
for (Node node : queue2) {
list.add(node.data);
}
queue2.clear();
reverse = !reverse;
}
}
}
}