Reputation: 1543
Building Tree Using List of Objects
My assignment was to take a list of 5 books, each containing a title and a rating and turn them into a tree that looks like this:
//1 1984
// 2 Animal Farm
// 3 Crime and Punishment
// 3 Demons
// 2 War and Peace
The lower ratings take precedence in terms of the hierarchical tree structure.
I made a class called book:
public static class Book {
protected int rating;
protected String title;
public Book (int rating, String title) {
this.rating = rating;
this.title = title;
}
}
I then made a Node class, which will make up the tree:
public static class Node {
protected Book book;
protected List<Node> children;
public Node(Book book) {
this.book = book;
this.children = new ArrayList<>();
}
}
My main method then looks like this:
public static void main (String[]args) throws Exception {
BufferedReader br = new BufferedReader (new InputStreamReader(System.in));
List<Book> books = new ArrayList<>();
books.add(new Book(1,"1984"));
books.add(new Book (2,"Animal Farm"));
books.add(new Book (3,"Crime and Punishment"));
books.add(new Book (2,"War and Peace"));
books.add(new Book (3,"Demons"));
Node node = createTree(books);
}
Finally, this is where I'm running into the most issues, building the actual tree. It can simply have print statements but I'm confused as to the best way to tackle this:
public static Node createTree(List<Book>books) {
Node root = new Node (books.get(0));
root.children.add(root);
//The first node will be 1984 with a 1 rating. After that I'm not sure what exactly to do next?
return root;
}
I know it seems like I'm simply looking for an answer but I literally have been building this thing all day, tried everything, and am at a dead end. I know that the solution can probably be solved recursively but I'm have troubling wrapping my brain around how it could work in the createTree() method again. Any help would be appreciated. Thank you so much.
Upvotes: 1
Views: 1700
Answers (3)
Reputation: 9651
Here is a very simple way to produce the tree you want for this particular example:
private static Node createTree(List<Book> books) {
Node root = new Node(null);
addTrees(root, books, 1);
return root;
}
private static void addTrees(Node node, List<Book> books, int rating) {
int i = 0;
while (i < books.size()) {
Book book = books.get(i);
if (book.rating == rating) {
node.children.add(new Node(book));
books.remove(i);
} else {
++i;
}
}
if (!node.children.isEmpty()) {
addTrees(node.children.get(0), books, rating+1);
}
}
And methods the print the tree:
private static void printTree(Node node) {
if (node.book != null) {
printBook(node.book);
}
for (Node child: node.children) {
printTree(child);
}
}
private static void printBook(Book book) {
for (int i = 1; i < book.rating; ++i) {
System.out.print(" ");
}
System.out.println(book.rating + " " + book.title);
}
Upvotes: 2
Reputation: 109547
One starts with something like:
public static Node createTree(List<Book> books) {
Node tree = null;
...
return tree;
}
How would one do it?
Suppose the last node inserted was one with rating 4:
/-->1-->3-->*4*
If the rating is not larger than 3, say 2, go up to smaller than 2.
/-->1-->*+2* going up 2 nodes, inserting 2
/-->1-->3-->*+4* going up 1 node, inserting 4
/-->1-->3-->4-->*+6* inserting 6
As you see, one needs a stack of nodes representing the last path from the root.
In pseudo-code:
for (Book book : books) {
while (!path.isEmpty()
&& book.rating >= path.last().book.rating) {
path.removeLast();
}
Node node = new Node(book);
if (path.isEmpty()) {
tree = node;
} else {
path.last().children.add(node);
}
path.add(node);
}
You must consider the root: a tree can have only one root, one rating 1. Or you make an artifical (predefined) root with rating 0, so more than one rating 1 is possible.
Upvotes: 1
Reputation: 620
I'm slightly unfamiliar with tree-structures with more than 2 nodes. I'm thinking that a Min-Heap - a complete binary tree in which the value in each internal node is lesser than or equal to the values in the children of that node - could probably accomplish the same thing by manipulating how the tree traversal is handled.
In any case, assuming the tree can have more than 2 leaves, the following solution should help you:
There are 3 main cases the add method needs to take care of besides if the root is null:
Case 1: The book rating is less than the current nodes rating, append the new node at the position of the current node and add the current node as a leaf to the new node instead.
Case 2: The book rating is greater than the current node rating. Check to see if the node has any leaves, if it has no leaves we add the book as a leaf to the current node and return. If it has a leaf, we enter the first leaf as argument and call the add method again (recursion).
Case 3: The book rating is equal to the current nodes rating. First, if the visited node was the root of the tree, add the new node as a leaf to the tree at index 0. Iterate through all leaves of the root node and add all leaves that are not equal to the book rating as a leaf to the new node instead. Secondly, if it wasn’t the root node, then get the parent of the current node and add the new node as a leaf to that node.
Note that whenever the tree needs to be rebalanced the leaves are all apppended to the leaves of the first leaf (leaves.get(0)). Secondally the first leaf is the primary holder of the sub-tree.
The toString method uses a pre-order iteration and keeps track of the depth it is on to print the tree.
public class Tree {
private static class Node {
Book book;
List<Node> leaves;
Node parent;
public Node(Book b, Node p) {
this.book = b;
this.leaves = new LinkedList<>();
this.parent = p;
}
@Override
public String toString() {
return book.toString();
}
}
private Node root;
private void swap(Node oldParent, Node newParent) {
oldParent.leaves.add(newParent);
newParent.parent = oldParent.parent;
oldParent.parent = newParent;
newParent.leaves.add(oldParent);
oldParent.leaves.remove(newParent);
if (newParent.parent != null) {
newParent.parent.leaves.add(0, newParent);
newParent.parent.leaves.remove(oldParent);
}
if (oldParent == root) {
root = newParent;
// Handle special scenario when the leaf of the root and the leaf of the the leaf
// have the same value and then rebalance the leaves.
if (!oldParent.leaves.isEmpty() && !newParent.leaves.isEmpty()) {
Node n2 = oldParent.leaves.get(0);
Node n1 = newParent.leaves.get(0);
if (n1.book.rating != n2.book.rating)
return;
root.leaves.add(0, n2);
n2.parent = root;
n1.leaves.clear();
}
}
}
private void add(Node n, Book b) {
System.out.println("@" + b.toString());
int prevNodeRating = n.book.rating;
if (b.rating < prevNodeRating) {
swap(n, new Node(b, n));
}
else if (b.rating > prevNodeRating) {
if (n.leaves.isEmpty()) {
Node newNode = new Node(b, n);
n.leaves.add(newNode);
} else {
add(n.leaves.get(0), b);
return;
}
}
else {
if (n == root) {
if (!n.leaves.isEmpty() && n.leaves.get(0).book.rating == b.rating) {
root.leaves.add(new Node(b, n));
return;
}
Node newNode = new Node(b, n);
n.leaves.add(0, newNode); // set at first position
Iterator<Node> itr = n.leaves.iterator();
itr.next(); // skip first;
while (itr.hasNext()) {
Node leaf = itr.next();
if (leaf.book.rating >= b.rating) {
newNode.leaves.add(leaf);
leaf.parent = newNode;
itr.remove();
}
}
} else {
n.parent.leaves.add(new Node(b, n.parent));
}
}
System.out.println(toString() + "\n----------------");
}
public void add(Book b) {
if (root == null)
root = new Node(b, null);
else add(root, b);
}
private void toStringItr(Node n, int lvl, StringBuilder sb) {
if(n == null) return;
for (int i = 0; i < 3*lvl; i++) {
sb.append(" ");
}
sb.append(n.book.toString()).append("\n");
n.leaves.forEach((leaf) -> {
toStringItr(leaf, lvl + 1, sb);
});
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
if (root == null)
return "null";
toStringItr(root, 0, sb);
return sb.toString();
}
}
INPUT
Tree mt = new Tree();
mt.add(new Book(4,"A"));
mt.add(new Book(3,"B"));
mt.add(new Book(2,"C"));
mt.add(new Book(3,"D"));
mt.add(new Book(1,"E"));
mt.add(new Book(4,"F"));
mt.add(new Book(1,"G"));
mt.add(new Book(2,"H"));
mt.add(new Book(8,"X"));
mt.add(new Book(7,"Y"));
System.out.println(mt.toString());
OUTPUT
1, E
1, G
2, C
3, B
4, A
7, Y
8, X
4, F
3, D
2, H
Alternativly,
1, 1984
2, Animal Farm
3, Crime and Punishment
3, Demons
2, War and Peace
Step by step output (after first root)
@3, B
3, B
4, A
----------------
@2, C
2, C
3, B
4, A
----------------
@3, D
@3, D
2, C
3, B
4, A
3, D
----------------
@1, E
1, E
2, C
3, B
4, A
3, D
----------------
@4, F
@4, F
@4, F
@4, F
1, E
2, C
3, B
4, A
4, F
3, D
----------------
@1, G
1, E
1, G
2, C
3, B
4, A
4, F
3, D
----------------
@2, H
@2, H
@2, H
1, E
1, G
2, C
3, B
4, A
4, F
3, D
2, H
----------------
@8, X
@8, X
@8, X
@8, X
@8, X
1, E
1, G
2, C
3, B
4, A
8, X
4, F
3, D
2, H
----------------
@7, Y
@7, Y
@7, Y
@7, Y
@7, Y
@7, Y
1, E
1, G
2, C
3, B
4, A
7, Y
8, X
4, F
3, D
2, H
----------------
Upvotes: 2
Related Questions
- Building A Tree Like Structure
- Creating Swing Tree from Array list
- building tree from input data
- How to implement a binary tree structure with objects?
- Java: Tree Creation
- Create a dynamic tree in java
- Is it possible to create a tree of objects in Java?
- To develop a Tree Structure
- TreeModel backed by Lists
- Building a tree in Java