Wednesday, April 19, 2017

java binary tree







// ref: http://javabeat.net/binary-search-tree-traversal-java/

package binarysearchtreedemo;

public class BinarySearchTreeDemo {

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();

        int[] nums = {40, 25, 78, 10, 32};
//        int[] nums = {10, 20, 0, 5, 15};
        for (int i : nums) {
            bst.insert(i);
        }
//        System.out.println("Inorder traversal");
//        bst.printInorder();

        System.out.println("Preorder Traversal");
        bst.printPreorder();

//        System.out.println("Postorder Traversal");
//        bst.printPostorder();
//
//        System.out.println("The minimum value in the BST: " + bst.findMinimum());
//        System.out.println("The maximum value in the BST: " + bst.findMaximum());
        System.out.println("Print Same Level Node: "  );
        bst.printSameLevelNode(3);
   
    }
}



------------------------------------------------------------------------------------------------------------------


/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package binarysearchtreedemo;

import java.util.ArrayList;

/**
 * Represents the Binary Search Tree.
 */
public class BinarySearchTree {

    //Refrence for the root of the tree.
    public Node root;

    ArrayList<Integer> nodeAl = new ArrayList<Integer>();

    int level_no, count = 0,tree_height, desired_level;

    public BinarySearchTree insert(int value) {
        Node node = new Node(value);

        if (root == null) {
            root = node;
            return this;
        }

        insertRec(root, node);
        return this;
    }

    private void insertRec(Node latestRoot, Node node) {

        if (latestRoot.value > node.value) {

            if (latestRoot.left == null) {
                latestRoot.left = node;
//        return;
            } else {
                insertRec(latestRoot.left, node);
            }
        } else {
            if (latestRoot.right == null) {
                latestRoot.right = node;
//        return;
            } else {
                insertRec(latestRoot.right, node);
            }
        }
    }

    public void printSameLevelNode(int _desired_level) {

//        level_no = _level_no;
//        printSameLevelNode(root);
//        nodeAl.clear();
        tree_height = height(root);
        desired_level = _desired_level;
        System.out.println("height=" + tree_height);

        int i;
//        for (i = 1; i <= h; i++) {
//            printGivenLevel(root, i);
//        }
        if(desired_level>tree_height || desired_level<=0)
        {
            System.out.print("Highest level number can be 1 to "+tree_height);
        }
        else
        {
            printGivenLevel(root, desired_level);
            
        }
        System.out.print("\n");
        

    }

    /* Print nodes at the given level */
    void printGivenLevel(Node root, int level) {
        if (root == null) {
            
            return;
        }
        if (level == 1) {
            
            count++;
            if(count==1)
            {
                System.out.print("Level "+ desired_level+" Nodes are: ");
            }
            
            System.out.print(root.value + " ");
        } else if (level > 1) {
            printGivenLevel(root.left, level - 1);
            printGivenLevel(root.right, level - 1);
        }
    }

    int height(Node root) {
        if (root == null) {
            return 0;
        } else {
            /* compute  height of each subtree */
            int lheight = height(root.left);
            int rheight = height(root.right);

            /* use the larger one */
            if (lheight > rheight) {
                return (lheight + 1);
            } else {
                return (rheight + 1);
            }
        }
    }

    public void printSameLevelNode(Node _currRoot) {

        Node currNode = _currRoot;

        System.out.println("parent Node=" + currNode.value + " left child=" + currNode.left.value + " right child=" + currNode.right.value);

        for (int i = 0; i <= level_no; i++) {
            if (i == level_no) {
//                nodeAl.add(currNode.left.value);
//                nodeAl.add(currNode.right.value);
            } else {
                printSameLevelNode(currNode.left);
                printSameLevelNode(currNode.right);
            }
        }

//        System.out.println("nodeAl=" + nodeAl);
    }

    /**
     * Returns the minimum value in the Binary Search Tree.
     */
    public int findMinimum() {
        if (root == null) {
            return 0;
        }
        Node currNode = root;
        while (currNode.left != null) {
            currNode = currNode.left;
            System.out.println("currNode=" + currNode.value);
        }
        return currNode.value;
    }

    /**
     * Returns the maximum value in the Binary Search Tree
     */
    public int findMaximum() {
        if (root == null) {
            return 0;
        }

        Node currNode = root;
        while (currNode.right != null) {
            currNode = currNode.right;
        }
        return currNode.value;
    }

    /**
     * Printing the contents of the tree in an inorder way.
     */
    public void printInorder() {
        printInOrderRec(root);
        System.out.println("");
    }

    /**
     * Helper method to recursively print the contents in an inorder way
     */
    private void printInOrderRec(Node currRoot) {
        if (currRoot == null) {
            return;
        }
        printInOrderRec(currRoot.left);
        System.out.print(currRoot.value + ", ");
        printInOrderRec(currRoot.right);
    }

    /**
     * Printing the contents of the tree in a Preorder way.
     */
    public void printPreorder() {
        printPreOrderRec(root);
        System.out.println("");
    }

    /**
     * Helper method to recursively print the contents in a Preorder way
     */
    private void printPreOrderRec(Node currRoot) {
        if (currRoot == null) {
            return;
        }
        System.out.print(currRoot.value + ", ");
        printPreOrderRec(currRoot.left);
        printPreOrderRec(currRoot.right);
    }

    /**
     * Printing the contents of the tree in a Postorder way.
     */
    public void printPostorder() {
        printPostOrderRec(root);
        System.out.println("");
    }

    /**
     * Helper method to recursively print the contents in a Postorder way
     */
    private void printPostOrderRec(Node currRoot) {
        if (currRoot == null) {
            return;
        }
        printPostOrderRec(currRoot.left);
        printPostOrderRec(currRoot.right);
        System.out.print(currRoot.value + ", ");

    }
}


------------------------------------------------------------------------------------------------------------------


package binarysearchtreedemo;


public class Node {
  //The value present in the node.
  public int value;

  //The reference to the left subtree.
  public Node left;

  //The reference to the right subtree.
  public Node right;

  public Node(int value) {
    this.value = value;
  }

}

------------------------------------------------------------------------------------------------------------------

output:

Preorder Traversal
40, 25, 10, 32, 78,
Print Same Level Node:
height=3
Level 3 Nodes are: 10 32