Write a program in Java that implements the Rooted Tree with Unbound Branching:

Question

Write a program in Java that implements the Rooted Tree with Unbound Branching:
a) This tree should support multiple children nodes (not just binary tree), with the left-child
right-sibling scheme
b) The program should support a search method that can locate the first instance of the node
that holds the given key and returns true if the node is found
c) There should be an insert method that takes a parent node (key value) and the node to be
inserted as arguments: public void insert(Node parent, Node child)
d) If the parent node does not have a child, then the new node becomes the left-child.
Otherwise, it becomes the right-most child of the parent node (i.e., insert at the end)
e) Test your program by building a tree with 3 levels:
a. Use the insert method to build the tree. Call this method several times with the proper
parent and child nodes as arguments.
b. Root node has key = 10, and it has 4 children with keys 20, 30, 40, and 50 (node 20 is
the left-child)
c. The node 20 has 3 children with keys 200, 210, and 220
d. The node 30 has 2 children with keys 300 and 310
e. The node 40 has 1 child with key 400
f. The node 50 has 3 children with keys 500, 510, and 520
g. Use the search method to search for node 320 and node 510. Display the results.

Explanation / Answer

import java.util.Iterator;

public class App {
public static void main(String[] args) {

Tree tree = new Tree();

/*
* The second parameter for the addNode method is the identifier
* for the node's parent. In the case of the root node, either
* null is provided or no second parameter is provided.
*/
tree.addNode("Harry");
tree.addNode("Jane", "Harry");
tree.addNode("Bill", "Harry");
tree.addNode("Joe", "Jane");
tree.addNode("Diane", "Jane");
tree.addNode("George", "Diane");
tree.addNode("Mary", "Diane");
tree.addNode("Jill", "George");
tree.addNode("Carol", "Jill");
tree.addNode("Grace", "Bill");
tree.addNode("Mark", "Jane");

tree.display("Harry");

System.out.println(" ***** DEPTH-FIRST ITERATION *****");

// Default traversal strategy is 'depth-first'
Iterator depthIterator = tree.iterator("Harry");

while (depthIterator.hasNext()) {
Node node = depthIterator.next();
System.out.println(node.getIdentifier());
}

System.out.println(" ***** BREADTH-FIRST ITERATION *****");

Iterator breadthIterator = tree.iterator("Harry", TraversalStrategy.BREADTH_FIRST);

while (breadthIterator.hasNext()) {
Node node = breadthIterator.next();
System.out.println(node.getIdentifier());
}
}
}
TraversalStrategy.java
/*
* Copyright (C) 2007-2014 by Brett Alistair Kromkamp .
*/

package com.quesucede.tree;

public enum TraversalStrategy {
DEPTH_FIRST,
BREADTH_FIRST
}
Node.java
/*
* Copyright (C) 2007-2014 by Brett Alistair Kromkamp .
*/

package com.quesucede.tree;

import java.util.ArrayList;

public class Node {

private String identifier;
private ArrayList children;

// Constructor
public Node(String identifier) {
this.identifier = identifier;
children = new ArrayList();
}

// Properties
public String getIdentifier() {
return identifier;
}

public ArrayList getChildren() {
return children;
}

// Public interface
public void addChild(String identifier) {
children.add(identifier);
}
}

Tree.java
/*
* Copyright (C) 2007-2014 by Brett Alistair Kromkamp .
*/

package com.quesucede.tree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;

public class Tree {

private final static int ROOT = 0;

private HashMap nodes;
private TraversalStrategy traversalStrategy;

// Constructors
public Tree() {
this(TraversalStrategy.DEPTH_FIRST);
}

public Tree(TraversalStrategy traversalStrategy) {
this.nodes = new HashMap();
this.traversalStrategy = traversalStrategy;
}

// Properties
public HashMap getNodes() {
return nodes;
}

public TraversalStrategy getTraversalStrategy() {
return traversalStrategy;
}

public void setTraversalStrategy(TraversalStrategy traversalStrategy) {
this.traversalStrategy = traversalStrategy;
}

// Public interface
public Node addNode(String identifier) {
return this.addNode(identifier, null);
}

public Node addNode(String identifier, String parent) {
Node node = new Node(identifier);
nodes.put(identifier, node);

if (parent != null) {
nodes.get(parent).addChild(identifier);
}

return node;
}

public void display(String identifier) {
this.display(identifier, ROOT);
}

public void display(String identifier, int depth) {
ArrayList children = nodes.get(identifier).getChildren();

if (depth == ROOT) {
System.out.println(nodes.get(identifier).getIdentifier());
} else {
String tabs = String.format("%0" + depth + "d", 0).replace("0", " "); // 4 spaces
System.out.println(tabs + nodes.get(identifier).getIdentifier());
}
depth++;
for (String child : children) {

// Recursive call
this.display(child, depth);
}
}

public Iterator iterator(String identifier) {
return this.iterator(identifier, traversalStrategy);
}

public Iterator iterator(String identifier, TraversalStrategy traversalStrategy) {
return traversalStrategy == TraversalStrategy.BREADTH_FIRST ?
new BreadthFirstTreeIterator(nodes, identifier) :
new DepthFirstTreeIterator(nodes, identifier);
}
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.