python二叉树的序列化该怎么理解

本篇文章给大家分享的是有关python二叉树的序列化该怎么理解,小编觉得挺实用的,因此分享给大家学习,希望大家阅读完这篇文章后可以有所收获,话不多说,跟着小编一起来看看吧。

网站建设哪家好,找创新互联建站!专注于网页设计、网站建设、微信开发、重庆小程序开发、集团企业网站建设等服务项目。为回馈新老客户创新互联还提供了文峰免费建站欢迎大家使用!

设计一个算法,序列化和反序列化一棵二叉树。

解释:序列化的意思是将内存中的一些特定的结构,变成有格式信息的字符串。

如,对于链表而言,我们可以将1->2->3->NULL这样的链表序列化为"1,2,3"。对于序列化算法,必须支持反序列化,及在约定的格式下,可以将满足格式要求的字符串重新构造为想要的结构。

答:

使用BFS。对于下面这棵二叉树:

1

/ \

2 3

/ \

4 5

BFS序为:[1,2,3,4,5]。如果我们将叶子节点的左右儿子用#来表示的话,可以得到下面这棵树:

1

/ \

2 3

/ \ / \

# # 4 5

/ \ / \

# # # #

一行一行看可以得到:[1,2,3,#,#,4,5,#,#,#,#]

去掉尾部连续的#,可以得到[1,2,3,#,#,4,5],这样就完成了使用BFS来序列化。

同样的,我们也可以使用DFS进行序列化,DFS序列化的结果如下:[1,2,#,#,3,4,#,#,5,#,#],去掉末尾的#得到[1,2,#,#,3,4,#,#,5],要比BFS序列化的结果要长。原因主要在于大部分的#出现在最底层,所以BFS的方式可以使得尽量多的#都在序列化的尾部。

面试官角度:

所谓的序列化,是将一个结构化的东西变成扁平化的字符串。这样可以方便传输和进行压缩等。使用BFS或者DFS的方法在面试中都是正确的,但如果能够比较出BFS的方法可以更有效的节省空间的话,可以得到额外的加分。

以上就是python二叉树的序列化该怎么理解,小编相信有部分知识点可能是我们日常工作会见到或用到的。希望你能通过这篇文章学到更多知识。更多详情敬请关注创新互联行业资讯频道。


文章名称:python二叉树的序列化该怎么理解
网页网址:http://scyanting.com/article/gpjgdp.html