- Program 3 Serialize A Tree Given The Ntree Class Write Methods Serialize And Deserialize Which Write The Tree To A T 1 (25.67 KiB) Viewed 40 times
tomorrow. Please use Java language and provide a comment for what
each part of the code does. Please test by compiling and run the
code and please give the output.
Here's the given Ntree class.
import java.util.*;
public class NTree {
protected class Node {
E data;
Node parent;
List children;
protected Node(E data) {
this.data =
data;
this.children =
new ArrayList();
}
protected void addChild(Node c)
{ children.add(c); }
public boolean equals(Node rhs)
{
return
this.data.equals(rhs.data);
}
}
protected Node root;
public NTree() {}
public NTree(List values, List parents) throws
Exception {
if (values.size() !=
parents.size()) throw new Exception();
Map m = new
TreeMap<>();
for (int i = 0; i <
values.size(); i++) {
Node nd = new
Node(values.get(i));
m.put(values.get(i), nd);
if
(parents.get(i) >= 0) { // -1
signals root
nd.parent =
m.get(values.get(parents.get(i)));
nd.parent.addChild(nd);
}
else root =
nd;
}
}
public boolean equals(NTree rhs) {
return equals(root,
rhs.root);
}
protected boolean equals(Node lhs, Node rhs)
{
if (lhs == null || rhs == null)
return lhs == rhs;
if (!lhs.equals(rhs) || lhs.parent
!= rhs.parent) return false;
for (int i = 0; i <
lhs.children.size(); i++) {
if
(!equals(lhs.children.get(i), rhs.children.get(i))) return
false;
}
return true;
}
public void serialize(String fname) {}
public void deserialize(String fname) {}
public static void main(String [] args) {
try {
List food = Arrays.asList("Food",
"Plant", "Animal", "Roots", "Leaves", "Fruits", "Fish", "Mammals",
"Birds", "Potatoes", "Carrots", "Lettuce", "Cabbage", "Apples",
"Pears", "Plums", "Oranges", "Salmon", "Tuna", "Beef", "Lamb",
"Chicken", "Duck", "Wild", "Farm", "GrannySmith", "Gala");
List foodparents =
Arrays.asList(-1, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 5, 5, 5, 5,
6, 6, 7, 7, 8, 8, 17, 17, 13, 13);
NTree foodtree = new NTree(food,
foodparents);
foodtree.serialize("foodtree.out");
NTree foodtree2 = new
NTree<>();
foodtree2.deserialize("foodtree.out");
System.out.println(foodtree.equals(foodtree2));
List intvalues =
Arrays.asList(9, 6, 5, 4, 2, 10, 7, 1, 3, 8, 11, 12, 13, 14);
List intparents = Arrays.asList(
-1, 0, 1, 1, 1, 2, 2, 2, 3, 3, 8, 8, 8, 8);
NTree inttree = new
NTree<>(intvalues, intparents);
NTree inttree2 = new
NTree<>();
inttree.serialize("inttree.out");
inttree2.deserialize("inttree.out");
System.out.println(inttree.equals(inttree2));
} catch (Exception e) {
e.printStackTrace();
}
}
}
Here's the foodtree.out:
Food
Food Plant
Food Animal
Food Plant Roots
Food Plant Leaves
Food Plant Fruits
Food Animal Fish
Food Animal Mammals
Food Animal Birds
Food Plant Roots Potatoes
Food Plant Roots Carrots
Food Plant Leaves Lettuce
Food Plant Leaves Cabbage
Food Plant Fruits Apples
Food Plant Fruits Pears
Food Plant Fruits Plums
Food Plant Fruits Oranges
Food Animal Fish Salmon
Food Animal Fish Tuna
Food Animal Mammals Beef
Food Animal Mammals Lamb
Food Animal Birds Chicken
Food Animal Birds Duck
Food Animal Fish Salmon Wild
Food Animal Fish Salmon Farm
Food Plant Fruits Apples GrannySmith
Food Plant Fruits Apples Gala
Program 3: Serialize a tree Given the NTree class, write methods serialize and deserialize , which write the tree to a text file and read it back. Compile and test your code. "foodtree.out" gives an example of a serialized format that is inefficient in time and space. Implement a better version for extra credit.