Program of Binary Tree in Java

Binary tree is a data structure who hava at most 2 children often called the right node and the left node.Each node (excluding a root) in a tree is associated by a coordinated edge from precisely one other node. This node is known as a parent. Then again, every node can be associated with discretionary number of node, called children. Node without any children are called leaves, or . Nodes which are not leaves are called inside nodes. Nodes with a similar parent are called kin.

There are three .java classes for the binary tree data structure:

  1. Node.
  2. Runner.
  3. Tree

Code is successfully compiled on the Eclipse compiler

Node:

package binary_tree;

public class Node {

int iData;
double fData;
Node leftChild;
Node rightChild;

public void displayNode()
{

}
}

Runner:

package binary_tree;

public class Runner {

public static void main(String args[])
{

Tree t = new Tree();

t.insert(63, 0.55);
t.insert(27, 0.33);
t.insert(80, 0.66);
t.insert(13, 0.22);
t.insert(51, 0.44);
t.insert(70, 0.44);
t.insert(92, 0.44);
t.insert(26, 0.44);
t.insert(33, 0.44);
t.insert(58, 0.44);
t.insert(82, 0.44);
t.insert(57, 0.44);
t.insert(60, 0.44);

System.out.print(“inOrder: “); t.inOrder();
System.out.println();
System.out.print(“preOrder: “); t.preOrder();
System.out.println();
System.out.print(“postOrder: “); t.postOrder();
System.out.println();
}

}
// 13 26 27 33 51 57 58 60 63 70 80 82 92 inorder
//

Tree:

package binary_tree;

public class Tree {

private Node root;

public Node find(int key)
{
Node current = root;

while(current.iData != key)
{
if(key< current.iData)
{
current = current.leftChild;
}
else
{
current = current.rightChild;
}
if(current == null)
return null;
}
return current;
}
public void insert(int id, double dd)
{
Node newNode = new Node();
newNode.iData = id;
newNode.fData = dd;

if(root == null)
{
root = newNode;
}
else
{
Node current = root;
Node parent;

while(true)
{
parent = current;
if(id < current.iData)
{
current = current.leftChild;
if(current == null)
{
parent.leftChild = newNode;
return;
}
}
else
{
current = current.rightChild;
if(current == null)
{
parent.rightChild = newNode;
return;
}
}
}
}
}
private void postOrder(Node localRoot)
{
if(localRoot != null)
{
inOrder(localRoot.leftChild);
inOrder(localRoot.rightChild);
System.out.print(localRoot.iData + ” “);
}
}
private void preOrder(Node localRoot)
{
if(localRoot != null)
{
System.out.print(localRoot.iData + ” “);
inOrder(localRoot.leftChild);
inOrder(localRoot.rightChild);
}
}
private void inOrder(Node localRoot)
{
if(localRoot != null)
{
inOrder(localRoot.leftChild);
System.out.print(localRoot.iData + ” “);
inOrder(localRoot.rightChild);
}
}
public void inOrder()
{
inOrder(root);
}
public void postOrder()
{
postOrder(root);
}
public void preOrder()
{
preOrder(root);
}
public Node minimum()
{
Node current,last;
last = current = root;

while(current != null)
{
last = current;
current = current.leftChild;
}
return last;
}
// delete a node with no children

public boolean delete(int key)
{
Node current = root;
Node parent = root;
boolean isLeftChild = true;

while(current.iData != key)
{
parent = current;
if(key < current.iData)
{
isLeftChild = true;
current = current.leftChild;
}
else
{
isLeftChild = false;
current = current.rightChild;
}
if(current == null)
{
return false;
}
}
if(current.leftChild == null && current.rightChild == null)
{
if(current == root)
{
root = null;
}
else if(isLeftChild)
{
parent.leftChild = null;
}
else
{
parent.rightChild = null;
}
}
else if(current.rightChild == null)
{
if(current == root)
{
root = current.leftChild;
}
else if(isLeftChild)
{
parent.leftChild = current.leftChild;
}
else
{
parent.rightChild = current.leftChild;
}
}
else if(current.leftChild == null)
{
if(current == root)
{
root = current.rightChild;
}
else if(isLeftChild)
{
parent.leftChild = current.rightChild;
}
else
{
parent.rightChild = current.rightChild;
}
}
else
{
Node successor = getSuccessor(current);

if(current == root)
{
root = successor;
}
else if(isLeftChild)
{
parent.leftChild = successor;
}
else
{
parent.rightChild = successor;
}
}
return true;
}
private Node getSuccessor(Node delNode)
{
Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.rightChild;

while(current != null)
{
successorParent = successor;
successor = current;
current = current.leftChild;
}
if(delNode.rightChild != successor)
{
successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
}
return successor;
}
}

Comment if you have any confusion or query thanks !!!

Add a Comment

Your email address will not be published. Required fields are marked *