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