@Test public void testBreadthFirstSearch() { for (int i = 1; i < 6; i++) { Assert.assertNotNull(Searcher.breadthFirstSearch(binTree, i)); } Assert.assertNull(Searcher.breadthFirstSearch(binTree, 10)); BinaryTreeNode<Integer> four = Searcher.breadthFirstSearch(binTree, 4); Assert.assertNotNull(four); Assert.assertFalse(four.isLeaf()); Assert.assertNull(four.leftChild()); Assert.assertNotNull(four.rightChild()); Assert.assertEquals(Integer.valueOf(5), four.rightChild().data()); BinaryTreeNode<Integer> five = Searcher.breadthFirstSearch(binTree, 5); Assert.assertTrue(five.isLeaf()); }
public static <E extends Comparable<E>> BinaryTreeNode<E> breadthFirstSearch(BinarySearchTree<E> binTree, BinaryTreeNode<E> startNode, E value) { LOGGER.debug("Searching for: {}.", value); Set<BinaryTreeNode<E>> visited = new HashSet<BinaryTreeNode<E>>(); Queue<BinaryTreeNode<E>> queue = new Queue<BinaryTreeNode<E>>(); LOGGER.debug("Visited: {}.", startNode); visited.add(startNode); queue.enqueue(startNode); BinaryTreeNode<E> node = null; BinaryTreeNode<E> leftChild = null; BinaryTreeNode<E> rightChild = null; while (!queue.isEmpty()) { node = queue.dequeue(); if (node.data().equals(value)) { return node; } leftChild = node.leftChild(); rightChild = node.rightChild(); if (leftChild != null && !visited.contains(leftChild)) { LOGGER.debug("Visited: {}.", leftChild); visited.add(leftChild); queue.enqueue(leftChild); } if (rightChild != null && !visited.contains(rightChild)) { LOGGER.debug("Visited: {}.", rightChild); visited.add(rightChild); queue.enqueue(rightChild); } } return null; }
Searcher { public static <E extends Comparable<E>> BinaryTreeNode<E> breadthFirstSearch(BinarySearchTree<E> binTree, BinaryTreeNode<E> startNode, E value) { LOGGER.debug("Searching for: {}.", value); Set<BinaryTreeNode<E>> visited = new HashSet<BinaryTreeNode<E>>(); Queue<BinaryTreeNode<E>> queue = new Queue<BinaryTreeNode<E>>(); LOGGER.debug("Visited: {}.", startNode); visited.add(startNode); queue.enqueue(startNode); BinaryTreeNode<E> node = null; BinaryTreeNode<E> leftChild = null; BinaryTreeNode<E> rightChild = null; while (!queue.isEmpty()) { node = queue.dequeue(); if (node.data().equals(value)) { return node; } leftChild = node.leftChild(); rightChild = node.rightChild(); if (leftChild != null && !visited.contains(leftChild)) { LOGGER.debug("Visited: {}.", leftChild); visited.add(leftChild); queue.enqueue(leftChild); } if (rightChild != null && !visited.contains(rightChild)) { LOGGER.debug("Visited: {}.", rightChild); visited.add(rightChild); queue.enqueue(rightChild); } } return null; } }
Searcher { public static <E extends Comparable<E>> BinaryTreeNode<E> breadthFirstSearch(BinarySearchTree<E> binTree, BinaryTreeNode<E> startNode, E value) { LOGGER.debug("Searching for: {}.", value); Set<BinaryTreeNode<E>> visited = new HashSet<BinaryTreeNode<E>>(); Queue<BinaryTreeNode<E>> queue = new Queue<BinaryTreeNode<E>>(); LOGGER.debug("Visited: {}.", startNode); visited.add(startNode); queue.enqueue(startNode); BinaryTreeNode<E> node = null; BinaryTreeNode<E> leftChild = null; BinaryTreeNode<E> rightChild = null; while (!queue.isEmpty()) { node = queue.dequeue(); if (node.data().equals(value)) { return node; } leftChild = node.leftChild(); rightChild = node.rightChild(); if (leftChild != null && !visited.contains(leftChild)) { LOGGER.debug("Visited: {}.", leftChild); visited.add(leftChild); queue.enqueue(leftChild); } if (rightChild != null && !visited.contains(rightChild)) { LOGGER.debug("Visited: {}.", rightChild); visited.add(rightChild); queue.enqueue(rightChild); } } return null; }  }
Searcher { public static <E extends Comparable<E>> BinaryTreeNode<E> breadthFirstSearch(BinarySearchTree<E> binTree, BinaryTreeNode<E> startNode, E value) { LOGGER.debug("Searching for: {}.", value); Set<BinaryTreeNode<E>> visited = new HashSet<BinaryTreeNode<E>>(); Queue<BinaryTreeNode<E>> queue = new Queue<BinaryTreeNode<E>>(); LOGGER.debug("Visited: {}.", startNode); visited.add(startNode); queue.enqueue(startNode); BinaryTreeNode<E> node = null; BinaryTreeNode<E> leftChild = null; BinaryTreeNode<E> rightChild = null; while (!queue.isEmpty()) { node = queue.dequeue(); if (node.data().equals(value)) { return node; } leftChild = node.leftChild(); rightChild = node.rightChild(); if (leftChild != null && !visited.contains(leftChild)) { LOGGER.debug("Visited: {}.", leftChild); visited.add(leftChild); queue.enqueue(leftChild); } if (rightChild != null && !visited.contains(rightChild)) { LOGGER.debug("Visited: {}.", rightChild); visited.add(rightChild); queue.enqueue(rightChild); } } return null; }  static BinaryTreeNode<E> binarySearch(BinarySearchTree<E> binTree,
			BinaryTreeNode<E> startNode, E value); static BinaryTreeNode<E> binarySearch(BinarySearchTree<E> binTree, E value); static BinaryTreeNode<E> breadthFirstSearch(BinarySearchTree<E> binTree,
			BinaryTreeNode<E> startNode, E value); static BinaryTreeNode<E> breadthFirstSearch(BinarySearchTree<E> binTree, E value); static BinaryTreeNode<E> depthFirstSearch(BinarySearchTree<E> binTree,
			BinaryTreeNode<E> startNode, E value); static BinaryTreeNode<E> depthFirstSearch(BinarySearchTree<E> binTree, E value); }
Searcher { public static <E extends Comparable<E>> BinaryTreeNode<E> breadthFirstSearch(BinarySearchTree<E> binTree, BinaryTreeNode<E> startNode, E value) { LOGGER.debug("Searching for: {}.", value); Set<BinaryTreeNode<E>> visited = new HashSet<BinaryTreeNode<E>>(); Queue<BinaryTreeNode<E>> queue = new Queue<BinaryTreeNode<E>>(); LOGGER.debug("Visited: {}.", startNode); visited.add(startNode); queue.enqueue(startNode); BinaryTreeNode<E> node = null; BinaryTreeNode<E> leftChild = null; BinaryTreeNode<E> rightChild = null; while (!queue.isEmpty()) { node = queue.dequeue(); if (node.data().equals(value)) { return node; } leftChild = node.leftChild(); rightChild = node.rightChild(); if (leftChild != null && !visited.contains(leftChild)) { LOGGER.debug("Visited: {}.", leftChild); visited.add(leftChild); queue.enqueue(leftChild); } if (rightChild != null && !visited.contains(rightChild)) { LOGGER.debug("Visited: {}.", rightChild); visited.add(rightChild); queue.enqueue(rightChild); } } return null; }  static BinaryTreeNode<E> binarySearch(BinarySearchTree<E> binTree,
			BinaryTreeNode<E> startNode, E value); static BinaryTreeNode<E> binarySearch(BinarySearchTree<E> binTree, E value); static BinaryTreeNode<E> breadthFirstSearch(BinarySearchTree<E> binTree,
			BinaryTreeNode<E> startNode, E value); static BinaryTreeNode<E> breadthFirstSearch(BinarySearchTree<E> binTree, E value); static BinaryTreeNode<E> depthFirstSearch(BinarySearchTree<E> binTree,
			BinaryTreeNode<E> startNode, E value); static BinaryTreeNode<E> depthFirstSearch(BinarySearchTree<E> binTree, E value); static final Logger LOGGER; }