Please help with these code activity Part 1 - Tree Height Add a method to the Li
ID: 3834249 • Letter: P
Question
Please help with these code activity
Part 1 - Tree Height
Add a method to the LinkedBinaryTree class that returns the height of a tree. Like many tree methods, this will require a fairly simple method in LinkedBinaryTree and another method in BTNode that does most of the work. First, check to see if the root is null. If it is, then the tree is obviously empty and return 0. If it is not null, return root.height().
Part 2 - Decision Tree
Create a decision tree for a topic of your choice. Examples: How to choose a college major? How to select a car? How to determine what to eat for dinner? You must have at least 14 questions that you could potentially ask the user. You will need to add a few missing methods to get your program to work correctly.
//*******************************************************************
// LinkedBinaryTree.java Java Foundations
//
// Implements a binary tree using a linked representation.
//*******************************************************************
import java.util.Iterator;
public class LinkedBinaryTree<T> implements BinaryTree<T>
{
protected BTNode<T> root;
//-----------------------------------------------------------------
// Creates an empty binary tree.
//-----------------------------------------------------------------
public LinkedBinaryTree()
{
root = null;
}
//-----------------------------------------------------------------
// Creates a binary tree with the specified element as its root.
//-----------------------------------------------------------------
public LinkedBinaryTree (T element)
{
root = new BTNode<T>(element);
}
//-----------------------------------------------------------------
// Creates a binary tree with the two specified subtrees.
//-----------------------------------------------------------------
public LinkedBinaryTree (T element, LinkedBinaryTree<T> left,
LinkedBinaryTree<T> right)
{
root = new BTNode<T>(element);
root.setLeft(left.root);
root.setRight(right.root);
}
//-----------------------------------------------------------------
// Returns the element stored in the root of the tree. Throws an
// EmptyCollectionException if the tree is empty.
//-----------------------------------------------------------------
public T getRootElement()
{
if (root == null)
throw new EmptyCollectionException ("Get root operation "
+ "failed. The tree is empty.");
return root.getElement();
}
//-----------------------------------------------------------------
// Returns the left subtree of the root of this tree.
//-----------------------------------------------------------------
public LinkedBinaryTree<T> getLeft()
{
if (root == null)
throw new EmptyCollectionException ("Get left operation "
+ "failed. The tree is empty.");
LinkedBinaryTree<T> result = new LinkedBinaryTree<T>();
result.root = root.getLeft();
return result;
}
//-----------------------------------------------------------------
// Returns the element in this binary tree that matches the
// specified target. Throws a ElementNotFoundException if the
// target is not found.
//-----------------------------------------------------------------
public T find (T target)
{
BTNode<T> node = null;
if (root != null)
node = root.find(target);
if (node == null)
throw new ElementNotFoundException("Find operation failed. "
+ "No such element in tree.");
return node.getElement();
}
//-----------------------------------------------------------------
// Returns the number of elements in this binary tree.
//-----------------------------------------------------------------
public int size()
{
int result = 0;
if (root != null)
result = root.count();
return result;
}
public Iterator<T> iterator() {
return new ArrayIterator<T>();
}
}
//********************************************************************
// EmptyCollectionException.java Java Foundations
//
// Represents the situation in which a collection is empty.
//********************************************************************
public class EmptyCollectionException extends RuntimeException
{
//------------------------------------------------------------------
// Sets up this exception with an appropriate message.
//------------------------------------------------------------------
public EmptyCollectionException (String message)
{
super (message);
}
}
//********************************************************************
// ElementNotFoundException.java Java Foundations
//
// Represents the situation in which a target element is not
// present in a collection
//********************************************************************
public class ElementNotFoundException extends RuntimeException
{
//------------------------------------------------------------------
// Sets up this exception with an appropriate message.
//------------------------------------------------------------------
public ElementNotFoundException (String message)
{
super (message);
}
}
//*******************************************************************
// BTNode.java Java Foundations
//
// Represents a node in a binary tree with a left and right child.
// Therefore this class also represents the root of a subtree.
//*******************************************************************
public class BTNode<T>
{
protected T element;
protected BTNode<T> left, right;
//-----------------------------------------------------------------
// Creates a new tree node with the specified data.
//-----------------------------------------------------------------
public BTNode (T element)
{
this.element = element;
left = right = null;
}
//-----------------------------------------------------------------
// Returns the element stored in this node.
//-----------------------------------------------------------------
public T getElement()
{
return element;
}
//-----------------------------------------------------------------
// Sets the element stored in this node.
//-----------------------------------------------------------------
public void setElement (T element)
{
this.element = element;
}
//*******************************************************************
// BinaryTree.java Java Foundations
//
// Defines the interface to a binary tree collection.
//*******************************************************************
import java.util.Iterator;
public interface BinaryTree<T> extends Iterable<T>
{
// Returns the element stored in the root of the tree.
public T getRootElement();
// Returns the left subtree of the root.
public BinaryTree<T> getLeft();
// Returns the right subtree of the root.
public BinaryTree<T> getRight();
// Returns true if the binary tree contains an element that
// matches the specified element and false otherwise.
public boolean contains (T target);
// Returns a reference to the element in the tree matching
// the specified target.
public T find (T target);
// Returns true if the binary tree contains no elements, and
// false otherwise.
public boolean isEmpty();
// Returns the number of elements in this binary tree.
public int size();
// Returns the string representation of the binary tree.
public String toString();
}
//********************************************************************
// BackPainExpert.java Java Foundations
//
// Represents a simple expert system for back pain diagnosis.
//********************************************************************
import java.util.Scanner;
public class BackPainExpert
{
private LinkedBinaryTree<String> tree;
//-----------------------------------------------------------------
// Sets up the diagnosis question tree.
//-----------------------------------------------------------------
public BackPainExpert()
{
String e1 = "Did the pain occur after a blow or jolt?";
String e2 = "Do you have a fever?";
String e3 = "Do you have difficulty controlling your arms or legs?";
String e4 = "Do you have persistent morning stiffness?";
String e5 = "Do you have a sore throat or runny nose?";
String e6 = "Do you have pain or numbness in one arm or leg?";
String e7 = "Emergency! You may have damaged your spinal cord.";
String e8 = "See doctor if pain persists.";
String e9 = "You may have an inflammation of the joints.";
String e10 = "See doctor to address symptoms.";
String e11 = "You may have a respiratory infection.";
String e12 = "You may have a sprain or strain.";
String e13 = "You may have a muscle or nerve injury.";
LinkedBinaryTree<String> n2, n3, n4, n5, n6, n7, n8, n9,
n10, n11, n12, n13;
n8 = new LinkedBinaryTree<String>(e8);
n9 = new LinkedBinaryTree<String>(e9);
n4 = new LinkedBinaryTree<String>(e4, n8, n9);
n10 = new LinkedBinaryTree<String>(e10);
n11 = new LinkedBinaryTree<String>(e11);
n5 = new LinkedBinaryTree<String>(e5, n10, n11);
n12 = new LinkedBinaryTree<String>(e12);
n13 = new LinkedBinaryTree<String>(e13);
n6 = new LinkedBinaryTree<String>(e6, n12, n13);
n7 = new LinkedBinaryTree<String>(e7);
n2 = new LinkedBinaryTree<String>(e2, n4, n5);
n3 = new LinkedBinaryTree<String>(e3, n6, n7);
tree = new LinkedBinaryTree<String>(e1, n2, n3);
}
//-----------------------------------------------------------------
// Follows the diagnosis tree based on user responses.
//-----------------------------------------------------------------
public void diagnose()
{
Scanner scan = new Scanner(System.in);
BinaryTree<String> current = tree;
System.out.println ("So, you're having back pain.");
while (current.size() > 1)
{
System.out.println (current.getRootElement());
if (scan.nextLine().equalsIgnoreCase("N"))
current = current.getLeft();
else
current = current.getRight();
}
System.out.println (current.getRootElement());
}
}
//********************************************************************
// BackPainAnalyzer.java Java Foundations
//
// Demonstrates the use of a binary tree.
//********************************************************************
public class BackPainAnalyzer
{
//-----------------------------------------------------------------
// Asks questions of the user to diagnose a medical problem.
//-----------------------------------------------------------------
public static void main (String[] args)
{
BackPainExpert expert = new BackPainExpert();
expert.diagnose();
}
}
//********************************************************************
// ArrayIterator.java Java Foundations
//
// Represents an iterator over the elements of a collection.
//********************************************************************
import java.util.*;
public class ArrayIterator<T> implements Iterator<T>
{
private int DEFAULT_CAPACITY = 10;
private int count; // the number of elements in the iterator
private int current; // the current position in the iteration
private T[] items; // the iterator's storage for elements
//-----------------------------------------------------------------
// Sets up this iterator.
//-----------------------------------------------------------------
public ArrayIterator()
{
items = (T[]) (new Object[DEFAULT_CAPACITY]);
count = 0;
current = 0;
}
//-----------------------------------------------------------------
// Adds the specified item to this iterator.
//-----------------------------------------------------------------
public void add (T item)
{
if (count == items.length)
expandCapacity();
items[count] = item;
count++;
}
//-----------------------------------------------------------------
// Returns true if this iterator has at least one more element to
// deliver in the iteration.
//-----------------------------------------------------------------
public boolean hasNext()
{
return (current < count);
}
//-----------------------------------------------------------------
// Returns the next element in the iteration. If there are no more
// elements in this iteration, a NoSuchElementException is thrown.
//-----------------------------------------------------------------
public T next()
{
if (! hasNext())
throw new NoSuchElementException();
current++;
return items[current - 1];
}
//-----------------------------------------------------------------
// The remove operation is not supported in this collection.
//-----------------------------------------------------------------
public void remove() throws UnsupportedOperationException
{
throw new UnsupportedOperationException();
}
//-----------------------------------------------------------------
// Exapands the capacity of the storage array
//-----------------------------------------------------------------
private void expandCapacity()
{
T[] larger = (T []) (new Object[items.length*2]);
int location = 0;
for (T element : items)
larger[location++] = element;
items = larger;
}
}
Explanation / Answer
#include <iostream>
#include <string>
#include <queue>
using namespace std;
// Linked list node
struct ListNode
{
int data;
ListNode* next;
};
// Binary tree node structure
struct BinaryTreeNode
{
int data;
BinaryTreeNode *left, *right;
};
// Function to insert a node at the beginning of the Linked List
void push(struct ListNode** head_ref, int new_data)
{
// allocate node and assign data
struct ListNode* new_node = new ListNode;
new_node->data = new_data;
// link the old list off the new node
new_node->next = (*head_ref);
// move the head to point to the new node
(*head_ref) = new_node;
}
// method to create a new binary tree node from the given data
BinaryTreeNode* newBinaryTreeNode(int data)
{
BinaryTreeNode *temp = new BinaryTreeNode;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// converts a given linked list representing a complete binary tree into the
// linked representation of binary tree.
void convertList2Binary(ListNode *head, BinaryTreeNode* &root)
{
// queue to store the parent nodes
queue<BinaryTreeNode *> q;
// Base Case
if (head == NULL)
{
root = NULL; // Note that root is passed by reference
return;
}
// 1.) The first node is always the root node, and add it to the queue
root = newBinaryTreeNode(head->data);
q.push(root);
// advance the pointer to the next node
head = head->next;
// until the end of linked list is reached, do the following steps
while (head)
{
// 2.a) take the parent node from the q and remove it from q
BinaryTreeNode* parent = q.front();
q.pop();
// 2.c) take next two nodes from the linked list. We will add
// them as children of the current parent node in step 2.b. Push them
// into the queue so that they will be parents to the future nodes
BinaryTreeNode *leftChild = NULL, *rightChild = NULL;
leftChild = newBinaryTreeNode(head->data);
q.push(leftChild);
head = head->next;
if (head)
{
rightChild = newBinaryTreeNode(head->data);
q.push(rightChild);
head = head->next;
}
// 2.b) assign the left and right children of parent
parent->left = leftChild;
parent->right = rightChild;
}
}
// Utility function to traverse the binary tree after conversion
void inorderTraversal(BinaryTreeNode* root)
{
if (root)
{
inorderTraversal( root->left );
cout << root->data << " ";
inorderTraversal( root->right );
}
}
// Driver program to test above functions
int main()
{
// create a linked list shown in above diagram
struct ListNode* head = NULL;
push(&head, 36); /* Last node of Linked List */
push(&head, 30);
push(&head, 25);
push(&head, 15);
push(&head, 12);
push(&head, 10); /* First node of Linked List */
BinaryTreeNode *root;
convertList2Binary(head, root);
cout << "Inorder Traversal of the constructed Binary Tree is: ";
inorderTraversal(root);
return 0;
}