How to implement a binary tree from a string array using a given class and then serialize, deserialize, and traverse it?

Question

I have a coding project for my data structures class but I am struggling with where to start. The assignment asks this:

Input your binary tree as an array, using the array representation and node labels A, ..., J, as Strings. Label null stands for a non-existent node, not for a node having a value of null. Check the validity of your binary tree input: each node, excepting the root, should have a father. Generate the dynamic memory implementation of the tree, using only the nodes with labels different than null. Save the obtained BinaryTreeobject as a file, using serialization. Deserialize the file to restore the tree. Perform a preorder, a postorder, and an inorder tree traversal of the restored tree and list the labels of the visited nodes. Create unit tests and implement a test class.

I am given a binary tree class:

public class BinaryTree<T> implements java.io.Serializable
{    
private T data;
private BinaryTree<T> left;
private BinaryTree<T> right;
public BinaryTree(T data) 
{ 
this.data = data; 
left = null; 
right = null;
} 
public T getData() 
{
return data;
}    
public void attachLeft(BinaryTree<T> tree) 
{ 
if (tree != null) left = tree; 
}    
public void attachRight(BinaryTree<T> tree)
{
if (tree != null) right = tree;
}   
public BinaryTree<T> detachLeft() 
{ 
BinaryTree<T> t = left; 
left = null; 
return t;  
} 
public BinaryTree<T> detachRight() 
{ 
BinaryTree<T> t = right;
right = null;
return t;
}     
public boolean isEmpty()
{ 
return data == null;
}    
public void inOrder(BinaryTree <T> tree)   
{        
if ( tree != null) 
{   
inOrder(tree.left);
System.out.println(tree.getData());
inOrder(tree.right); 
}    
}
public void preOrder(BinaryTree <T> tree)
{
}
public void postOrder(BinaryTree <T> tree) {
}
}

I would like this to be broken down into smaller steps if possible as I am not sure where to begin. Also, I have no experience with serialization.

I am not asking for code, just a guide through this.

You don't need to do anything special to your class to make it serialize; just use ObjectOutputStream. A quick web search for that should turn up lots of examples. — Bohemian
– Bohemian ♦, Commented Sep 11, 2020 at 2:59

Hung Vu · Accepted Answer · 2020-09-11 01:42:50Z

1

Assuming the relation ship of string index vs. node is left child = 2 * parent index + 1 and right child = 2 * parent index + 2.
Now the string is given in the form "A, B, ..., J", you can split the string in to an array where arr[0] = A and arr[N] = J
Each element itself is a tree of size 1, and they are a sub tree of the big one which contains all element.
Base on the index, iteratively or recursively add them to a big tree. For example, arr[0] = A = root, arr[1] = left child = B // because 1 = 2 * 0 + 1, arr[2] = right child = C // because 2 = 2 * 0 + 2 and so on. Ignore the null nodes, now you have a final tree.

answered Sep 11, 2020 at 1:42

Hung Vu

6336 silver badges17 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

How to implement a binary tree from a string array using a given class and then serialize, deserialize, and traverse it?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related