ToDo: Write a definition of the method nodeCount that returns the number of node
ID: 3539087 • Letter: T
Question
ToDo:
Write a definition of the method nodeCount that returns the number of nodes in a binary tree. Add this method to the class BinaryTree and test this method.
Write a definition of the method leavesCount that takes as a parameter a reference of the root node of a binary tree and returns the number of leaves in a binary tree. Add this method to the class BinaryTree and test this method.
Write a definition of the method singleP that returns the number of nodes in a binary tree that have only one child. Add this method to the class BinaryTree and test this method.
//Data: 65 78 34 22 40 89 50 75 80 100 90 97 45 120 105 -999
import java.util.*;
public class Driver
{
static Scanner console = new Scanner(System.in);
public static void main(String[] args)
{
BinarySearchTree<Integer> treeRoot =
new BinarySearchTree<Integer>();
Integer num;
System.out.println("Enter integers ending with -999");
num = console.nextInt();
while (num != -999)
{
treeRoot.insert(num);
num = console.nextInt();
}
System.out.print("treeRoot nodes in inorder: ");
treeRoot.inorderTraversal();
System.out.println();
System.out.print("Number of Nodes: " + treeRoot.treeNodeCount());
System.out.println();
System.out.print("Number of Leaves: "
+ treeRoot.treeLeavesCount());
System.out.println();
System.out.println("Tree Height: "
+ treeRoot.treeHeight());
System.out.println("Number of single Parents: "
+ treeRoot.singleParent());
}
}
_______________________________________________________________________________________
public class BinarySearchTree<T> extends BinaryTree<T>
{
//Default constructor
//Postcondition: root = null;
public BinarySearchTree()
{
super();
}
//Method to determine whether searchItem is in the
//binary search tree.
//Postcondition: Returns true if searchItem is found
// in the binary search tree;
// otherwise, returns false.
public boolean search(T searchItem)
{
BinaryTreeNode<T> current;
boolean found = false;
if (root == null)
System.out.println("Cannot search an empty tree.");
else
{
current = root;
while (current != null && !found)
{
Comparable<T> temp =
(Comparable<T>) current.info;
if (temp.compareTo(searchItem) == 0)
found = true;
else if (temp.compareTo(searchItem) > 0)
current = current.lLink;
else
current = current.rLink;
}//end while
}//end else
return found;
}//end search
//Method to insert insertItem in the binary search tree.
//Postcondition: If no node in the binary search tree has
// the same info as insertItem, a node with
// the info insertItem is created and inserted
// in the binary search tree.
public void insert(T insertItem)
{
BinaryTreeNode<T> current; //reference variable to
//traverse the tree
BinaryTreeNode<T> trailCurrent = null; //reference variable
//behind current
BinaryTreeNode<T> newNode; //reference variable to
//create the node
newNode = new BinaryTreeNode<T>(insertItem, null, null);
if (root == null)
root = newNode;
else
{
current = root;
while (current != null)
{
trailCurrent = current;
Comparable<T> temp1 =
(Comparable<T>) current.info;
if (temp1.compareTo(insertItem) == 0)
{
System.err.print("The insert item is "
+ "already in the tree -- "
+ "duplicates are not "
+ "allowed.");
return;
}
else if (temp1.compareTo(insertItem) > 0)
current = current.lLink;
else
current = current.rLink;
}//end while
Comparable<T> temp2 =
(Comparable<T>) trailCurrent.info;
if (temp2.compareTo(insertItem) > 0)
trailCurrent.lLink = newNode;
else
trailCurrent.rLink = newNode;
}
}//end insert
//Method to delete deleteItem from the binary search tree
//Postcondition: If a node with the same info as
// deleteItem is found, it is deleted from
// the binary search tree.
public void deleteNode(T deleteItem)
{
BinaryTreeNode<T> current; //reference variable to
//traverse the tree
BinaryTreeNode<T> trailCurrent; //reference variable
//behind current
boolean found = false;
if (root == null)
System.err.println("Cannot delete from an "
+ "empty tree.");
else
{
current = root;
trailCurrent = root;
while (current != null && !found)
{
if (current.info.equals(deleteItem))
found = true;
else
{
trailCurrent = current;
Comparable<T> temp =
(Comparable<T>) current.info;
if (temp.compareTo(deleteItem) > 0)
current = current.lLink;
else
current = current.rLink;
}
}//end while
if (current == null)
System.out.println("The delete item is not in "
+ "the tree.");
else if (found)
{
if (current == root)
root = deleteFromTree(root);
else
{
Comparable<T> temp =
(Comparable<T>) trailCurrent.info;
if (temp.compareTo(deleteItem) > 0)
trailCurrent.lLink =
deleteFromTree(trailCurrent.lLink);
else
trailCurrent.rLink =
deleteFromTree(trailCurrent.rLink);
}
}//end else-if
}
}//end deleteNode
//Method to delete the node, to which p points, from
//the binary search tree.
//Postcondition: The node to which p points is deleted
// from the binary search tree. The
// reference of the root node of the binary
// search tree after deletion is returned.
private BinaryTreeNode deleteFromTree(BinaryTreeNode<T> p)
{
BinaryTreeNode<T> current; //reference variable to
//traverse the tree
BinaryTreeNode<T> trailCurrent; //reference variable
//behind current
if (p == null)
System.err.println("Error: The node to be deleted "
+ "is null.");
else if (p.lLink == null && p.rLink == null)
p = null;
else if (p.lLink == null)
p = p.rLink;
else if (p.rLink == null)
p = p.lLink;
else
{
current = p.lLink;
trailCurrent = null;
while (current.rLink != null)
{
trailCurrent = current;
current = current.rLink;
}//end while
p.info = current.info;
if (trailCurrent == null) //current did not move;
//current == p.lLink;
//adjust p
p.lLink = current.lLink;
else
trailCurrent.rLink = current.lLink;
}//end else
return p;
}//end deleteFromTree
}
_______________________________________________________________________________________________
import java.util.NoSuchElementException;
public abstract class BinaryTree<T> implements BinaryTreeADT<T>
{
//Definition of the class implementing binary nodes
protected class BinaryTreeNode<T>
{
public T info;
public BinaryTreeNode<T> lLink;
public BinaryTreeNode<T> rLink;
//Default constructor
//Postcondition: info = null; lLink = null; rLink = null;
public BinaryTreeNode()
{
info = null;
lLink = null;
rLink = null;
}
//Constructor with parameters
//Sets info to point to the object elem points to and
//lLink and rLink are set to point to the objects left
//and right, respectively.
//Postcondition: info = elem; lLink = left;
// rLink = right;
public BinaryTreeNode(T elem, BinaryTreeNode<T> left,
BinaryTreeNode<T> right)
{
info = elem;
lLink = left;
rLink = right;
}
//Returns a clone of this binary tree.
//This method clones only the references stored in the
//nodes of the binary tree. The objects that binary tree
//nodes point to are not cloned.
public Object clone()
{
BinaryTreeNode<T> copy = null;
try
{
copy = (BinaryTreeNode<T>) super.clone();
}
catch (CloneNotSupportedException e)
{
return null;
}
return copy;
}
//Method to return the info as a string.
//Postcondition: info as a String object is returned.
public String toString()
{
return info.toString();
}
}
protected BinaryTreeNode<T> root;
//Default constructor
//Postcondition: root = null;
public BinaryTree()
{
root = null;
}
//Returns a clone of this binary tree.
//This method clones only the references stored in the nodes
//of the binary tree. The objects that binary tree nodes
//point to are not cloned.
public Object clone()
{
BinaryTree<T> copy = null;
try
{
copy = (BinaryTree<T>) super.clone();
}
catch (CloneNotSupportedException e)
{
return null;
}
if (root != null)
copy.root = copyTree(root);
return copy;
}
//Method to determine whether the binary tree is empty.
//Postcondition: Returns true if the binary tree is
// empty; otherwise, returns false.
public boolean isEmpty()
{
return (root == null);
}
//Method to do an inorder traversal of the binary tree.
//Postcondition: The nodes of the binary tree are output
// in the inorder sequence.
public void inorderTraversal()
{
inorder(root);
}
//Method to do a preorder traversal of the binary tree.
//Postcondition: The nodes of the binary tree are output
// in the preorder sequence.
public void preorderTraversal()
{
preorder(root);
}
//Method to do a postorder traversal of the binary tree.
//Postcondition: The nodes of the binary tree are output
// in the postorder sequence.
public void postorderTraversal()
{
postorder(root);
}
//Method to determine the height of the binary tree.
//Postcondition: The height of the binary tree is
// returned.
public int treeHeight()
{
return height(root);
}
//Method to determine the number of nodes in the
//binary tree.
//Postcondition: The number of nodes in the binary tree
// is returned.
public int treeNodeCount()
{
return nodeCount(root);
}
//Method to determine the number of leaves in the
//binary tree.
//Postcondition: The number of leaves in the binary tree
// is returned.
public int treeLeavesCount()
{
return leavesCount(root);
}
//Method to destroy the binary tree.
//Postcondition: root = null
public void destroyTree()
{
root = null;
}
//Method to determine whether searchItem is in the binary
//tree.
//Postcondition: Returns true if searchItem is found
// in the binary tree;
// otherwise, returns false.
public abstract boolean search(T searchItem);
//Method to insert insertItem in the binary tree.
//Postcondition: If no node in the binary tree has the same
// info as insertItem, a node with the info
// insertItem is created and inserted
// in the binary tree.
public abstract void insert(T insertItem);
//Method to delete deleteItem from the binary tree.
//Postcondition: If a node with the same info as
// deleteItem is found, it is deleted
// from the binary tree.
public abstract void deleteNode(T deleteItem);
//Method to do an inorder traversal of the binary
//tree to which p points.
//Postcondition: The nodes of the binary tree to which p
// points are output in the inorder
// sequence.
private void inorder(BinaryTreeNode<T> p)
{
if (p != null)
{
inorder(p.lLink);
System.out.print(p.info + " ");
inorder(p.rLink);
}
}
//Method to do a preorder traversal of the binary
//tree to which p points.
//Postcondition: The nodes of the binary tree to which p
// points are output in the preorder
// sequence.
private void preorder(BinaryTreeNode<T> p)
{
if (p != null)
{
System.out.print(p.info + " ");
preorder(p.lLink);
preorder(p.rLink);
}
}
//Method to do a postorder traversal of the binary
//tree to which p points.
//Postcondition: The nodes of the binary tree to which p
// points are output in the postorder
// sequence.
private void postorder(BinaryTreeNode<T> p)
{
if (p != null)
{
postorder(p.lLink);
postorder(p.rLink);
System.out.print(p.info + " ");
}
}
//Method to determine the height of the binary tree
//to which p points.
//Postcondition: The height of the binary tree to
// which p points is returned.
private int height(BinaryTreeNode<T> p)
{
if (p == null)
return 0;
else
return 1 + Math.max(height(p.lLink),
height(p.rLink));
}
//Method to determine the number of nodes in the binary
//tree to which p points.
//Postcondition: The number of nodes in the binary tree
// to which p points is returned.
private int nodeCount(BinaryTreeNode<T> p)
{
// System.out.println("ToDo nodeCount");
//ToDo
return 0;
}
//Method to determine the number of leaves in the binary
//tree to which p points.
//Postcondition: The number of leaves in the binary tree
// to which p points is returned.
private int leavesCount(BinaryTreeNode<T> p)
{
// System.out.println("ToDo leavesCount");
//ToDo
return 0;
}
//Method to make a copy of the binary tree to which
//otherTreeRoot points.
//Postcondition: A copy of the binary tree to which
// otherTreeRoot is created and the reference of
// the root node of the copied binary tree
// is returned.
private BinaryTreeNode<T> copyTree
(BinaryTreeNode<T> otherTreeRoot)
{
BinaryTreeNode<T> temp;
if (otherTreeRoot == null)
temp = null;
else
{
temp = (BinaryTreeNode<T>) otherTreeRoot.clone();
temp.lLink = copyTree(otherTreeRoot.lLink);
temp.rLink = copyTree(otherTreeRoot.rLink);
}
return temp;
}//end copyTree
public int singleParent()
{
return singleP(root);
}
private int singleP(BinaryTreeNode<T> p)
{
// System.out.println("ToDo singleP");
//ToDo
return 0;
}
}
________________________________________________________________________________________________
public interface BinaryTreeADT<T> extends Cloneable
{
public Object clone();
//Returns a clone of this binary tree.
//This method clones only the references stored in
//the nodes of the binary tree. The objects that
//binary tree nodes point to are not cloned.
public boolean isEmpty();
//Method to determine whether the binary tree is empty.
//Postcondition: Returns true if the binary tree is
// empty; otherwise, returns false.
public void inorderTraversal();
//Method to do an inorder traversal of the binary tree.
//Postcondition: The nodes of the binary tree are
// output in the inorder sequence.
public void preorderTraversal();
//Method to do a preorder traversal of the binary tree.
//Postcondition: The nodes of the binary tree are
// output in the preorder sequence.
public void postorderTraversal();
//Method to do a postorder traversal of the binary tree.
//Postcondition: The nodes of the binary tree are
// output in the postorder sequence.
public int treeHeight();
//Method to determine the height of the binary tree.
//Postcondition: The height of the binary tree is
// returned.
public int treeNodeCount();
//Method to determine the number of nodes in the
//binary tree.
//Postcondition: The number of nodes in the binary
// tree is returned.
public int treeLeavesCount();
//Method to determine the number of leaves in the
//binary tree.
//Postcondition: The number of leaves in the binary
// tree is returned.
public void destroyTree();
//Method to destroy the binary tree.
//Postcondition: root = null
public boolean search(T searchItem);
//Method to determine whether searchItem is in the
//binary search tree.
//Postcondition: Returns true if searchItem is found
// in the binary search tree;
// otherwise, returns false.
public void insert(T insertItem);
//Method to insert insertItem in the binary search tree.
//Postcondition: If no node in the binary search tree
// has the same info as insertItem, a node
// with the info insertItem is created and
// inserted in the binary search tree.
public void deleteNode(T deleteItem);
//Method to delete deleteItem from the binary search tree
//Postcondition: If a node with the same info as
// deleteItem is found, it is deleted from
// the binary search tree.
public int singleParent();
}
Explanation / Answer
definition of the method leavesCount that takes as a parameter a reference of the root node of a binary tree and returns the numbers of leaves in the binary tree. This what i get so far
public class BinaryTree
{
//Definition of the node
protected class BinaryTreeNode
{
DataElement info;
BinaryTreeNode llink;
BinaryTreeNode rlink;
}
protected BinaryTreeNode root;
//default constructor
//Postcondition: root = null;
public BinaryTree()
{
root = null;
}
//copy constructor
public BinaryTree(BinaryTree otherTree)
{
if(otherTree.root == null) //otherTree is empty
root = null;
else
root = copy(otherTree.root);
}
//Method to determine whether the binary tree is empty.
//Postcondition: Returns true if the binary tree is empty;
// otherwise, returns false.
public boolean isEmpty()
{
return (root == null);
}
//Method to do an inorder traversal of the binary tree.
//Postcondition: The nodes of the binary tree are output
// in the inorder sequence.
public void inorderTraversal()
{
inorder(root);
}
//Method to do a preorder traversal of the binary tree.
//Postcondition: The nodes of the binary tree are output
// in the preorder sequence.
public void preorderTraversal()
{
preorder(root);
}
//Method to do a postorder traversal of the binary tree.
//Postcondition: The nodes of the binary tree are output
// in the postorder sequence.
public void postorderTraversal()
{
postorder(root);
}
//Method to determine the height of the binary tree.
//Postcondition: The height of the binary tree is returned.
public int treeHeight()
{
return height(root);
}
//Method to determine the number of nodes in the
//binary tree.
//Postcondition: The number of nodes in the binary tree
// is returned.
public int treeNodeCount()
{
return nodeCount(root);
}
//Method to determine the number of leaves in the
//binary tree.
//Postcondition: The number of leaves in the binary tree
// is returned.
public int treeLeavesCount()
{
return leavesCount(root);
}
//Method to destroy the binary tree.
//Postcondition: root = null
public void destroyTree()
{
root = null;
}
//Method to make a copy of the binary tree
//specified by otherTree points.
//Postcondition: A copy of otherTree is assigned to
// this binary tree.
public void copyTree(BinaryTree otherTree)
{
if(this != otherTree) //avoid self-copy
{
root = null;
if(otherTree.root != null) //otherTree is nonempty
root = copy(otherTree.root);
}
}
//Method to make a copy of the binary tree to
//which otherTreeRoot points.
//Postcondition: A copy of the binary tree to which
// otherTreeRoot is created and the reference of
// the root node of the copied binary tree
// is returned.
private BinaryTreeNode copy(BinaryTreeNode otherTreeRoot)
{
BinaryTreeNode temp;
if(otherTreeRoot == null)
temp = null;
else
{
temp = new BinaryTreeNode();
temp.info = otherTreeRoot.info.getCopy();
temp.llink = copy(otherTreeRoot.llink);
temp.rlink = copy(otherTreeRoot.rlink);
}
return temp;
}//end copy
//Method to do an inorder traversal of the binary
//tree to which p points.
//Postcondition: The nodes of the binary tree to which p
// points are output in the inorder sequence.
private void inorder(BinaryTreeNode p)
{
if(p != null)
{
inorder(p.llink);
System.out.print(p.info + " ");
inorder(p.rlink);
}
}
//Method to do a preorder traversal of the binary
//tree to which p points.
//Postcondition: The nodes of the binary tree to which p
// points are output in the preorder sequence.
private void preorder(BinaryTreeNode p)
{
if(p != null)
{
System.out.print(p.info + " ");
preorder(p.llink);
preorder(p.rlink);
}
}
//Method to do a postorder traversal of the binary
//tree to which p points.
//Postcondition: The nodes of the binary tree to which p
// points are output in the postorder sequence.
private void postorder(BinaryTreeNode p)
{
if(p != null)
{
postorder(p.llink);
postorder(p.rlink);
System.out.print(p.info + " ");
}
}
//Method to determine the height of the binary tree
//to which p points.
//Postcondition: The height of the binary tree to which p
// points is returned.
private int height(BinaryTreeNode p)
{
if(p == null)
return 0;
else
return 1 + max(height(p.llink), height(p.rlink));
}
//Method to determine the larger of x and y.
//Postcondition: The larger of x and y is returned.
private int max(int x, int y)
{
if(x >= y)
return x;
else
return y;
}
}
//Method to determine the number of leaves in the binary
//tree to which p points.
//Postcondition: The number of leaves in the binary tree
// to which p points is returned.
private int leavesCount(BinaryTreeNode p)
{
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.