Implement the find1() and find2() in Java. find1(k, n) // find value k in tree rooted at
Question:
Implement the find1() and find2() in Java.
find1(k, n) // find value k in tree rooted at Node n using a while loop
find2(k, n) // find value k in tree rooted at Node n using recursion
node_count(n) // counts the nodes in the tree
node_sum(n) // sums up all the values stored at the nodes
levels(n) // returns how many levels of nodes are in the tree.
// An empty tree has 0 levels.
//=============================================
// Client Program
//
class Node_03
{
public static void main (String[] args) throws java.lang.Exception
{
//--------------------------------------------
// Build the tree
//
Node node_1 = new Node(1);
Node node_4 = new Node(4);
Node node_6 = new Node(6);
Node node_3 = new Node(3, node_1, node_4);
Node node_9 = new Node(9, node_6, null);
Node node_5 = new Node(5, node_3, node_9);
// Test Cases
System.out.println("find1(1, node_5): " + find1(1, node_5));
System.out.println("find2(1, node_5): " + find2(1, node_5) + ' ');
System.out.println("find1(4, node_5): " + find1(4, node_5));
System.out.println("find2(4, node_5): " + find1(4, node_5) + ' ');
System.out.println("find1(6, node_5): " + find1(6, node_5));
System.out.println("find2(6, node_5): " + find2(6, node_5) + ' ');
System.out.println("find1(3, node_5): " + find1(3, node_5));
System.out.println("find2(3, node_5): " + find1(3, node_5) + ' ');
System.out.println("find1(9, node_5): " + find1(9, node_5));
System.out.println("find2(9, node_5): " + find2(9, node_5) + ' ');
System.out.println("find1(5, node_5): " + find1(5, node_5));
System.out.println("find2(5, node_5): " + find1(5, node_5) + ' ');
System.out.println("find1(2, node_5): " + find1(2, node_5));
System.out.println("find2(2, node_5): " + find2(2, node_5) + ' ');
System.out.println("find1(8, node_5): " + find1(8, node_5));
System.out.println("find2(8, node_5): " + find1(8, node_5) + ' ');
System.out.println("node_count(node_5): " + node_count(node_5));
System.out.println("node_sum(node_5): " + node_sum(node_5));
System.out.println("levels(node_5): " + levels(node_5) + ' ');
// Print serialized tree
//
serial(node_5); System.out.println();
}
//--------------------------------------------
// Sertialize tree
//
//------------------------------------
static void serial(Node n)
{
if (n == null) System.out.print('-');
else
{
System.out.print(n.data + " ");
serial(n.left); System.out.print(' ');
serial(n.right);
}
}
//------------------------------------
static void in_order(Node n)
{
if(n == null) return;
in_order(n.left);
System.out.print(n.data + " ");
in_order(n.right);
}
//------------------------------------
// Iterative find, use while loop
//
static Node find1(int value, Node n)
{
return null;
}
//------------------------------------
// Recursive find.
//
static Node find2(int value, Node n)
{
return null;
}
//------------------------------------
// Count how many Nodes in the tree.
//
static int node_count(Node n)
{
return 0;
}
//------------------------------------
// Dum up the values stored at the Nodes.
//
static int node_sum(Node n)
{
return 0;
}
//------------------------------------
// How many Nodes on a path from root
// to deepest Node in the tree.
//
static int levels(Node n)
{
return 0;
}
}
//=============================================
// Define Node class
//
class Node
{
int data;
Node left;
Node right;
Node(int d, Node l, Node r)
{
data = d;
left = l;
right = r;
}
Node(int d)
{
data = d;
left = null;
right = null;
}
}
/*
Serialized tree:
5 3 1 - - 4 - - 9 6 - - -
*/
Database management systems
ISBN: 978-0072465631
3rd edition
Authors: Raghu Ramakrishan, Johannes Gehrke, Scott Selikoff