二叉树的存贮与读取

key

在别的论坛上见有人问这个问题，想了一下，在这里发一下自己的见解。

写一个程序，用来存贮二叉树并能读出来。

这个问题包括三点：二叉树的遍历，建立以及存贮。其中存贮是难点，主要考虑什么样的存贮方案。
我能想到的存贮方案有：

1. 最简单的存贮：把各个元素按满树的位置来存贮。这种存贮方法最大问题就是占空间多。
2. 构建存贮链接：每个存贮单元包括：根节点值，左子树位置值，右子树位置值。下面是一个例子：
R1, 1, 6, R2, 2, 5, R4, 3, 4, R8, 0, 0, R9, 0, 0, R5, 0, 0, R3, 7, 9, R6, 0, 8, R10, 0, 0, R7, 10, 0, R11, 0, 0
这种存贮方式使用了额外的两个值来存贮每个节点的左右子树的位置，所以存贮空间为：n * sizeof(R) + 2 * n * sizeof(int)
缺点是存贮算法相对复杂，对于二进制存贮比较好，因为可以随机读写记录。对文本存贮则需要在内存上先算好每棵子树的位置才能写入。
3. 编号存贮：每个子树的根节点按照其满树的位置编号，在写入硬盘时，每个节点记录为：根节点值，位置值。
这种存贮方式比较容易构建（节点编号为根树编号*2 + 0|1），存贮空间也比方法2少很多。比较适合按层遍历。

有时间把代码写上来，没时间就算了。

someonehappy

如果要考虑到存储空间的利用，是不是还应该考虑具体应用的情况？

比如说，基本没有什么更改的和删除的情况，和会有大量节点被多次的加入修改和删除的情况，应该是很不同的。特别在象你提到的如果存放的是不定长的内容，比如字符串的情况下，因为删除而被释放的空间，不见的就能被新节点使用，可能会空间不够，最终导致很多的碎片。

另外，看不太明白你说的第三种方法，什么叫作满树？还是意思是假设这个树有个最大层数的限制？

key

原帖由 someonehappy 于 20-5-2009 13:14 发表

                               
登录/注册后可看大图

如果要考虑到存储空间的利用，是不是还应该考虑具体应用的情况？

比如说，基本没有什么更改的和删除的情况，和会有大量节点被多次的加入修改和删除的情况，应该是很不同的。特别在象你提到的如果存放的是不定长的 ...

满树是一种特殊的二叉树，它除了最底的一层外，其他层都有2^(n-1)个结点。
完全二叉树则是一种特殊的满树，它的所有层，包括最底的一层都有2^(n-1)个结点。