The main goal is to implement two recursive methods, each is built to manipulate
ID: 3802381 • Letter: T
Question
The main goal is to implement two recursive methods, each is built to manipulate linked data structures. To host these methods you also have to define two utterly simplified node classes.
1.) Add a class named BinaryNode to the project. This class supports the linked representation of binary trees. However, for the BinaryNode class Generic implementation not needed, the nodes will store integer values The standard methods will not be needed in this exercise except the constructor
2.) Add a toString( ) method to the BinaryNode class. The method creates a String description of the tree.
3.) Add a method named BSTFactory () to the class. This method is static returns, for any given N, the root reference of a full binary search tree of depth N such that the nodes store the integers 1, 2, 3, …, 2 N+1 – 1 must be recursive. More precisely double recursive, the method calls itself with decreased depth with respect to the left link and right link of the caller node takes parameter(s), depth is naturally the control parameter, and it may be helpful to add another parameter, the “top” number stored in the root of the current sub-tree may also benefit of a private helper method which computes the power of 2 of a given exponent Hints: Construct and draw the BST solutions on a piece of paper for depth values N = 0, 1, 2, 3. Note that the solution is always unique, there is only one way to fill in the numbers Observe the values in the root nodes, deduct and verify a rule for the root values Observe the values in the children of the root, deduct and verify a rule how to express the children values in terms of the root value. The rules you found will help to parametrize correct the BSTFactory( ) method in the recursive algorithm
4.) Add another class SimpleNode to you project (this class is independent of the previous BinaryNode class). SimpleNode is a (non-generic) representative of any Node class . As in the above case, none of the standard methods but the constructor will be used in this demonstration. You will need however the toString( ) method and the getTail( ) method from your previous assignments. The type of the data stored in the nodes has no relevance to this application, choose String values at will
5.) Add a method named reverse () to the class. This method is static takes the head of the original list for parameter given the head reference of a linked list, returns the head reference of the linked list in reversed order; that is the method has to reverse all the links of the original list, the original tail will be the head and the original head will be the new tail. Note that the nodes are not cloned and the data stored in the nodes are not moved or changed must be recursive, applied on shorter and shorter lists Choose carefully the base case(s)
6.) Add an Application class to the project to test and demonstrate the work of the methods. Print all output to the console
7.) Test BSTFactory for all values N = 0, 1, 2, 3, 4, 5 8.) Test reverse( ) for lists of length 0, 1, 5 and 10 9.) Use the toString() method of your classes to create output messages. Design your display such that it gives clear explanation about the output data.
Explanation / Answer
class LinkedList {
static Node head1, head2;
static class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
/*function to get the intersection point of two linked
lists head1 and head2 */
int getNode() {
int c1 = getCount(head1);
int c2 = getCount(head2);
int d;
if (c1 > c2) {
d = c1 - c2;
return _getIntesectionNode(d, head1, head2);
} else {
d = c2 - c1;
return _getIntesectionNode(d, head2, head1);
}
}
/* function to get the intersection point of two linked
lists head1 and head2 where head1 has d more nodes than
head2 */
int _getIntesectionNode(int d, Node node1, Node node2) {
int i;
Node current1 = node1;
Node current2 = node2;
for (i = 0; i < d; i++) {
if (current1 == null) {
return -1;
}
current1 = current1.next;
}
while (current1 != null && current2 != null) {
if (current1.data == current2.data) {
return current1.data;
}
current1 = current1.next;
current2 = current2.next;
}
return -1;
}
/*Takes head pointer of the linked list and
returns the count of nodes in the list */
int getCount(Node node) {
Node current = node;
int count = 0;
while (current != null) {
count++;
current = current.next;
}
return count;
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
// creating first linked list
list.head1 = new Node(3);
list.head1.next = new Node(6);
list.head1.next.next = new Node(15);
list.head1.next.next.next = new Node(15);
list.head1.next.next.next.next = new Node(30);
// creating second linked list
list.head2 = new Node(10);
list.head2.next = new Node(15);
list.head2.next.next = new Node(30);
System.out.println("The node of intersection is " + list.getNode()); }
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.