二叉树的保存
在我学习保存二叉树时，接触到的是利用数组（列表）、字符串或者是链表的方法来保存，将完全二叉树按照从上到下，从左到右的顺序将节点的名字依次排序。在没有节点的地方则是用0（#）来代替。之后再使用“先序序列”，“中序序列”，“后序序列”方法进行还原、遍历。我们发现当二叉树足够大时会出现大量的0。
利用压缩原理储存
在我想如何解决0带来的额外的内存占用，首先想到的是我在学习压缩包压缩时的方法。计算机是使用二进制的，将连续的0和1用数量来代替。比如00011000会被保存为3个0，两个1，三个0。
假设有一个二叉树{‘A’,‘B’,0,‘C’,‘D’,0,0}，利用这种思想就简化为{‘A’,‘B’,‘10’,‘C’,‘D’,'20’}。在此可能不会省空间，甚至会浪费空间，但在树足够大，0足够多时，则会节省很多空间。
利用空节点之下必然无节点
众所周知空节点之下是无节点的，我们就可以利用这种规律将除了第一个空节点用零记录下来。而由这个空节点衍生出来的空节点就不作记录。
比如有一个二叉树{‘A’,‘B’,‘C’,‘D’,‘E’,0,‘F’,‘G’,‘H’,0,‘I’,0,0,‘J’,'K,‘L’,‘M’,‘N’,‘O’}利用这种思想就简化成{‘A’,‘B’,‘C’,‘D’,‘E’,0,‘F’,‘G’,‘H’,0,‘I’,‘J’,'K,‘L’,‘M’,‘N’,‘O’}
在此只作为一种思想提供，这是本人在学习中独立想到的。如有雷同纯属巧合。未经作者允许禁止转载。
|