java - 从字符串加载二叉树(parent-left-right)

Question

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

代表它的对象看起来像这样(java)

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

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

然后我阅读它并将它作为一个列表 - 对象按 O,A,C,D,E,F,B 的顺序

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

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

Answer 1

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

鉴于您的第一个陈述，恢复数据仍然是可能的。一种分解级别信息的算法如下:

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

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