首页 > 代码库 > 二叉树的序列化与反序列化
二叉树的序列化与反序列化
一个二叉树被序列化为数组,如何反序列化,也就是如何从序列化好的一个数组恢复成二叉树?
在上一篇文章中讲述了如何将一个有序数组创建成一个二叉搜索树,那么如果将将一个儿茶搜索树序列化为一个有序数组,然后按照上面的方法在反序列化即可。对二叉搜索树进行中序遍历即可得到一个有序的数组,那么上篇文章已经完成了对二叉搜索树的序列化和反序列化。同时如果想将二叉搜索树的序列化和反序列化的结果通过文件读取,也是同样的道理。
设计一个算法,将一棵二叉搜索树(Binary Search Tree,BST)保存到文件中,需要能够从文件中恢复原来的二叉搜索树。注意算法的时空复杂度。
如果通过文件的话,我们使用中序遍历是不合适的,因为从文件读取时顺序读取的。但是先序遍历存放到文件,然后从文件中按照依序读取,是符合要求的。
void DeSerialize(int min,int max,int& val,BinTree*& root,ifstream& fin) { int temp; if(val > min && val < max) { temp = val; root = new BinTree; root->right = NULL; root->left = NULL; root->value = http://www.mamicode.com/temp;>上面是对二叉搜索树的序列和反序列化的方法因为二叉树与二叉搜索树的性质不同,所以不能简单的采用前面文章中的方法。不过,我们可以采用先序遍历的思想,只是在这里需要改动。为了能够在重构二叉树时结点能够插入到正确的位置,在使用先序遍历保存二叉树到文件中的时候需要把NULL结点也保存起来(可以使用特殊符号如“#”来标识NULL结点)。
假定二叉树如下所示:
_30_ / \ 10 20 / / \ 50 45 35则使用先序遍历,保存到文件中的内容如下:
30 10 50 # # # 20 45 # # 35 # #
序列化二叉树
先序遍历的代码可以完成序列化二叉树的工作,不管你信不信,反正我是信了。代码如下:
void SerializeBinaryTree(BinTree *p, ostream &out) //BinaryTree是二叉树结构体,typedef struct node BinaryTree. { if (!p) { out << "# "; } else { out << p->data << " "; SerializeBinaryTree(p->left, out); SerializeBinaryTree(p->right, out); } }反序列化二叉树
从文件中读取二叉树结点并重构的方法与前面相似。采用先序遍历的思想每次读取一个结点,如果读取到NULL结点的标识符号“#”,则忽略它。如果读取到结点数值,则插入到当前结点,然后遍历左孩子和右孩子。
void readBinaryTree(BinTree *&p, ifstream &fin) { int token; bool isNumber; if (!readNextToken(token, fin, isNumber)) //readNextToken读取文件下一个值,如果是数字返回true,否则返回false return; if (isNumber) { p = new BinTree; p->value = http://www.mamicode.com/toekn; //newNode函数创建新结点,设定data为token,left和right初始化为NULL >
二叉树的序列化与反序列化
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。