I cannot edit anything else. I have highlighted what can be edited. Given: MyTre
ID: 3705291 • Letter: I
Question
I cannot edit anything else. I have highlighted what can be edited.
Given: MyTree.java & TreeNode.java
public class MyTree{
private TreeNode root;
public MyTree(){
root=null;
}
public void remove(int data){
//implement this method to remove a node with the same data value
}
public void printReverse(){
//implement this method to print data in descending order
}
public void display(){
//implement to display the tree structure
}
public boolean isEmpty(){ return root==null;}
public int size(){
return sizeHelper(root);
}
private int sizeHelper(TreeNode node){
if(node==null) return 0;
else return 1+sizeHelper(node.getLeft())+sizeHelper(node.getRight());
}
public boolean search(int data){
return searchHelper(root, data);
}
private boolean searchHelper(TreeNode node, int data){
if(node==null) return false;
if(node.getData()==data) return true;
else if(node.getData()<data)
return searchHelper(node.getRight(),data);
else
return searchHelper(node.getLeft(), data);
}
public void add(int data){
root=addHelper(root, data);
}
private TreeNode addHelper(TreeNode node, int data){
if(node==null) node=new TreeNode(data);
else if(data<=node.getData()) //or call compareTo method
node.setLeft(addHelper(node.getLeft(), data));
else
node.setRight(addHelper(node.getRight(), data));
return node;
}
public void printInorder(){
printHelper(root);
}
private void printHelper(TreeNode node){
if(node!=null){
printHelper(node.getLeft());
System.out.println(node.getData());
printHelper(node.getRight());
}
}
}
public class TreeNode implements Comparable<TreeNode>{
private int data;
private TreeNode left;
private TreeNode right;
public TreeNode(int data){
this.data=data;
left=right=null;
}
public int getData(){
return data;
}
public TreeNode getLeft(){
return left;
}
public TreeNode getRight(){
return right;
}
public void setData(int data){
this.data = data;
}
public void setLeft(TreeNode left){
this.left = left;
}
public void setRight(TreeNode right){
this.right = right;
}
public int compareTo(TreeNode node){
return data-node.getData();
}
}
Explanation / Answer
The below code is the implementation of above 3 functions highlighted in bold--
public void remove(int data, BSTNode pos){
//implement this method to remove a node with the same data value
key
if (pos == null) return;
if (data.compareTo(pos.data)<0)
remove (data, pos.leftChild);
else if (data.compareTo(pos.data)>0)
remove (data, pos.rightChild);
else {
if (pos.leftChild != null && pos.rightChild != null)
{
/* pos has two children */
BSTNode maxFromLeft = findMax (pos.leftChild); //need to make a findMax helper
//"Replacing " pos.data " with " maxFromLeft.data
pos.data = maxFromLeft.data;
remove (maxFromLeft.data, pos.leftChild);
}
else if(pos.leftChild != null) {
/* node pointed by pos has at most one child */
BSTNode trash = pos;
//"Promoting " pos.leftChild.data " to replace " pos.data
pos = pos.leftChild;
trash = null;
}
else if(pos.rightChild != null) {
/* node pointed by pos has at most one child */
BSTNode trash = pos;
/* "Promoting " pos.rightChild.data" to replace " pos.data */
pos = pos.rightChild;
trash = null;
}
else {
pos = null;
}
}
}
void printReverse(node* root) / done using stacks and queue data structure
{
stack <node *> S; // initialize stack
queue <node *> Q; // initialize queue
Q.push(root); // root is pushed into Queue
// 1) Instead of printing a node, we push the node to stack
// 2) Right subtree is visited before left subtree
while (Q.empty() == false)
{
/* Dequeue node and make it root */
root = Q.front();
Q.pop();
S.push(root);
/* Enqueue right child */
if (root->right)
Q.push(root->right); // NOTE: RIGHT CHILD IS ENQUEUED BEFORE LEFT
/* Enqueue left child */
if (root->left)
Q.push(root->left);
}
// Now pop all items from stack one by one and print them
while (S.empty() == false)
{
root = S.top(); // this reverses the order of level order traversal
cout << root->data << " ";
S.pop();
}
}
public void display(){
//implement to display the tree structure- will display level order traversal of tree
{
int h = heightOfTree(root); will calculate tree's height
int i;
for (i=1; i<=h; i++)
printGivenLevel(root, i);
}
/* Compute the "height" of a tree -- the number of
nodes along the longest path from the root node
down to the farthest leaf node.*/
int heightOfTree(Node root)
{
if (root == null)
return 0;
else
{
/* compute height of each subtree */
int lheight = heightOfTree(root.left);
int rheight = heightOfTree(root.right);
/* use the larger one */
if (lheight > rheight)
return(lheight+1);
else return(rheight+1);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.