In: Computer Science
Create a new project to build a Binary search tree, and do the following:
Create a TreeNode class,
Add the methods "Insert" to insert new nodes to the tree.
Add the method "inorder". Make the method to return a list of the node elements in inorder.
Implement the equals method in the BST. Two BST are equal if they contain the same elements.
In the main insert the elements of the tree, call the max method and print the max element, and Print the tree in "inorder" format.
Enter the following tree :
BinaryTree Test your program in case you have two identical trees and another time when you have different trees.
Java Please!
package DS;
// Class for BSTNode
class TNode
{
// To store key value
public int key;
// To point to left child
public TNode left;
// To point to right child
public TNode right;
// Default constructor to initialize instance
variables
public TNode(int key)
{
this.key = key;
left = null;
right = null;
key = 0;
}// End of default constructor
}// End of class BSTNode
// Defines class TreeNode for binary search tree
class TreeNode
{
// Declares root node
public TNode root;
// Default constructor to initialize root
public TreeNode()
{
this.root = null;
}// End of default constructor
// Method to insert key
public void insert(int key)
{
// Creates a node using
parameterized constructor
TNode newNode = new
TNode(key);
// Checks if root is null then this
node is the first node
if(root == null)
{
// root is
pointing to new node
root =
newNode;
return;
}// End of if condition
// Otherwise at least one node
available
// Declares current node points to
root
TNode currentNode = root;
// Declares parent node assigns
null
TNode parentNode = null;
// Loops till node inserted
while(true)
{
// Parent node
points to current node
parentNode =
currentNode;
// Checks if
parameter key is less than the current node key
if(key <
currentNode.key)
{
// Current node points to current node
left
currentNode = currentNode.left;
// Checks if current node is null
if(currentNode == null)
{
// Parent node left points to
new node
parentNode.left =
newNode;
return;
}// End of inner if condition
}// End of outer
if condition
// Otherwise
parameter key is greater than the current node key
else
{
// Current node points to current node
right
currentNode = currentNode.right;
// Checks if current node is null
if(currentNode == null)
{
// Parent node right points
to new node
parentNode.right =
newNode;
return;
}// End of inner if condition
}// End of outer
if condition
}// End of while
}// End of method
// Method to return biggest key
int maxValue()
{
// Stores the root key as the
maximum
int maximum = root.key;
// Loops till right child is not
null
while(root.right != null)
{
// Stores the
maximum as the current key
maximum =
root.right.key;
// Move to next
right child
root =
root.right;
} // End of while loop
// Returns the maximum
return maximum;
} // End of method
// Method for In Order traversal
public void inorder()
{
inorder(root);
}//End of method
// Method for In Order traversal recursively
private void inorder(TNode root)
{
// Checks if root is not null
if (root != null)
{
// Recursively calls the method with left child
inorder(root.left);
// Displays current node value
System.out.print(root.key + " ");
// Recursively calls the method with right child
inorder(root.right);
}// End of if condition
}// End of method
// Method to return true if both the BST is equals
// Otherwise returns false
boolean checkEqual(TNode one, TNode two)
{
// Checks if both the parameter node is null then
return true
if((one == null) && (two == null))
return true;
// Otherwise checks if first node is not null and
second node is null
// or first node is null and second node not null then
return false
else if((one != null && two == null)||(one ==
null && two != null))
return false;
// Otherwise checks if first node key is equals to
second node key
else if(one.key == two.key)
// Recursively calls the method
with left child for both
// and right
return checkEqual(one.left,
two.left) && checkEqual(one.right, two.right);
// Otherwise returns false
else
return false;
}// End of method
}// End of class TreeNode
// Driver class definition
public class BinaryTreeNode
{
// main method definition
public static void main(String []s)
{
// Creates TreeNode class temporary
object using default constructor
TreeNode t = new TreeNode();
// Creates TreeNode class object
one using default constructor
TreeNode one = new
TreeNode();
// Calls the method to insert to
tree one
one.insert(11);
one.insert(44);
one.insert(22);
one.insert(3);
one.insert(33);
// Creates TreeNode class object
two using default constructor
TreeNode two = new
TreeNode();
// Calls the method to insert to
tree two
two.insert(11);
two.insert(44);
two.insert(22);
two.insert(3);
two.insert(33);
// Creates TreeNode class object
three using default constructor
TreeNode three = new
TreeNode();
// Calls the method to insert to
tree three
three.insert(9);
three.insert(1);
three.insert(7);
three.insert(90);
three.insert(50);
// Calls the method to perform in
order traversal for 3 trees
System.out.println("\n\n
**************Inorder Traversal BST One **************");
one.inorder();
System.out.println("\n\n
**************Inorder Traversal BST Two **************");
two.inorder();
System.out.println("\n\n
**************Inorder Traversal BST Three **************");
three.inorder();
// Calls the method to check
equality of one and two BST
if(t.checkEqual(one.root,
two.root))
System.out.print("\n\n Both BST One and BST Two are equal.");
else
System.out.print("\n\n BST One and BST Two are equal.");
// Calls the method to check
equality of one and three BST
if(t.checkEqual(one.root,
three.root))
System.out.print("\n\n Both BST One and BST Three are
equal.");
else
System.out.print("\n\n BST One and BST Three are not
equal.");
// Calls the method to display the
maximum value of each BST
System.out.println("\n\n Maximum
value in BST One: " + one.maxValue());
System.out.println("\n Maximum
value in BST Two: " + two.maxValue());
System.out.println("\n Maximum
value in BST Three: " + three.maxValue());
}// End of main method
}// End of driver class
Sample Output:
**************Inorder Traversal BST One **************
3 11 22 33 44
**************Inorder Traversal BST Two **************
3 11 22 33 44
**************Inorder Traversal BST Three **************
1 7 9 50 90
Both BST One and BST Two are equal.
BST One and BST Three are not equal.
Maximum value in BST One: 44
Maximum value in BST Two: 44
Maximum value in BST Three: 90