Homework Sourseadd to the implementation of a binary tree program IntTreeA5
add to the implementation of a binary tree program IntTreeA5.java (source listed at the end of this assignment) a method that returns the total number of nodes in a tree. (Hint: look for a recursive solution.) Write a driver program and test it on a few examples. In each test run: insert a few nodes to a tree, then print the tree, and then print the total number of nodes in that tree.
public class IntTreeA5 {
private IntNode root;
public IntTreeA5() {
root = null;
}
public void insert(int val){
IntNode newnode = new IntNode(val,null,null);
if (root == null)
root = newnode;
else
insertRec(newnode, root);
}
private void insertRec(IntNode newnode, IntNode root){
if (newnode.val < root.val) {
if (root.left == null) root.left = newnode;
else insertRec (newnode, root.left);
}
else {
if (root.right == null) root.right = newnode;
else insertRec (newnode, root.right);
}
}
public void treeShape(){
System.out.println(\"--------------------\");
System.out.println(\"tree: \");
treeShapeRec(root, \"\");
System.out.println(\"--------------------\");
}
private void treeShapetRec(IntNode root, String s) {
if (root != null) {
treeShapeRec(root.left, s.replace(\'-\',\' \') + \" ---\");
System.out.println(s + root.val);
treeShapeRec(root.right, s.replace(\'-\',\' \') + \" ---\");
}
}
public int numberOfNodes() {
//put your code here
}
private class IntNode {
public int val;
public IntNode left;
public IntNode right;
public IntNode(int val, IntNode left, IntNode right){
this.val = val;
this.left = left;
this.right = right;
}
}
}
Solution
to find the total number of node in a tree, we need root of the tree. which should be send as argument in numberOfNodes() function.
public int numberOfNodes(IntNode root) {
if (root == null)
return 0;
else
return(numberOfNodes(root.left) + 1 + numberOfNodes(root.right));
}
