The following two classes demonstrate an implementation of the Generic Binary Tree data structure.
The first class is BinaryTreeNode.java which acts as the node class for the tree, holding integer type data and two pointers for left and right child respectively of type same as the node class itself. The member fields are declared to be public by intention of increasing the readability of the code ahead.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
/** * Can act as the node class for any binary tree with integer type data. * @author team Coddicted * */ public class BinaryTreeNode { public int x; // To store the data public BinaryTreeNode leftNode; // To store the left child reference public BinaryTreeNode rightNode; // To store the right child reference } |
The second class is GenericBinaryTree.java which provides the basic methods for creating and traversing the tree. So far, we’ve not added any method for deletion of nodes. The implementation provides two overloaded methods for inserting a new node in the tree.
First one is the raw level fill insertion, which inserts the new node on the first empty slot on last running level of the tree.
The other implementation provides option to tell the path of the new node to be inserted in the tree in the form of a String of consecutive ‘r’ and ‘l’ (small for ‘L’ char) characters to denote the two directions at each location starting from the root node. Note, however, that this method assumes that the root node has previously been created.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 |
import java.util.LinkedList; import java.util.Queue; /** * Implementation of a GenericBinaryTree with <code>int</code> type data. * The nodes are of type {@link BinaryTreeNode}. * * @author team Coddicted * */ public class GenericBinaryTree { /** * Adds a new {@link BinaryTreeNode} type node with <code>data</code> as * its value to the current GenericBinaryTree pointed by <code>root</code>. * * @param root * @param data */ public void insertIntoGenericBinaryTree(BinaryTreeNode root, int data){ BinaryTreeNode newNode, tempNode; Queue<BinaryTreeNode> q; newNode = new BinaryTreeNode(); newNode.x = data; newNode.leftNode = newNode.rightNode = null; if(root == null){ // There are no nodes in the tree right now. // Make the current node as root node. root = newNode; return; } q = new LinkedList<BinaryTreeNode>(); q.add(root); while(q.peek() != null) { tempNode = q.poll(); if(tempNode.leftNode != null) q.add(tempNode.leftNode); else{ tempNode.leftNode = newNode; q = null; return; } if(tempNode.rightNode != null) q.add(tempNode.rightNode); else{ tempNode.rightNode = newNode; q = null; return; } } } public void levelOrderTraverse(BinaryTreeNode root){ BinaryTreeNode tempNode; Queue<BinaryTreeNode> q; if(root == null) return; q = new LinkedList<BinaryTreeNode>(); q.add(root); while(q.peek() != null) { tempNode = q.poll(); System.out.println(tempNode.x); if(tempNode.leftNode != null) q.add(tempNode.leftNode); if(tempNode.rightNode != null) q.add(tempNode.rightNode); } } /** * @param root root node of the tree to be traversed. * @return * The String representation of the entire tree currently held * by the <code>root</code> node.<br> * A node with no children is represented as (<code>data</code>, * <code>null</code>, <code>null</code>). */ public String levelOrderStringTraversal(BinaryTreeNode root){ String leftSubTree, rightSubTree; if(root == null) return null; leftSubTree = levelOrderStringTraversal(root.leftNode); rightSubTree = levelOrderStringTraversal(root.rightNode); return "(" + root.x + ", " + leftSubTree + ", " + rightSubTree + ")"; } /** * Inserts the <code>data</code> as per the specified <code>path</code> * in the tree having root <code>root</code>. * @param root reference of root node for the tree to insert <code>data</code> into. * @param data data value to be inserted as node. * @param path Path specified as String of consecutive 'l' and 'r' characters for * directions to follow at each node, beginning at <code>root</code> */ public void insertIntoGenericBinaryTree(BinaryTreeNode root, int data, String path){ BinaryTreeNode newNode; char[] pathArr = path.toCharArray(); int loopCount = pathArr.length-1, i; newNode = new BinaryTreeNode(); newNode.x = data; newNode.leftNode = newNode.rightNode = null; for(i=0; i<loopCount; i++){ if(pathArr[i]=='l'){ root = root.leftNode; } else if(pathArr[i]=='r') { root = root.rightNode; } else { return; } } if(pathArr[i]=='l') root.leftNode = newNode; else root.rightNode = newNode; } } |
A sample class to demonstrate the usage of above code follows:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
public class GenericBinaryTreeUser { public static void main(String[] args) { GenericBinaryTree gbt = new GenericBinaryTree(); BinaryTreeNode root = new BinaryTreeNode(); root.x = 5; gbt.insertIntoGenericBinaryTree(root, 3,"l"); gbt.insertIntoGenericBinaryTree(root, 4,"ll"); gbt.insertIntoGenericBinaryTree(root, 6,"lll"); gbt.insertIntoGenericBinaryTree(root, 10, "r"); gbt.insertIntoGenericBinaryTree(root, 11, "rr"); gbt.insertIntoGenericBinaryTree(root, 13, "rrr"); gbt.insertIntoGenericBinaryTree(root, 12, "rl"); gbt.insertIntoGenericBinaryTree(root, 21, "rll"); gbt.insertIntoGenericBinaryTree(root, 20, "rlr"); gbt.insertIntoGenericBinaryTree(root, 22, "rlrr"); gbt.insertIntoGenericBinaryTree(root, 23, "rlrrr"); gbt.insertIntoGenericBinaryTree(root, 24, "rlrrrl"); System.out.println(gbt.levelOrderStringTraversal(root)); } } |
The sample usage code above makes a tree as shown below:
Binary Tree: as generated from the code
What’s so generic in node tree (public int x) ???
Hi Tom,
By generic here we mean that the node structure itself is rather irrelevant. You could use any other node class instead of BinaryTreeNode as per your choice and the implementation strategy would still work.
We are not referring to the Java Generics in anyway. Sorry if this is where you got confused.
-Thanks
Team Coddicted