// *******************************************************************
// Trees1.java By: AimanHanna (C) 1993 - 2017
// This program introduces the Binary Trees data structure. A binary tree
// starts at a top node, referred to as root, which can fork left and right.
// There are no loops in a binary tree. Following any of the branches will
// eventually reach an end. The end nodes are referred to as leafs.
// In general, trees are one of the most important and useful data structures.
// Generally, data can be stored in a tree in any way. This program however
// stores data in the tree following a rule called "Binary Search Tree Storage Rule".
// This rule states the following:
// 1) All the values in the left subtree are less than the value in the root,
// 2) All values in the right subtree are greater than or equal to the value in the root,
// 3) The above rules apply recursively to each subtree in both sides.
//
// Key Points:
// 1) Binary Trees.
// 2) The Binary Search Tree Storage Rule.
// *******************************************************************
import java.util.Scanner;
// A tree class that stores integer values
class IntTree
{
// Inner Node class. Each node has an an integer value and two links to left and right branches (or null).
class Node
{
privateintval;
private Node leftNext;
private Node rightNext;
// Default constructors
public Node()
{
val = 0;
leftNext = null;
rightNext = null;
}
// Parameterized constructor
public Node(int v, Node lf, Node rt)
{
val = v;
leftNext = lf;
rightNext = rt;
}
publicvoid setVal(int v)
{
val = v;
}
publicvoid setLeftNext(Node lf)
{
leftNext = lf;
}
publicvoid setRightNext(Node rt)
{
rightNext = rt;
}
publicint getVal()
{
returnval;
}
public Node getLeftNext()
{
returnleftNext;
}
public Node getRightNext()
{
returnrightNext;
}
}// End of Node Class
private Node root;
// Constructor
public IntTree()
{
root = null;
}
// A method that inserts a node at the proper location into the tree
publicvoid add(int v)
{
root = insert(v, root);
}
// A recursive method that searches the tree for a given value and returns
// a pointer to the first found node that has this value or null if value is not found
privatestatic Node find(int v, Node subTreeRt)
{
if(subTreeRt == null)
returnnull;
elseif(subTreeRt.val == v)
{
return subTreeRt;
}
elseif(subTreeRt.val > v)
{
returnfind(v, subTreeRt.leftNext); // Search the left side of the tree
}
else
returnfind(v, subTreeRt.rightNext); // Search the right side of the tree
}
// A method that indicates whether or not a value is in the tree
publicboolean contains(int v)
{
if(find(v, root) != null)
returntrue;
else
returnfalse;
}
// A private recursive method that performs the actual addition of a node in the tree
private Node insert(int v, Node subTreeRt)
{
if(subTreeRt == null)
returnnew Node(v, null, null);
elseif(subTreeRt.val > v)
{
// Node to be inserted in the left side of the tree
subTreeRt.leftNext = insert(v, subTreeRt.leftNext);
}
else
{
// Node to be inserted in the right side of the tree
subTreeRt.rightNext = insert(v, subTreeRt.rightNext);
}
return subTreeRt;
}
// A method that displays the content of the tree using Inorder Processing
publicvoid showTreesContentsInorder()
{
showSubTreesContentsInorder(root);
}
privatestaticvoid showSubTreesContentsInorder(Node subTreeRt)
{
if (subTreeRt != null)
{
showSubTreesContentsInorder(subTreeRt.leftNext);// Show left side of the tree
System.out.print(subTreeRt.val + " ");// Show the value at root
showSubTreesContentsInorder(subTreeRt.rightNext);// Show right side of the tree
}
}
// A method that displays the content of the tree using Preorder Processing
// The arrows are placed to provide more visualization of the tree
publicvoid showTreesContentsPreorder()
{
showSubTreesContentsPreorder(root);
}
privatestaticvoid showSubTreesContentsPreorder(Node subTreeRt)
{
if (subTreeRt != null)
{
System.out.println("at root, value is " + subTreeRt.val);
System.out.println(subTreeRt.val + " ");// Show the value at root
System.out.println("<---- " );
showSubTreesContentsPreorder(subTreeRt.leftNext);// Show left side of the tree
System.out.println("----> " );
showSubTreesContentsPreorder(subTreeRt.rightNext);// Show right side of the tree
}
}
}
publicclass Trees1{
publicstaticvoid main(String[] args)
{
Scanner kb = new Scanner(System.in);
int x;
IntTree tr1 = new IntTree();
System.out.print("Enter the values you wish to store in the tree or \"-1\" to terminate: ");
x = kb.nextInt();
while (x !=-1)
{
tr1.add(x);
x = kb.nextInt();
}
System.out.println("\nDisplaying contents of tree using Inorder Processing");
System.out.println("======");
tr1.showTreesContentsInorder();
System.out.println("\n\nDisplaying contents of tree using Preorder Processing");
System.out.println("======");
tr1.showTreesContentsPreorder();
System.out.println("\n\nThanks for using our Tree Data Structure. Goodbye.");
}
}
/* The Output
Enter the values you wish to store in the tree or "-1" to terminate: 100 4 52 49 232 522 83 17 99 25 76 32 78 43 -1
Displaying contents of tree using Inorder Processing
======
4 17 25 32 43 49 52 76 78 83 99 100 232 522
Displaying contents of tree using Preorder Processing
======
at root, value is 100
100
<----
at root, value is 4
4
<----
---->
at root, value is 52
52
<----
at root, value is 49
49
<----
at root, value is 17
17
<----
---->
at root, value is 25
25
<----
---->
at root, value is 32
32
<----
---->
at root, value is 43
43
<----
---->
---->
---->
at root, value is 83
83
<----
at root, value is 76
76
<----
---->
at root, value is 78
78
<----
---->
---->
at root, value is 99
99
<----
---->
---->
at root, value is 232
232
<----
---->
at root, value is 522
522
<----
---->
Thanks for using our Tree Data Structure. Goodbye.
*/