Read : Binary Search Tree (bst)- Breadth first and depth first search, insert and delete in java
Binary Tree
Breadth first search or level order of binary tree in java
visits all the nodes of a same level left to right before going to the next level.
50 17 72 12 23 54 76 9 14 19 67
Full program/ example >
import java.io.IOException;
import java.util.Stack;
class Node {
public int value;
public Node leftChild;
public Node rightChild;
@Overridepublic String toString() {//return "[value=" + value + ", left=" + leftChild + ", right=" + rightChild + "]";return "[value=" + value +"]";}
}
class Tree {
public Node root; // first node of tree
// -------------------------------------------------------------
public Tree() // constructor
{
root = null;
} // no nodes in tree yet
// -------------------------------------------------------------
public void insert(int id) {
Node newNode = new Node(); // make new node
newNode.value = id; // insert data
if (root == null) // no node in root
root = newNode;
else // root occupied
{
Node current = root; // start at root
Node parent;
while (true) // (exits internally)
{
parent = current;
if (id < current.value) // go left?
{
current = current.leftChild;
if (current == null) // if end of the line,
{ // insert on left
parent.leftChild = newNode;
return;
}
} // end if go left
else // or go right?
{
current = current.rightChild;
if (current == null) // if end of the line
{ // insert on right
parent.rightChild = newNode;
return;
}
} // end else go right
} // end while
} // end else not root
} // end insert()
// -------------------------------------------------------------
// Breadth-First Search //Display output in tree form
public void displayTree() {
Stack parentStack = new Stack();
parentStack.push(root);
int nBlanks = 32;
boolean isRowEmpty = false;
while (isRowEmpty == false) {
Stack childStack = new Stack();
isRowEmpty = true;
for (int j = 0; j < nBlanks; j++)
System.out.print(' ');
while (parentStack.isEmpty() == false) {
Node currentNode = (Node) parentStack.pop();
if (currentNode != null) {
System.out.print(currentNode.value);
childStack.push(currentNode.leftChild);
childStack.push(currentNode.rightChild);
if (currentNode.leftChild != null || currentNode.rightChild != null)
isRowEmpty = false;
} else {
System.out.print("--");
childStack.push(null);
childStack.push(null);
}
for (int j = 0; j < nBlanks * 2 - 2; j++)
System.out.print(' ');
} // end while parentStack not empty
System.out.println();
nBlanks /= 2;
while (childStack.isEmpty() == false)
parentStack.push(childStack.pop());
} // end while isRowEmpty is false
}
// Breadth-First Search // Simply- without formatting
public void displayTree2() {
Stack parentStack = new Stack();
parentStack.push(root);
boolean noChild = false;
while (noChild == false) {
Stack childStack = new Stack();
noChild = true; // Initially true, we will iterate till its false
while (parentStack.isEmpty() == false) {
Node currentNode = (Node) parentStack.pop();
if (currentNode != null) {
System.out.print(currentNode.value + " ");
childStack.push(currentNode.leftChild);
childStack.push(currentNode.rightChild);
// Find any any child exists or not OR
//If any of the left or right child has value - we will set noChild as false, so that we won't break while loop
if (currentNode.leftChild != null || currentNode.rightChild != null)
noChild = false; // It was set true at start of while loop and will
// remain true if no child exists
}
}
while (childStack.isEmpty() == false)
parentStack.push(childStack.pop());
} // end while isRowEmpty is false
System.out.println();
}
}
public class BinaryTree_BinarySearchTree_ExampleJava {
public static void main(String[] args) throws IOException {
// Insert
Tree theTree = new Tree();
theTree.insert(50);
theTree.insert(17);
theTree.insert(72);
theTree.insert(12);
theTree.insert(23);
theTree.insert(54);
theTree.insert(76);
theTree.insert(9);
theTree.insert(14);
theTree.insert(19);
theTree.insert(67);
// Breadth-First Search //Display output in tree form
System.out.println("Breadth-First Search //Display output in tree form");
theTree.displayTree();
// Breadth-First Search // Simply- without formatting
System.out.println("\nBreadth-First Search");
theTree.displayTree2();
}
}
//output
/*
Breadth-First Search //Display output in tree form
50
17 72
12 23 54 76
9 14 19 -- -- 67 -- --
Breadth-First Search
50 17 72 12 23 54 76 9 14 19 67
*/
|
Having any doubt? or you liked the tutorial! Please comment in below section.
Please express your love by liking JavaMadeSoEasy.com (JMSE) on facebook, following on google+ or Twitter.
RELATED LINKS>