Building general trees in java (with recursion)
I have neglected the order for now, and just given an Tree.insert(parentData, data)
.
With the hope that this helps getting you started.
public class Node<T> {
private T data;
private List<Node<T>> children;
Node<T> find(T data) {
if (this.data.equals(data)) {
return this;
}
for (Node<T> node : children) {
Node<T> found = node.find(data);
if (found != null) {
return found;
}
}
return null; // Not found.
}
public class Tree<T> {
public find(T data) {
return root == null ? null : root.find(data);
}
public boolean insert(T parentData, T data) {
Node<T> found = find(parentData);
if (found == null) {
return false;
}
found.getChildren().add(new Node(data));
return true;
}
As one sees, having a find(data)
method for retrieving the (parent) Node helps.
The search method find
here disregards any sorting of the values, and does a preorder search.
As far as order is concerned, normally on has nodes of the form:
class Node<T> {
List<Node<T>> children; // 0, 1, ... N
List<T> values; // 0, 1, ... N-1
}
With an sort ordering:
children[0]
values[0}
children[1}
values[0]
children[2]
...
children[N-1]
values[N-1]
children[N]
One might retain the values in the entire tree in this order. Sorting and preorder/postorder walks and bread fírst/depth first walks are different notions.
Admin
Updated on June 05, 2022Comments
-
Admin almost 2 years
I have been stuck on a problem for quite a few days. My end goal is to perform preorder, inorder, and postorder traversals on a general tree. The problem I am having is just populating the tree. I am only able to add nodes to the root and to the root's children. I am not able to move "down" past the roots children. I woke up one morning with the idea of building the tree recursively from a bottom-up approach. I have never used recursion so first of all, is this possible? I would basically build the tree by creating the nodes at the bottom of the tree and then work my way up?
Here is my node class:
//Represents node of the Tree<T> class public class Node<T> { public T data; public List<Node<T>> children; //Default constructor public Node() { super(); children = new ArrayList<Node<T>>(); } public Node(T data) { this(); setData(data); } //Return the children of Node<T> public List<Node<T>> getChildren() { if(this.children == null) { return new ArrayList<Node<T>>(); } return this.children; } //Sets the children of a Node<T> object public void setChildren(List<Node<T>> children) { this.children = children; } //Returns the number of immediate children of this Node<T> public int getNumberOfChildren() { if(children == null) { return 0; } return children.size(); } //Adds a child to the list of children for this Node<T> public void addChild(Node<T> child) { if(children == null) { children = new ArrayList<Node<T>>(); } children.add(child); } public void addChildAt(int index, Node<T> child) throws IndexOutOfBoundsException { if(index == getNumberOfChildren()) { addChild(child); return; } else { children.get(index); children.add(index, child); } } public boolean isLeaf() { if(getNumberOfChildren() == 0) return true; return false; } public T getData() { return this.data; } public void setData(T data) { this.data = data; } public String toString() { StringBuilder sb = new StringBuilder(); sb.append("{").append(getData().toString()).append(",["); int i = 0; for(Node<T> e : getChildren()) { if(i > 0) { sb.append(","); } sb.append(e.getData().toString()); i++; } sb.append("]").append("}"); return sb.toString(); } }
Here is my tree class:
//Tree class public class Tree<T> { private Node<T> root; //Default constructor public Tree() { super(); } //Returns the root public Node<T> getRoot() { return this.root; } //Set the root of the tree public void setRoot(Node<T> root) { this.root = root; } //Returns the Tree<T> as a List of Node<T> objects public List<Node<T>> toList() { List<Node<T>> list = new ArrayList<Node<T>>(); walk(root, list); return list; } //String representation of ttree public String toString() { return toList().toString(); } //Preorder traversal private void walk(Node<T> element, List<Node<T>> list) { list.add(element); for(Node<T> data : element.getChildren()) { walk(data, list); } } }
This is my main driver program:
//Importing packages import java.util.Scanner; import java.util.StringTokenizer; import java.io.*; import java.io.BufferedReader; import java.util.List; import java.util.ArrayList; //Class header public class treeTraversals { //Main method public static void main (String[] args) throws IOException { //Defining variables String file; int size = 0; int id = 1; int counter = 1; Scanner keyboard = new Scanner(System.in); //Request file System.out.print("Enter the filename: "); file = keyboard.nextLine(); //Read file File treeFile = new File(file); Scanner inputFile = new Scanner(treeFile); BufferedReader reader = new BufferedReader(new FileReader(file)); //Find size of input file while(reader.readLine() != null) { size++; } reader.close(); String[] parent = new String[size+1]; String[] child = new String[size+1]; //Add file vaules to arrays while(inputFile.hasNext()) { String line = inputFile.nextLine(); StringTokenizer st = new StringTokenizer(line); while(st.hasMoreTokens()) { String previousValue = st.nextToken(); String nextValue = st.nextToken(); parent[counter] = previousValue; child[counter] = nextValue; counter++; } } System.out.println(); //Output to the screen System.out.println("The Tree"); System.out.println(); for(int l = 1; l <= size; l++) { System.out.print(parent[l] + " "); System.out.println(child[l]); } //Create the root of the tree Tree tree = new Tree(); Node root = new Node(parent[id]); tree.setRoot(root); Node active = new Node(); //Fill tree with nodes for(id = 1; id <= size; id++) { Node parentNode = new Node(parent[id]); Node childNode = new Node(child[id]); active = root; int passage = 0; //Adds children to the root node if(parentNode.getData().equals(active.getData())) { active.addChild(childNode); System.out.println(tree.toList()); } //Adds children to the root's children else if(!parentNode.getData().equals(active.getData())) { boolean marked = false; int i = -1; int n = 0; while(i != active.getNumberOfChildren() && marked == false && n <= 2) { active = root; active = (Node)active.getChildren().get(n); if(active.getData().equals(parentNode.getData())) { active.addChild(childNode); marked = true; } i++; n++; } active = root; if(n >= 3 && marked == false) { for(int p=0; p < active.getNumberOfChildren(); p++) { active = (Node)active.getChildren().get(p); if(active.getData().equals(parentNode.getData())) { active.addChild(childNode); //p++; marked = true; } else { active = root; active = (Node)active.getChildren().get(p); active = (Node)active.getChildren().get(p); if(active.getData().equals(parentNode)) { active.addChild(childNode); System.out.println("No"); p = 0; } } } } } //See the nodes in the tree System.out.println(tree.toList()); } } }
Lastly, here is the text file that is provided:
a b a c a d b e b f d g d h d i e j e k g l g m k n k o k p
Please, any help would be appreciated, I'm stuck on my own approach so I'm asking: how would I even start if I'm going with a recursive approach?