Complete Tree program:
import java.util.Stack;
/**
*
*/
/**
* @author Abhinaw.Tripathi
*
*/
class Node
{
public int iData;
public double dData;
public Node leftChild;
public Node rightChild;
public void displayNode()
{
System.out.println('{');
System.out.println(iData);
System.out.println(", ");
System.out.println(dData);
System.out.println("} ");
}
class Tree
{
private Node root;
public Tree()
{
root=null;
}
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,int dd)
{
Node newNode=new Node();
newNode.iData=id;
newNode.dData=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;
}
}
}
}
}
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.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;
successor.leftChild=current.leftChild;
}
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(successor!=delNode.rightChild)
{
successorParent.leftChild=successor.rightChild;
successor.rightChild=delNode.rightChild;
}
return successor;
}
public void traverse(int traverseType)
{
switch (traverseType)
{
case 1:System.out.println("\n Preorer traversal: ");
preOder(root);
break;
case 2:System.out.println("\n InOrder traversal: ");
inOrder(root);
break;
case 3:System.out.println("\n PostOrder traversal: ");
postOrder(root);
break;
default:
break;
}
}
private void postOrder(Node localRoot)
{
if(localRoot!=null)
{
postOrder(localRoot.leftChild);
postOrder(localRoot.rightChild);
System.out.println(localRoot.iData + " ");
}
}
private void inOrder(Node localRoot)
{
if(localRoot!=null)
{
inOrder(localRoot.leftChild);
System.out.println(localRoot.iData + " ");
inOrder(localRoot.rightChild);
}
}
private void preOder(Node localRoot)
{
if(localRoot!=null)
{
System.out.println(localRoot.iData + " ");
preOder(localRoot.leftChild);
preOder(localRoot.rightChild);
}
}
public void displayTree()
{
Stack globalStack=new Stack();
globalStack.push(root);
int nBlank=32;
boolean isRowEmpty=false;
System.out.println("....................................................");
while(isRowEmpty==true)
{
Stack localStack=new Stack();
isRowEmpty=false;
for(int i=0;i<nBlank;i++)
System.out.println(' ');
while(globalStack.isEmpty()==false)
{
Node temp=(Node)globalStack.pop();
if(temp!=null)
{
System.out.println(temp.iData);
localStack.push(temp.leftChild);
localStack.push(temp.rightChild);
if(temp.leftChild!=null || temp.rightChild!=null)
isRowEmpty=false;
}
else
{
System.out.println("----");
localStack.push(null);
localStack.push(null);
}
for(int i=0;i<nBlank*2*2;i++)
System.out.println(' ');
}
System.out.println(" ");
nBlank/=2;
while(localStack.isEmpty()==false)
globalStack.push(localStack.pop());
}
System.out.println(" ");
}
}
}
public class BinaryTreeApp {
/**
* @param args
*/
public static void main(String[] args) {
Tree theTree=new Tree();
theTree.insert(50,1.5);
theTree.insert(25,1.2);
theTree.insert(75,1.7);
theTree.displayTree();
// do somthing like this
}
}
import java.util.Stack;
/**
*
*/
/**
* @author Abhinaw.Tripathi
*
*/
class Node
{
public int iData;
public double dData;
public Node leftChild;
public Node rightChild;
public void displayNode()
{
System.out.println('{');
System.out.println(iData);
System.out.println(", ");
System.out.println(dData);
System.out.println("} ");
}
class Tree
{
private Node root;
public Tree()
{
root=null;
}
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,int dd)
{
Node newNode=new Node();
newNode.iData=id;
newNode.dData=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;
}
}
}
}
}
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.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;
successor.leftChild=current.leftChild;
}
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(successor!=delNode.rightChild)
{
successorParent.leftChild=successor.rightChild;
successor.rightChild=delNode.rightChild;
}
return successor;
}
public void traverse(int traverseType)
{
switch (traverseType)
{
case 1:System.out.println("\n Preorer traversal: ");
preOder(root);
break;
case 2:System.out.println("\n InOrder traversal: ");
inOrder(root);
break;
case 3:System.out.println("\n PostOrder traversal: ");
postOrder(root);
break;
default:
break;
}
}
private void postOrder(Node localRoot)
{
if(localRoot!=null)
{
postOrder(localRoot.leftChild);
postOrder(localRoot.rightChild);
System.out.println(localRoot.iData + " ");
}
}
private void inOrder(Node localRoot)
{
if(localRoot!=null)
{
inOrder(localRoot.leftChild);
System.out.println(localRoot.iData + " ");
inOrder(localRoot.rightChild);
}
}
private void preOder(Node localRoot)
{
if(localRoot!=null)
{
System.out.println(localRoot.iData + " ");
preOder(localRoot.leftChild);
preOder(localRoot.rightChild);
}
}
public void displayTree()
{
Stack globalStack=new Stack();
globalStack.push(root);
int nBlank=32;
boolean isRowEmpty=false;
System.out.println("....................................................");
while(isRowEmpty==true)
{
Stack localStack=new Stack();
isRowEmpty=false;
for(int i=0;i<nBlank;i++)
System.out.println(' ');
while(globalStack.isEmpty()==false)
{
Node temp=(Node)globalStack.pop();
if(temp!=null)
{
System.out.println(temp.iData);
localStack.push(temp.leftChild);
localStack.push(temp.rightChild);
if(temp.leftChild!=null || temp.rightChild!=null)
isRowEmpty=false;
}
else
{
System.out.println("----");
localStack.push(null);
localStack.push(null);
}
for(int i=0;i<nBlank*2*2;i++)
System.out.println(' ');
}
System.out.println(" ");
nBlank/=2;
while(localStack.isEmpty()==false)
globalStack.push(localStack.pop());
}
System.out.println(" ");
}
}
}
public class BinaryTreeApp {
/**
* @param args
*/
public static void main(String[] args) {
Tree theTree=new Tree();
theTree.insert(50,1.5);
theTree.insert(25,1.2);
theTree.insert(75,1.7);
theTree.displayTree();
// do somthing like this
}
}
No comments:
Post a Comment