现在的位置: 首页 > 综合 > 正文

百度Intern面试题之二叉树的网络传输及恢复–二叉树的文件存储和读取

2012年09月06日 ⁄ 综合 ⁄ 共 3213字 ⁄ 字号 评论关闭

  这不是我的面试题,是一个同学在百度的面试题。

  要求将一颗二叉树通过网络传输到给另一个客户端,并且在该客户端恢复为原始二叉树。

 

  这道题目可以理解为如何将一颗二叉树存储到文件中,并且读取后正确恢复。

 

  以这样的一棵二叉树为例:

 

 

  我想到了三种解决方法:

  1. 二叉树补全法,将这课二叉树补全,变成一颗完全二叉树,再使用数组进行存储,写入文件中。这样做需要在节点中增加一个属性,标记是否为补全的节点。

  这种方法不太合理,因为使用了补全操作,对于一颗很不规则的二叉树,将会占用非常大的存储空间,并且修改了二叉树的属性。

  2. 游标实现法。定义一个新的结构体,其中的left和right指针修改为结构体在数组中的位置。

  就像下面这样,数组的第一个位置表示NULL位置,剩余的存放节点,left和right分别指向左右子节点所在数组索引。这是前序遍历递归调用得到的数组。

 

  3. 二叉树位置描述实现。同2类似,不过这里没有左右子节点的指针,而是用一个整形来描述当前节点在一颗完全二叉树中的位置。显然,在上图这样的二叉树中,节点1的位置为1,节点2的位置为2,节点3的位置为3,节点4的位置为4,节点5的位置为6,依次类推。。。

 

  依次,可以定义一个新的结构体描述节点信息,用于存储。

   

  于是可以前序遍历递归调用,得到这样的一个数组。

 

 

 

  恢复的时候,查找左右子节点,只需要查找p值2倍于自身以及2倍+1于自身的节点。

 

  下面就是对与方法3的C++源码。

 

 

 

 

 

 

  这是该程序的输出结果:

 

  

抱歉!评论已关闭.