Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * Binary Search Tree
- */
- public class BST {
- //attributes
- private Object item; //data container
- private BST left,right,parent;
- //constructor
- public BST(Object item) { this.item = item; }
- public BST() {}
- //setters
- public void setItem(Object item) { this.item = item; }
- public void setLeft(BST left) { this.left = left; }
- public void setRight(BST right) { this.right = right; }
- public void setParent(BST parent) { this.parent = parent; }
- //setters
- public Object getItem() { return item; }
- public BST getLeft() { return left; }
- public BST getRight() { return right; }
- public BST getParent() { return parent; }
- public BST addNode(Object item, BST root) {
- //create a new node(tree)
- BST node = new BST(item);
- if(root == null) root = node;
- else {
- Comparable c = (Comparable)root.getItem();
- if(c.compareTo(item) > 0) {
- root.left = addNode(item, root.getLeft()); //recursive call
- }
- if(c.compareTo(item) <= 0) {
- root.right = addNode(item, root.getRight());
- }
- }
- return root; //return the updated root
- }
- public void preOder(BST root) {
- if(root != null) {
- System.out.print(root.getItem()); //Logical marker
- preOder(root.getLeft());
- preOder(root.getRight());
- }
- }
- public void inOder(BST root) {
- if(root != null) {
- inOder(root.getLeft());
- System.out.print(root.getItem()); //Logical marker
- inOder(root.getRight());
- }
- }
- public void postOder(BST root) {
- if(root != null) {
- postOder(root.getLeft());
- postOder(root.getRight());
- System.out.print(root.getItem()); //Logical marker
- }
- }
- public void levelOder(BST root) {
- java.util.Queue<BST> q = new java.util.LinkedList<BST>();
- q.add(root);
- while(!q.isEmpty()) {
- BST temp = q.poll();
- System.out.print(temp.getItem());
- if(temp.getLeft() != null) {
- q.add(temp.getLeft());
- }
- if(temp.getRight() != null) {
- q.add(temp.getRight());
- }
- }
- }
- static public void main(String... args) {
- BST bst = null;
- bst = new BST().addNode(new String("6"), bst);
- bst = new BST().addNode(new String("4"), bst);
- bst = new BST().addNode(new String("9"), bst);
- bst = new BST().addNode(new String("7"), bst);
- bst = new BST().addNode(new String("2"), bst);
- bst = new BST().addNode(new String("8"), bst);
- bst = new BST().addNode(new String("5"), bst);
- bst = new BST().addNode(new String("0"), bst);
- bst = new BST().addNode(new String("3"), bst);
- bst = new BST().addNode(new String("1"), bst);
- bst = new BST().addNode(new String("6"), bst);
- System.out.print("Pre-Order: ");
- new BST().preOder(bst);
- System.out.print("\nIn-Order: ");
- new BST().inOder(bst);
- System.out.print("\nPost-Order: ");
- new BST().postOder(bst);
- System.out.print("\nLevel-Order: ");
- new BST().levelOder(bst);
- }
- }//End of the class
Advertisement
Add Comment
Please, Sign In to add comment