import java.util.LinkedList;
public class BST {
static class Node {
private int value;
private Node leftChild;
private Node rightChild;
public Node(int value) {
this.value = value;
}
}
static enum ChildType {
LEFT, RIGHT, ROOT
}
private Node root;
public BST(int[] sortedArray) {
int lo = 0;
int hi = sortedArray.length;
int mid = (lo + hi) / 2;
root = new Node(sortedArray[mid]);
build(root, ChildType.ROOT, sortedArray, lo, hi);
}
private void build(Node node, ChildType type, int[] array, int lo, int hi) {
if (lo >= hi) {
return;
}
int mid = (lo + hi) / 2;
Node n = node;
if (type == ChildType.LEFT) {
node.leftChild = new Node(array[mid]);
n = node.leftChild;
} else if (type == ChildType.RIGHT) {
node.rightChild = new Node(array[mid]);
n = node.rightChild;
}
build(n, ChildType.LEFT, array, lo, mid);
build(n, ChildType.RIGHT, array, mid+1, hi);
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
LinkedList<Node> nodes = new LinkedList<>();
nodes.add(root);
while (!nodes.isEmpty()) {
Node n = nodes.removeFirst();
if (n.leftChild != null) {
sb.append(n.leftChild.value + " -- left --> " + n.value + " \n");
nodes.add(n.leftChild);
}
if (n.rightChild != null) {
sb.append(n.rightChild.value + " -- right --> " + n.value + " \n");
nodes.add(n.rightChild);
}
}
return sb.toString();
}
public static void main(String[] args) {
int[] sortedArray = new int[7];
for (int i = 0; i < sortedArray.length; i++) {
sortedArray[i] = i;
}
BST bst = new BST(sortedArray);
System.out.println(bst);
}
}
Wednesday, December 5, 2012
How to Create a Binary Search Tree from a Sorted Array
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment