After writing a class for a Generic Tree Node, we need to write a Generic Tree class, which will use Generic Tree Nodes to build a Generic Tree:
GenericTreeTraversalOrderEnum.java
1 2 3 4 | public enum GenericTreeTraversalOrderEnum { PRE_ORDER, POST_ORDER } |
GenericTree.java
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 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 | import java.util.*; public class GenericTree<T> { private GenericTreeNode<T> root; public GenericTree() { super (); } public GenericTreeNode<T> getRoot() { return this .root; } public void setRoot(GenericTreeNode<T> root) { this .root = root; } public int getNumberOfNodes() { int numberOfNodes = 0 ; if (root != null ) { numberOfNodes = auxiliaryGetNumberOfNodes(root) + 1 ; //1 for the root! } return numberOfNodes; } private int auxiliaryGetNumberOfNodes(GenericTreeNode<T> node) { int numberOfNodes = node.getNumberOfChildren(); for (GenericTreeNode<T> child : node.getChildren()) { numberOfNodes += auxiliaryGetNumberOfNodes(child); } return numberOfNodes; } public boolean exists(GenericTreeNode<T> nodeToFind) { return (find(nodeToFind) != null ); } public GenericTreeNode<T> find(GenericTreeNode<T> nodeToFind) { GenericTreeNode<T> returnNode = null ; if (root != null ) { returnNode = auxiliaryFind(root, nodeToFind); } return returnNode; } private GenericTreeNode<T> auxiliaryFind(GenericTreeNode<T> currentNode, GenericTreeNode<T> nodeToFind) { GenericTreeNode<T> returnNode = null ; int i = 0 ; if (currentNode.equals(nodeToFind)) { returnNode = currentNode; } else if (currentNode.hasChildren()) { i = 0 ; while (returnNode == null && i < currentNode.getNumberOfChildren()) { returnNode = auxiliaryFind(currentNode.getChildAt(i), nodeToFind); i++; } } return returnNode; } public boolean isEmpty() { return (root == null ); } public List<GenericTreeNode<T>> build(GenericTreeTraversalOrderEnum traversalOrder) { List<GenericTreeNode<T>> returnList = null ; if (root != null ) { returnList = build(root, traversalOrder); } return returnList; } public List<GenericTreeNode<T>> build(GenericTreeNode<T> node, GenericTreeTraversalOrderEnum traversalOrder) { List<GenericTreeNode<T>> traversalResult = new ArrayList<GenericTreeNode<T>>(); if (traversalOrder == GenericTreeTraversalOrderEnum.PRE_ORDER) { buildPreOrder(node, traversalResult); } else if (traversalOrder == GenericTreeTraversalOrderEnum.POST_ORDER) { buildPostOrder(node, traversalResult); } return traversalResult; } private void buildPreOrder(GenericTreeNode<T> node, List<GenericTreeNode<T>> traversalResult) { traversalResult.add(node); for (GenericTreeNode<T> child : node.getChildren()) { buildPreOrder(child, traversalResult); } } private void buildPostOrder(GenericTreeNode<T> node, List<GenericTreeNode<T>> traversalResult) { for (GenericTreeNode<T> child : node.getChildren()) { buildPostOrder(child, traversalResult); } traversalResult.add(node); } public Map<GenericTreeNode<T>, Integer> buildWithDepth(GenericTreeTraversalOrderEnum traversalOrder) { Map<GenericTreeNode<T>, Integer> returnMap = null ; if (root != null ) { returnMap = buildWithDepth(root, traversalOrder); } return returnMap; } public Map<GenericTreeNode<T>, Integer> buildWithDepth(GenericTreeNode<T> node, GenericTreeTraversalOrderEnum traversalOrder) { Map<GenericTreeNode<T>, Integer> traversalResult = new LinkedHashMap<GenericTreeNode<T>, Integer>(); if (traversalOrder == GenericTreeTraversalOrderEnum.PRE_ORDER) { buildPreOrderWithDepth(node, traversalResult, 0 ); } else if (traversalOrder == GenericTreeTraversalOrderEnum.POST_ORDER) { buildPostOrderWithDepth(node, traversalResult, 0 ); } return traversalResult; } private void buildPreOrderWithDepth(GenericTreeNode<T> node, Map<GenericTreeNode<T>, Integer> traversalResult, int depth) { traversalResult.put(node, depth); for (GenericTreeNode<T> child : node.getChildren()) { buildPreOrderWithDepth(child, traversalResult, depth + 1 ); } } private void buildPostOrderWithDepth(GenericTreeNode<T> node, Map<GenericTreeNode<T>, Integer> traversalResult, int depth) { for (GenericTreeNode<T> child : node.getChildren()) { buildPostOrderWithDepth(child, traversalResult, depth + 1 ); } traversalResult.put(node, depth); } public String toString() { /* We're going to assume a pre-order traversal by default */ String stringRepresentation = "" ; if (root != null ) { stringRepresentation = build(GenericTreeTraversalOrderEnum.PRE_ORDER).toString(); } return stringRepresentation; } public String toStringWithDepth() { /* We're going to assume a pre-order traversal by default */ String stringRepresentation = "" ; if (root != null ) { stringRepresentation = buildWithDepth(GenericTreeTraversalOrderEnum.PRE_ORDER).toString(); } return stringRepresentation; } } |
This looks great! Just added to my project… you’re a life saver Vivin!
How do we get parent of a child ?