时间戳

首页 > 解决方案 > 如何使用给定的类从字符串数组实现二叉树，然后对其进行序列化、反序列化和遍历？

java - 如何使用给定的类从字符串数组实现二叉树，然后对其进行序列化、反序列化和遍历？

问题描述

我的数据结构类有一个编码项目，但我正在努力从哪里开始。作业问这个：

使用数组表示和节点标签 A、...、J 作为字符串将二叉树输入为数组。标签 null 代表不存在的节点，而不是具有 null 值的节点。检查二叉树输入的有效性：每个节点，除了根，都应该有一个父亲。生成树的动态内存实现，仅使用标签不为空的节点。将获得的 BinaryTree 对象保存为文件，使用序列化。反序列化文件以恢复树。对恢复的树执行前序、后序和中序树遍历，并列出访问节点的标签。创建单元测试并实现一个测试类。

我得到一个二叉树类：

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) {
}
}

如果可能的话，我希望将其分解为更小的步骤，因为我不确定从哪里开始。另外，我没有序列化的经验。

我不是要代码，只是一个指南。

标签： javabinary-tree

解决方案

  • 假设字符串索引与节点的关系为left child = 2 * parent index + 1和right child = 2 * parent index + 2。

  • 现在字符串以形式给出"A, B, ..., J"，您可以将字符串拆分为一个数组，其中arr[0] = A和arr[N] = J

  • 每个元素本身都是一棵大小为 1 的树，它们是包含所有元素的大树的子树。

  • 基于索引，迭代或递归地将它们添加到一棵大树中。例如，、arr[0] = A = root等。忽略空节点，现在你有一个最终的树。arr[1] = left child = B // because 1 = 2 * 0 + 1arr[2] = right child = C // because 2 = 2 * 0 + 2

推荐阅读