讨论: 关于二叉树的永久化问题

ekil

大家好
我前一段时间帮朋友做比设时,程序的据是用二叉树时组织的

程序退出时要将这个二叉树保存, 程序起动时又将它读入内存, 且要和原的那个树的结构一样!

我用的办法是:
1.先对这个二叉树时很填充,将它填充成完全的,空白部分用空结点填充
                 (注:我的这棵树只有0.001的可能性是完全二叉树)
2.将填充后的二叉树保存(广度优先,也就是一层一层的将数据联续保存)
   
3.程序起动时将数据读进来(按须将数据读入),建成完全二叉树,再把其
               中的空结点取了,就可以恢复成我原来的那个树了


我这个方法是可以实现对二叉树的永久化,但是,我的树一般不可能是一个完全二叉树,所以我现在想找一个更有效的办法,,然后写一个二叉树的类,以后用到时就可以直接用了

当时时间太急,我没有太多的去优化,这几天没事,就把这个问题想了一下,但也想不出个办法来,就想和大家一起讨论一下.

oustar

很有搞头的问题。主要是如何有效的保存二叉树的形状信息。

大家都GOOGLE一下。然后在进行讨论。

JohnBull

可以用:
((L)(R))
这种语法表示.比如:

1. (((asdw)(rerer))((()(sdfsd))()))

复制代码

应该不难吧?

自己设计一个8bit转6bit的编码,把任意数据变为变成ASCII格式.

ekil

to: JohnBull
把你的方法说的细一吗~
我不是很明白,

今晚我不下线,大家有什么好方法一起来说一下

BingbingNorth

ekil兄:
我有一个很通俗的办法,二叉树的扫描分前序、中序、后序三种，任意两种组合都能将一棵树表示出来。当然，每一个节点的值不用存两次。

另外，如果二叉树的空间是您给分配的线性表，那么只要将左右子树的指针改为偏移量，就能直接保存了，共享内存中的树一般就是这么做。

windflowers1976

有这样一种做法，可以保存一颗多叉树。
比如，根节点存成 TREE.ROOT，文件里面除了ROOT的内容之外，再存放下N个子节点的文件名称，如TREE.1 TREE.2 ...
在TREE.1 中有TREE.11, TREE.12 。。。

我看到的实现代码就是通过一个递归的函数，就可以读入文件表示的多叉树。当然，内存吃了不少。

是确实可用的代码，思路仅供参考。

flw

修改树的指针，使之变成文件的偏移量，就可以了。
另外，JohnBull 的方法很不错。

patrick007

johnbull的方法似乎只能记录叶子结点的信息
记录树时有个类似的方法，可能johnbull就是这意思，就是用广义表：
表头放子树根
a
| \
b  c
| \  \
d  e  f
可写成（a(b(d,e),c(,f))）,注意f为右孩子，
应该还可以写成(a(b((d)(e))c(()(f)))，这种形式可以写到文件里吧，只不过在读取恢复时，算法会比较复杂，要匹配括号，而且无形中增加了括号这个符号，等于浪费空间，不过硬盘空间也不太在乎这个吧，真不如你原来的方法。
flw那中方法感觉上可以,不过在进行恢复时，你这个算法也很麻烦，我想需要回溯，而且是要保存到文件里，应该有个具体表示，结构体什么的我想基本用不上，可以写成个3行或4行的某种数组，每行记录结点值，左孩偏移，右孩偏移，还可以加上父结点偏移。这种方法也会有许多辅助的符号出现，只当你空结点十分多时才可能节省空间，所以不建议使用。
你原来的方法容易实现，而且如果你允许浪费空间的话，可以坚持它。

ekil

哈哈，看各位的几篇贴了，胜过读一本数据结构书

楼上几位朋友的想法我明白了

谢谢

ekil

啊，不过如果大家还有别的方法还可以继续讨论

我一会要去上课了

喜望晚上回来能在这看到更多惊喜.........