[1] Pre-Order Traversal
[2] In-Order Traversal
[3] Post-Order Traversal
[4] Getting the size of the binary tree
[5] Get the minimum value
[6] Get the maximum value
[7] Get root value
[8] Inserting new elements
My implementation does not include duplication of elements. You may copy the code and test it yourself.
import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;
public class BinaryTree {
private static class TreeNode {
TreeNode left;
TreeNode right;
int nodeValue;
TreeNode(int data) {
left = null;
right = null;
nodeValue = data;
}
}
private TreeNode root;
public BinaryTree() {
root = null;
}
public void constructBinaryTreeHardCoded() {
root = null;
root = new TreeNode(6);
//root = insertData(root, 6);
root = insertData(root, 2);
root = insertData(root, 7);
root = insertData(root, 1);
root = insertData(root, 4);
root = insertData(root, 9);
root = insertData(root, 3);
root = insertData(root, 5);
root = insertData(root, 8);
}
public void testHarness(){
root = null;
Random rand = new Random();
int rootValue = rand.nextInt( 20 ) + 1;
root = new TreeNode(rootValue);
System.out.println("Random seeded root value: " + rootValue);
int numberOfNodes = rand.nextInt( 18 ) + 1;
System.out.println("Random number of children to be generated: " + numberOfNodes);
for (int i = 0; i < numberOfNodes; i++) {
int randValue = rand.nextInt( 30 ) + 1;
System.out.println("Inserting: " + randValue);
root = insertData(root, randValue);
}
}
public TreeNode insertData(TreeNode node, int data) {
if (node == null) {
node = new TreeNode(data);
} else {
if (data < node.nodeValue) {
if (node.left != null) {
node.left = insertData(node.left, data);
} else {
node.left = new TreeNode(data);
System.out.println("Inserted " + data + " to the left of " + node.nodeValue);
}
} else if (data > node.nodeValue) {
if (node.right != null) {
node.right = insertData(node.right, data);
} else {
node.right = new TreeNode(data);
System.out.println("Inserted " + data + " to the right of " + node.nodeValue);
}
} else {
System.out.println("Not inserting " + data + " because it already exists in the tree");
}
}
return(node);
}
public boolean isIdenticalTree(BinaryTree comparedTree) {
return (isIdenticalTree(root, comparedTree.root));
}
private boolean isIdenticalTree(TreeNode first, TreeNode second) {
if (first == null && second == null) {
return true;
} else if (first != null && second != null) {
return (
first.nodeValue == second.nodeValue &&
isIdenticalTree(first.left, second.left) &&
isIdenticalTree(first.right, second.right)
);
} else {
return false;
}
}
public int getSize() {
return(setSize(root));
}
private int setSize(TreeNode node) {
if (node == null) {
return 0;
} else {
return(setSize(node.left) + 1 + setSize(node.right));
}
}
public void printTreeTraversal() {
System.out.print("Inorder Traversal: ");
printInOrder(root);
System.out.print("\nPreorder Traversal: ");
printPreOrder(root);
System.out.print("\nPostorder Traversal: ");
printPostOrder(root);
System.out.println();
}
private void printInOrder(TreeNode node) {
if (node == null) {
return;
}
printInOrder(node.left);
visitTreeNode(node);
printInOrder(node.right);
}
private void printPreOrder(TreeNode node) {
if (node == null) {
return;
}
visitTreeNode(node);
printPreOrder(node.left);
printPreOrder(node.right);
}
private void printPostOrder(TreeNode node) {
if (node == null) {
return;
}
printPostOrder(node.left);
printPostOrder(node.right);
visitTreeNode(node);
}
private void visitTreeNode(TreeNode node){
System.out.print(node.nodeValue + " ");
}
public int getMinValue() {
return (getMinValue(root));
}
private int getMinValue(TreeNode node) {
while (node.left != null) {
node = node.left;
}
return (node.nodeValue);
}
public int getMaxValue() {
return (getMaxValue(root));
}
private int getMaxValue(TreeNode node) {
while (node.right != null) {
node = node.right;
}
return (node.nodeValue);
}
public int getMaxDepth() {
int depth = getMaxDepth(root);
return ((depth > 0) ? (depth - 1) : 0);
}
private int getMaxDepth(TreeNode node) {
if (node == null) {
return 0;
} else {
int leftDepth = getMaxDepth(node.left);
int rightDepth = getMaxDepth(node.right);
return (((leftDepth > rightDepth) ? leftDepth : rightDepth) + 1);
}
}
public boolean containsData(int data) {
return(containsData(root, data));
}
private boolean containsData(TreeNode node, int data) {
if (node == null) {
return false;
}
if (data == node.nodeValue) {
return true;
} else if (data < node.nodeValue) {
return(containsData(node.left, data));
} else {
return(containsData(node.right, data));
}
}
public int getRootValue(){
return root.nodeValue;
}
public boolean containsSumInPath(int total) {
return( containsSumInPath(root, total) );
}
private boolean containsSumInPath(TreeNode node, int total) {
if (node == null) {
return(total == 0);
} else {
int remainder = total - node.nodeValue;
if (containsSumInPath(node.left, remainder) || containsSumInPath(node.right, remainder)) {
addPaths( remainder, node.nodeValue, total);
}
return(containsSumInPath(node.left, remainder) || containsSumInPath(node.right, remainder));
}
}
private ArrayListpath = new ArrayList ();
private void addPaths(int remainder, int currentNodeValue, int total){
if (!path.contains(currentNodeValue)) {
path.add(currentNodeValue);
}
}
public ArrayListgetSumOfPath(){
Collections.reverse(path);
return path;
}
public static void main(String[] args) {
BinaryTree bTree1 = new BinaryTree();
BinaryTree bTree2 = new BinaryTree();
bTree1.constructBinaryTreeHardCoded();
System.out.println("Size of the binary tree: " + bTree1.getSize());
System.out.println("Root value in the binary tree: " + bTree1.getRootValue());
System.out.println("Smallest value in the binary tree: " + bTree1.getMinValue());
System.out.println("Largest value in the binary tree: " + bTree1.getMaxValue());
System.out.println("Maximum depth of the binary tree: " + bTree1.getMaxDepth());
System.out.println("Contains node value 4: " + bTree1.containsData(4));
System.out.println("Path has sum of 30: " + bTree1.containsSumInPath(30) + " = " + bTree1.getSumOfPath());
bTree1.printTreeTraversal();
System.out.println();
bTree2.testHarness();
System.out.println("Size of the binary tree: " + bTree2.getSize());
System.out.println("Root value in the binary tree: " + bTree2.getRootValue());
System.out.println("Smallest value in the binary tree: " + bTree2.getMinValue());
System.out.println("Largest value in the binary tree: " + bTree2.getMaxValue());
System.out.println("Maximum depth of the binary tree: " + bTree2.getMaxDepth());
System.out.println("Contains node value 11: " + bTree2.containsData(11));
Random rand = new Random();
int find = rand.nextInt( 30 ) + 1;
System.out.println("Path has sum of "+ find +": " + bTree2.containsSumInPath(find) + " = " + bTree2.getSumOfPath());
bTree2.printTreeTraversal();
System.out.println("Are identical binary trees: " + bTree1.isIdenticalTree(bTree2));
System.out.println("\nChanged elements in binary tree");
bTree2.constructBinaryTreeHardCoded();
System.out.println("Are identical binary trees: " + bTree1.isIdenticalTree(bTree2));
}
}
0 comments:
Post a Comment