==============================================
JAVA CODE FOR CREATING A BINARY TREE
==============================================
package com.sachi.test.tree;
import java.util.List;
public class Node {
private Node leftNode;
private Node rightNode;
private String nodeData;
public Node(String nodeData){
this.nodeData=nodeData;
this.leftNode=null;
this.rightNode=null;
}
public Node(String nodeData, Node leftNode, Node rightNode){
this.nodeData=nodeData;
this.leftNode=leftNode;
this.rightNode=rightNode;
}
public boolean isInnerNode(){
return leftNode!=null || rightNode!=null;
}
public boolean isLeaf(){
return leftNode==null && rightNode==null;
}
public boolean hasLeft() {
return leftNode != null;
}
public boolean hasRight() {
return rightNode != null;
}
public Node getLeftNode(){
return leftNode;
}
public Node getRightNode(){
return rightNode;
}
public String getNodeData(){
return nodeData;
}
public void setNodeData(String data){
nodeData=data;
}
/**
* RETURNS THE SIZE OF THE TREE
*
*/
public int getSize(){
int num=1;
if (hasLeft()){
num+=leftNode.getSize();
}
if (hasRight()){
num+=rightNode.getSize();
}
return num;
}
/**
* RETURNS THE HEIGHT OF THE TREE>
*
*/
public int treeHeight(){
if (isLeaf()){return 0;}
else
{
int h=0;
if (hasLeft()){
h=Math.max(h,leftNode.treeHeight());
}
if(hasRight()){
h=Math.max(h,rightNode.treeHeight());
}
return h+1;
}
}
/**
* RETURNS THE HEIGHT OF THE LEFT SUBTREE>
*
*/
public int leftTreeHeight(){
if (leftNode==null){return 0;}
else
{
int h=0;
if (hasLeft()){
h=Math.max(h,leftNode.leftTreeHeight());
}
return h+1;
}
}
/**
* RETURNS THE HEIGHT OF THE RIGHT SUBTREE>
*
*/
public int rightTreeHeight(){
if (rightNode==null){return 0;}
else
{
int h=0;
if(hasRight()){
h=Math.max(h,rightNode.rightTreeHeight());
}
return h+1;
}
}
public String toString() {
return toStringHelper("");
}
private String toStringHelper(String indent) {
String ret = "";
if (hasRight())
ret += rightNode.toStringHelper(indent+" ");
ret += indent + nodeData + "\n";
if (hasLeft())
ret += leftNode.toStringHelper(indent+" ");
return ret;
}
/**
* CHECK THE LEAVES LEVEL ARE SAME OR NOT
* @return true/false
*/
public boolean checktheLevelofLeavesSame(){
System.out.println("Height of right sub tree : "+ rightTreeHeight());
System.out.println("Height of left sub tree : "+ leftTreeHeight());
if (rightTreeHeight()==leftTreeHeight()){
return true;
}else{
return false;
}
}
/**
* @param dataList
* PREORDER TRAVERSAL OF THE TREE
*/
public void preorderTraversal(List<String> dataList){
dataList.add(nodeData);
if(this.hasLeft()){
leftNode.preorderTraversal(dataList);
}
if(this.hasRight()){
rightNode.preorderTraversal(dataList);
}
}
/**
* @param dataList
* POSTORDER TRAVERSAL OF THE TREE
*/
public void postorderTraversal(List<String> dataList){
if(this.hasLeft()){
leftNode.postorderTraversal(dataList);
}
if(this.hasRight()){
rightNode.postorderTraversal(dataList);
}
dataList.add(nodeData);
}
/**
* @param dataList
* INORDER TRAVERSAL OF THE TREE
*/
public void inorderTraversal(List<String> dataList){
if(this.hasLeft()){
leftNode.inorderTraversal(dataList);
}
dataList.add(nodeData);
if(this.hasRight()){
rightNode.inorderTraversal(dataList);
}
}
public static void main(String [] args) {
Node leftChild=new Node("domestic",new Node("dog"), new Node("cat"));
Node rightChild=new Node("wild",new Node("lion"), new Node("tiger"));
Node tree=new Node("animals",leftChild, rightChild);
System.out.println("Tree is : "+ tree );
System.out.println("Size of tree = " + tree.getSize());
System.out.println("Height of tree = " + tree.treeHeight());
System.out.println("checking if leaves are at same level = " + tree.checktheLevelofLeavesSame());
}
}
No comments:
Post a Comment