import java.util.ArrayList;
import java.util.LinkedList;
public class BST_Impl {
BST_Node root=null;
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = { 10, 4, 0, 34, 23, -2,-2, 5, 12, 9, 15, };
BST_Impl tree = new BST_Impl();
for (int i = 0; i < arr.length; i++) {
tree.insert(new BST_Node(arr[i]));
}
System.out.println("Level order traversal:");
tree.levelOrderTraversal(tree.root);
}
public void levelOrderTraversal(BST_Node root) {
ArrayList> orderList=new ArrayList>();
ArrayList orderValues=new ArrayList();
LinkedList curr=new LinkedList(); //maintain a queue of all nodes on current level.
LinkedList next=new LinkedList(); /*maintain a queue of all the nodes which are available in the next level of the current level, ie child of current level node */
curr.add(root);
while(!curr.isEmpty()) {
BST_Node node=(BST_Node)curr.remove();
if(node.left!=null) {
next.add(node.left);
}
if(node.right!=null) {
next.add(node.right);
}
orderValues.add(node.value);
if(curr.isEmpty()) {
orderList.add(orderValues);
curr=next;
next=new LinkedList();
orderValues=new ArrayList();
}
}
System.out.println(orderList);
}
public void insert(BST_Node node) {
BST_Node temp=root;
if(root==null) {
root=node;
}else {
while(temp!=null) { //inserting as leave of a node
if(temp.value>node.value) {
if(temp.left==null) {
temp.left=node;
break;
}
temp=temp.left;
}else if(temp.value
if(temp.right==null) {
temp.right=node;
break;
}
temp=temp.right;
}else {
System.out.println("cannot enter equal number:"+temp.value);
break;
}
}
}
}
}
class BST_Node{
BST_Node left;
BST_Node right;
int value;
public BST_Node( int value) {
this.value=value;
}
}
import java.util.LinkedList;
public class BST_Impl {
BST_Node root=null;
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = { 10, 4, 0, 34, 23, -2,-2, 5, 12, 9, 15, };
BST_Impl tree = new BST_Impl();
for (int i = 0; i < arr.length; i++) {
tree.insert(new BST_Node(arr[i]));
}
System.out.println("Level order traversal:");
tree.levelOrderTraversal(tree.root);
}
public void levelOrderTraversal(BST_Node root) {
ArrayList
ArrayList
LinkedList
LinkedList
curr.add(root);
while(!curr.isEmpty()) {
BST_Node node=(BST_Node)curr.remove();
if(node.left!=null) {
next.add(node.left);
}
if(node.right!=null) {
next.add(node.right);
}
orderValues.add(node.value);
if(curr.isEmpty()) {
orderList.add(orderValues);
curr=next;
next=new LinkedList
orderValues=new ArrayList
}
}
System.out.println(orderList);
}
public void insert(BST_Node node) {
BST_Node temp=root;
if(root==null) {
root=node;
}else {
while(temp!=null) { //inserting as leave of a node
if(temp.value>node.value) {
if(temp.left==null) {
temp.left=node;
break;
}
temp=temp.left;
}else if(temp.value
if(temp.right==null) {
temp.right=node;
break;
}
temp=temp.right;
}else {
System.out.println("cannot enter equal number:"+temp.value);
break;
}
}
}
}
}
class BST_Node{
BST_Node left;
BST_Node right;
int value;
public BST_Node( int value) {
this.value=value;
}
}
No comments:
Post a Comment