树结构的存储

面试题:

怎样把一棵树存到文件中,然后读入恢复为原来的树。以二叉树为例。

在面试官提示了“把树变成一维”后我尝试用非递归遍历结果还是没写出来(真是自己作死,干嘛要用非递归呢)
回到学校看了一下学数据结构时书上的代码。首先需要创建一棵树,书上是设置了一个不可能出现在树中的值作为结束符,用先根序列输入创建树。比如

可以用(-1,[1,2,4,-1,-1,5,-1,-1,3,-1,-1])来创建。
恩,那就简单了,存储时只需要把这个序列和结束符存起来就行了呗。写完后才发现这题这么简单……

数据结构教材上创建树是用cin读取输入,我改成了从数组读入。

首先是节点的定义:

然后是树的定义:

运行结果:

二叉树的存储-demo-效果
二叉树的存储-demo-效果

保存的文件内容是:

二叉树的存储-demo-保存的文件的内容
二叉树的存储-demo-保存的文件的内容

原来没有clazz那个变量保存泛型参数的类型,这样的话,保存的任意类型都可以读入到任意参数类型的树中,因为运行时泛型都擦除为了Object。所以增加了一个clazz变量保存泛型参数的类型,在恢复时检查是否类型匹配。

参考:


“树结构的存储”的3个回复

Loading...

发表评论

电子邮件地址不会被公开。 必填项已用*标注