4

我有一个看起来像这样的二叉树

在此处输入图像描述

代表它的对象看起来像这样（java）

 public class node {
   private String value = "";
   private TreeNode aChild;
   private TreeNode bChild;
 ....
 }

我想读取数据并从字符串构建树。
所以我写了一些小方法来序列化它，我有这样
的 (parent-left-right)
0,null,O@1,left,A@2,left,C@3,left,D@4,left, E@4,右,F@1,右,B@

然后我读了它，我把它作为一个列表 - 按 O、A、C、D、E、F、B 顺序排列的对象

现在我的问题是 - 我如何构建树？
迭代并将其放入堆栈，队列？
我应该以不同的顺序序列化吗？

（基本上我想学习从字符串数据构建树的最佳实践）
你能推荐我到那个主题的链接吗？

4

2 回答 2

0

您的序列化没有得到很好的解释，特别是关于您如何表示缺失的节点。有几种方法，例如用 () 表示树结构或在数组技术中使用二叉树。这两个都可以很容易地序列化。查看二叉树的高效阵列存储以获得进一步的解释。

于 2012-07-21T23:59:36.853 回答
0

鉴于您的第二个字符串表示，没有办法检索原始树。因此，除非任何具有该序列的树都是可接受的，否则您必须在字符串中包含 mor 信息。一种可能的方法是以某种方式表示null引用。另一个将使用括号或类似的。

鉴于您的第一个表示，恢复数据仍然是可能的。一种解释级别信息的算法如下：

  • 保持对树中当前位置的引用x
  • 对于要添加的每个节点n，只要x的级别不小于n的级别，就在树中将该引用x向上移动
  • 检查现在x的水平正好比n的水平小一
  • 使x成为n的父级，并且n成为x的下一个子级
  • 将x移动到现在指向n

如果您的节点中有父链接，则此方法有效。如果您不这样做，那么您可以维护每个级别的最新节点列表。然后x将对应于该列表的最后一个元素，并且将x向上移动意味着从列表中删除最后一个元素。x的级别将是列表的长度。

于 2012-07-21T23:44:44.013 回答