CODEWITHSUNDEEP
javabinary-tree
CyberknightMk1
CyberknightMk1

Reputation: 61

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

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.

Upvotes: 0

Views: 634

Answers (1)

Hung Vu
Hung Vu

Reputation: 633

  • 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.

Upvotes: 1

Related Questions