Question: Using the following implementation of Tree in java class Node { public int iData; // data item (key) public double dData; // data item public
Using the following implementation of Tree in java
class Node
{
public int iData; // data item (key)
public double dData; // data item
public Node leftChild; // this node's left child
public Node rightChild; // this node's right child
public void displayNode() // display ourself
{
System.out.print('{');
System.out.print(iData);
System.out.print(", ");
System.out.print(dData);
System.out.print("} ");
}
} // end class Node
//------------------------------------------------------------------
import java.io.IOException;
import java.util.Stack;
public class Tree
{ private Node root; // first node of tree
// -------------------------------------------------------------
public Tree() // constructor
{ root = null; } // no nodes in tree yet // -------------------------------------------------------------
public Node find(int key) // find node with given key
{ // (assumes non-empty tree) Node current = root; // start at root
while(current.iData != key) // while no match,
{ if(key < current.iData) // go left?
current = current.leftChild;
else // or go right?
current = current.rightChild;
if(current == null) // if no child,
return null; // didn't find it
}
return current; // found it
} // end find()
// -------------------------------------------------------------
public void insert(int id, double dd)
{ Node newNode = new Node(); // make new node
newNode.iData = id; // insert data
newNode.dData = dd;
if(root==null) // no node in root
root = newNode;
else // root occupied
{ Node current = root; // start at root
Node parent;
while(true) // (exits internally)
{ parent = current;
if(id < current.iData) // go left?
{ current = current.leftChild;
if(current == null) // if end of the line,
{ // insert on left parent.leftChild = newNode;
return;
}
} // end if go left
else // or go right?
{ current = current.rightChild;
if(current == null) // if end of the line
{ // insert on right parent.rightChild = newNode;
return;
}
} // end else go right
} // end while
} // end else not root
} // end insert()
// -------------------------------------------------------------
public boolean delete(int key) // delete node with given key
{ // (assumes non-empty list) Node current = root;
Node parent = root;
boolean isLeftChild = true;
while(current.iData != key) // search for node
{ parent = current;
if(key < current.iData) // go left?
{ isLeftChild = true;
current = current.leftChild;
}
else // or go right?
{ isLeftChild = false;
current = current.rightChild;
}
if(current == null) // end of the line,
return false; // didn't find it
} // end while
// found node to delete
// if no children, simply delete it
if(current.leftChild==null &&
current.rightChild==null)
{ if(current == root) // if root,
root = null; // tree is empty
else if(isLeftChild)
parent.leftChild = null; // disconnect
else // from parent
parent.rightChild = null;
}
// if no right child, replace with left subtree
else if(current.rightChild==null)
if(current == root)
root = current.leftChild;
else if(isLeftChild)
parent.leftChild = current.leftChild;
else
parent.rightChild = current.leftChild;
// if no left child, replace with right subtree
else if(current.leftChild==null)
if(current == root)
root = current.rightChild;
else if(isLeftChild)
parent.leftChild = current.rightChild;
else
parent.rightChild = current.rightChild;
else // two children, so replace with inorder successor
{ // get successor of node to delete (current)
Node successor = getSuccessor(current);
// connect parent of current to successor instead
if(current == root)
root = successor;
else if(isLeftChild)
parent.leftChild = successor;
else
parent.rightChild = successor;
// connect successor to current's left child
successor.leftChild = current.leftChild;
} // end else two children
// (successor cannot have a left child)
return true; // success
} // end delete()
// -------------------------------------------------------------
// returns node with next-highest value after delNode
// goes to right child, then right child's left descendents
private Node getSuccessor(Node delNode)
{ Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.rightChild; // go to right child
while(current != null) // until no more
{ // left children, successorParent = successor;
successor = current;
current = current.leftChild; // go to left child
}
// if successor not
if(successor != delNode.rightChild) // right child,
{ // make connections successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
}
return successor;
}
// -------------------------------------------------------------
public void traverse(int traverseType)
{ switch(traverseType)
{ case 1: System.out.print(" Preorder traversal: "); preOrder(root);
break;
case 2: System.out.print(" Inorder traversal: "); inOrder(root);
break;
case 3: System.out.print(" Postorder traversal: "); postOrder(root);
break;
}
System.out.println();
}
// -------------------------------------------------------------
private void preOrder(Node localRoot)
{ if(localRoot != null)
{ System.out.print(localRoot.iData + " ");
preOrder(localRoot.leftChild);
preOrder(localRoot.rightChild);
}
}
// -------------------------------------------------------------
private void inOrder(Node localRoot)
{ if(localRoot != null)
{ inOrder(localRoot.leftChild);
System.out.print(localRoot.iData + " ");
inOrder(localRoot.rightChild);
}
}
// -------------------------------------------------------------
private void postOrder(Node localRoot)
{ if(localRoot != null)
{ postOrder(localRoot.leftChild);
postOrder(localRoot.rightChild);
System.out.print(localRoot.iData + " ");
}
}
// -------------------------------------------------------------
Add the following methods:
1- Find the number of leaves of the tree which are left child of their parent.
2-Find the number of internal nodes.
3-Find the maximum value in a binary search tree.
4-Print a binary inorder.
Step by Step Solution
There are 3 Steps involved in it
1 Expert Approved Answer
Step: 1 Unlock
Question Has Been Solved by an Expert!
Get step-by-step solutions from verified subject matter experts
Step: 2 Unlock
Step: 3 Unlock
Study Help