// 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
------------------------------------------------------------------------------------------------------------------
output:
Preorder Traversal
40, 25, 10, 32, 78,
Print Same Level Node:
height=3
Level 3 Nodes are: 10 32
No comments:
Post a Comment