实验2 非线性结构及相关算法的设计与应用1
需积分: 0 101 浏览量
2022-08-08
21:20:52
上传
评论
收藏 103KB DOCX 举报
实验 2: 非线性结构及相关算法的设计与应用
第 1 部分：二叉树的连式存储、序列化和反序列化（4 学时）
实验内容：二叉树是由结点指针将多个结点关联起来的抽象数据结构，
是存在于内存中的，不能进行持久化，如果需要将一颗二叉树的结构
持久化保存在磁盘文件中，需要将其转换为字符串并保存到文件中。
所谓序列化是对二叉树进行先序遍历产生一个字符序列，与一般的先
序遍历不一样，需要记录空结点用#字符表示，并且假设序列中没有
结点的值为#。如下图所示的序列化存储为：A,B,#,C,#,#,D,#,E,F,#,#,#
所谓反序列化就是通过先序序列化的结果串 str 构建对应的二叉
树，其过程是用 i 从头扫描 str；采用先序方法，当 i 超界时返回
NULL；否则当遇到#字符时返回 NULL，当遇到其它字符时，创建一
个结点，可以采用递归的方法构造该二叉树；也可以采用非递归方法
构造该二叉树。
（1）采用二叉链式存储创建二叉树 B1；
（2）采用先序序列化显示输出序列，并存储到文件中；
（3）从文件中读出序列，并反序列化的递归方法构造二叉树 B2；
评论0