一个树，不一定是2叉树，让设计一个数据结构来serialize和 deserialize - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

一个树，不一定是2叉树，让设计一个数据结构来serialize和 deserialize

一个树，不一定是2叉树，让设计一个数据结构来serialize和 deserialize# JobHunting - 待字闺中

e*s2013-01-21 08:01

1 楼

再CAIWU的面经上看到的，有没有大牛给个IDEA？

j*y2013-01-21 08:01

2 楼

感觉还是可以用 pre-order travers 一个 left child, right siblin 的结构吧.

【在 e***s 的大作中提到】

: 再CAIWU的面经上看到的，有没有大牛给个IDEA？

w*x2013-01-21 08:01

3 楼

/*
Serialize/DeSerialize a tree
*/
struct NODE
{
int nVal;
vector vec;
NODE(int n) : nVal(n) {}
};
void _inner_serial(NODE* pNode, char*& p)
{
if (NULL == pNode)
return;
*p++ = pNode->vec.size();
*p++ = pNode->nVal;
for (vector::iterator it = pNode->vec.begin();
it != pNode->vec.end(); it++)
_inner_serial(*it, p);
}
const char* Serialize(NODE* pRoot, char mem[])
{
if (NULL == mem || NULL == pRoot)
return NULL;
char* p = mem;
_inner_serial(pRoot, p);
return mem;
}
NODE* _inner_deserial(const char*& p)
{
int n = *p++;
NODE* pRet = new NODE(*p++);
for (int i = 0; i < n; i++)
pRet->vec.push_back(_inner_deserial(p));
return pRet;
}
NODE* DeSerialize(const char mem[])
{
if (NULL == mem)
return NULL;
const char* p = mem;
return _inner_deserial(p);
}

j*y2013-01-21 08:01

4 楼

thanks.

【在 w****x 的大作中提到】

: /*
: Serialize/DeSerialize a tree
: */
: struct NODE
: {
: int nVal;
: vector vec;
: NODE(int n) : nVal(n) {}
: };
: void _inner_serial(NODE* pNode, char*& p)

j*y2013-01-21 08:01

5 楼

这种情况下 child是没有顺序的，是吧？
如何把 serialized的 array写到一个file去，然后从file读回来重建树呢？
多谢 :)

【在 w****x 的大作中提到】

: /*
: Serialize/DeSerialize a tree
: */
: struct NODE
: {
: int nVal;
: vector vec;
: NODE(int n) : nVal(n) {}
: };
: void _inner_serial(NODE* pNode, char*& p)

c*w2013-01-21 08:01

6 楼

我一直对你的头像很感兴趣，这个女的是谁？

【在 w****x 的大作中提到】

: /*
: Serialize/DeSerialize a tree
: */
: struct NODE
: {
: int nVal;
: vector vec;
: NODE(int n) : nVal(n) {}
: };
: void _inner_serial(NODE* pNode, char*& p)

e*s2013-01-21 08:01

7 楼

非常感谢！！

【在 w****x 的大作中提到】

: /*
: Serialize/DeSerialize a tree
: */
: struct NODE
: {
: int nVal;
: vector vec;
: NODE(int n) : nVal(n) {}
: };
: void _inner_serial(NODE* pNode, char*& p)

e*s2013-01-21 08:01

8 楼

再CAIWU的面经上看到的，有没有大牛给个IDEA？

j*y2013-01-21 08:01

9 楼

感觉还是可以用 pre-order travers 一个 left child, right siblin 的结构吧.

【在 e***s 的大作中提到】

: 再CAIWU的面经上看到的，有没有大牛给个IDEA？

w*x2013-01-21 08:01

10 楼

j*y2013-01-21 08:01

11 楼

thanks.

【在 w****x 的大作中提到】

: /*
: Serialize/DeSerialize a tree
: */
: struct NODE
: {
: int nVal;
: vector vec;
: NODE(int n) : nVal(n) {}
: };
: void _inner_serial(NODE* pNode, char*& p)

j*y2013-01-21 08:01

12 楼

这种情况下 child是没有顺序的，是吧？
如何把 serialized的 array写到一个file去，然后从file读回来重建树呢？
多谢 :)

【在 w****x 的大作中提到】

: /*
: Serialize/DeSerialize a tree
: */
: struct NODE
: {
: int nVal;
: vector vec;
: NODE(int n) : nVal(n) {}
: };
: void _inner_serial(NODE* pNode, char*& p)

c*w2013-01-21 08:01

13 楼

我一直对你的头像很感兴趣，这个女的是谁？

【在 w****x 的大作中提到】

: /*
: Serialize/DeSerialize a tree
: */
: struct NODE
: {
: int nVal;
: vector vec;
: NODE(int n) : nVal(n) {}
: };
: void _inner_serial(NODE* pNode, char*& p)

e*s2013-01-21 08:01

14 楼

非常感谢！！

【在 w****x 的大作中提到】

: /*
: Serialize/DeSerialize a tree
: */
: struct NODE
: {
: int nVal;
: vector vec;
: NODE(int n) : nVal(n) {}
: };
: void _inner_serial(NODE* pNode, char*& p)

u*o2013-01-21 08:01

15 楼

是赵雅芝啊，好像是她在京华烟云里姚木兰的扮相。。

【在 c***w 的大作中提到】

:
: 我一直对你的头像很感兴趣，这个女的是谁？

S*t2013-01-21 08:01

16 楼

you can encode the structure of the generic tree with 2n bits, and
reconstruct the structure from the 2n bits

【在 e***s 的大作中提到】

: 再CAIWU的面经上看到的，有没有大牛给个IDEA？

m*k2013-01-21 08:01

17 楼

抛一砖：
How about in-order traversal?
String serialize(Node root){
if(root == null){
return "()";
}
else{
return "(" + serialize( root.left) + root.val + serialize( root.
right) + ")" ;
}
}
ex:
1
/ \
2 3
/ \
4 5
will return
( ( (()4()) 2 ( ()5()) ) 1 ( ()3 () ) )
deserialize:
easy with stack,