j*****y
发帖数: 1071 | 1 如果里面存的是 string的话， 用什么做 sentinel 呢？
比如
a
/ \
# b
/
c
以前一个帖子好像说到，每个 character 用三个digit的string来表示
那么上面的就变成了
097
/ \
035 098
/
099
这种情况下还是可以用 # 做 sentinel
是这么做的吗？还是说有更好的方法？
|
x*******6
发帖数: 262 | 2 分别serialize preorder和inorder的data，取出时再重新构建tree可行否？ |
j*****y
发帖数: 1071 | 3 这个可以 ,多谢 :)
不过这个需要 tree里面没有相同的 key.
【在 x*******6 的大作中提到】
: 分别serialize preorder和inorder的data，取出时再重新构建tree可行否？
|
w****x
发帖数: 2483 | 4
做这个format:
bool isSentinel|| string
【在 j*****y 的大作中提到】
: 如果里面存的是 string的话， 用什么做 sentinel 呢？
: 比如
: a
: / \
: # b
: /
: c
: 以前一个帖子好像说到，每个 character 用三个digit的string来表示
: 那么上面的就变成了
: 097
|
j*****y
发帖数: 1071 | 5 你说的是 sentinel 放在前面？
能 detail点吗, 多谢 :)
【在 w****x 的大作中提到】
:
: 做这个format:
: bool isSentinel|| string
|
G*******l
发帖数: 19 | 6 话说我被面过这道题。。。
就是对于每个节点，存以下的数据：
null or not null:
if not null:
store the length of data for this node
actually data
这样任意字符串都可以存储不用担心某一个作为sentinel的节点被放在了字符串里的情
况 |
l**b
发帖数: 457 | 7 这个有重复的data的话怎么处理？
【在 x*******6 的大作中提到】
: 分别serialize preorder和inorder的data，取出时再重新构建tree可行否？
|
j*****y
发帖数: 1071 | 8 那这里的 sentinel是 null pointer ?
serialize以后要写到文件里面，这里有 struct, 那么文件里面存的是写 binary 的东
西吧？ 不是 text的 ？
【在 G*******l 的大作中提到】
: 话说我被面过这道题。。。
: 就是对于每个节点，存以下的数据：
: null or not null:
: if not null:
: store the length of data for this node
: actually data
: 这样任意字符串都可以存储不用担心某一个作为sentinel的节点被放在了字符串里的情
: 况
|
w****x
发帖数: 2483 | 9
一个节点如果不是null就写内存为 false,"this is an example"'\0'
如果是null就写内存为 true,'\0'
unserialize的时候先读第一个sizeof(bool), 就可以知道是不是sentinel(null指针)
了
【在 j*****y 的大作中提到】
: 那这里的 sentinel是 null pointer ?
: serialize以后要写到文件里面，这里有 struct, 那么文件里面存的是写 binary 的东
: 西吧？ 不是 text的 ？
|
e****e
发帖数: 418 | 10 What if the node has string value , how to
differentiate it from 一个节点如果不是null就写内存为 false,"this is an
example"? Thanks.
【在 w****x 的大作中提到】
:
: 一个节点如果不是null就写内存为 false,"this is an example"'\0'
: 如果是null就写内存为 true,'\0'
: unserialize的时候先读第一个sizeof(bool), 就可以知道是不是sentinel(null指针)
: 了
|
|
|
w****x
发帖数: 2483 | 11
真是..
bool isNull = (bool)*p;
p += sizeof(bool);
String strContent(p);
p += str.length()+1;
这样一个节点就解析出来了
【在 e****e 的大作中提到】
: What if the node has string value , how to
: differentiate it from 一个节点如果不是null就写内存为 false,"this is an
: example"? Thanks.
|
e****e
发帖数: 418 | 12 我的问题是：如何区分节点本身存的是true值,还是这个节点是个null,然后serialize
为true. 因为这两种情况下，写下的都值是true.
【在 w****x 的大作中提到】
:
: 真是..
: bool isNull = (bool)*p;
: p += sizeof(bool);
: String strContent(p);
: p += str.length()+1;
: 这样一个节点就解析出来了
|
e****e
发帖数: 418 | 13 It's a good approach.
【在 G*******l 的大作中提到】
: 话说我被面过这道题。。。
: 就是对于每个节点，存以下的数据：
: null or not null:
: if not null:
: store the length of data for this node
: actually data
: 这样任意字符串都可以存储不用担心某一个作为sentinel的节点被放在了字符串里的情
: 况
|
w****x
发帖数: 2483 | 14
serialize
只有null为true,非null为false
【在 e****e 的大作中提到】
: 我的问题是：如何区分节点本身存的是true值,还是这个节点是个null,然后serialize
: 为true. 因为这两种情况下，写下的都值是true.
|
e****e
发帖数: 418 | 15 如果有个节点它的string value是"true", how to differentiate this node with a
null node?
i.e
"true"
One way of interpretation is there is a root node with value "true".
Another is there is no tree at all, because the root points to null.
【在 w****x 的大作中提到】
:
: serialize
: 只有null为true,非null为false
|
w****x
发帖数: 2483 | 16
a
我晕，你看我unserialize的代码就知道了，写个serialize的：
if (NULL == pNode)
*p = true;
else
{
*p = false;
p += sizeof(bool);
从p开始写入字符串
}
【在 e****e 的大作中提到】
: 如果有个节点它的string value是"true", how to differentiate this node with a
: null node?
: i.e
: "true"
: One way of interpretation is there is a root node with value "true".
: Another is there is no tree at all, because the root points to null.
|
e****e
发帖数: 418 | 17 I see. Thank you, yhx.
Node Serialized Value
null true
true falsetrue
false falsefalse
"" false
"AB" falseAB
【在 w****x 的大作中提到】
:
: a
: 我晕，你看我unserialize的代码就知道了，写个serialize的：
: if (NULL == pNode)
: *p = true;
: else
: {
: *p = false;
: p += sizeof(bool);
: 从p开始写入字符串
|
j*****y
发帖数: 1071 | 18 刚才想了一下，明白了
比如
abc
/ \
ac cd
/
#
可以这么存储
3 abc 2 ac 1 # # 2 cd # #
长度和 data 之间有一个 空格， 即使 data 的前面有空格也是可以handle
比如 " abc"
【在 G*******l 的大作中提到】
: 话说我被面过这道题。。。
: 就是对于每个节点，存以下的数据：
: null or not null:
: if not null:
: store the length of data for this node
: actually data
: 这样任意字符串都可以存储不用担心某一个作为sentinel的节点被放在了字符串里的情
: 况
|
G*******l
发帖数: 19 | 19 不一定要是null pointer，可以用0代表这个节点的data长度是0表示null（如果没有0
长度的value的话），如果有可以用-1，或者随便一个负数应该都行的。。
存到文件不一定是binary，举个例子：
abc
/ \
null abcdef
那在文件里就是 3abc06abcdef
【在 j*****y 的大作中提到】
: 那这里的 sentinel是 null pointer ?
: serialize以后要写到文件里面，这里有 struct, 那么文件里面存的是写 binary 的东
: 西吧？ 不是 text的 ？
|
j*****y
发帖数: 1071 | 20 不用空格的话，会有一点小小的麻烦，比如长度是 123
0
【在 G*******l 的大作中提到】
: 不一定要是null pointer，可以用0代表这个节点的data长度是0表示null（如果没有0
: 长度的value的话），如果有可以用-1，或者随便一个负数应该都行的。。
: 存到文件不一定是binary，举个例子：
: abc
: / \
: null abcdef
: 那在文件里就是 3abc06abcdef
|
G*******l
发帖数: 19 | 21 yes~ 差不多就是这个想法，当然有没有空格都没关系，因为我们知道要读入的长度，
这个长度之后长度内的字符都属于这个node的value ：）
【在 j*****y 的大作中提到】
: 刚才想了一下，明白了
: 比如
: abc
: / \
: ac cd
: /
: #
: 可以这么存储
: 3 abc 2 ac 1 # # 2 cd # #
: 长度和 data 之间有一个 空格， 即使 data 的前面有空格也是可以handle
|
e****e
发帖数: 418 | 22 Pseudo code, da niu look look, Thanks.
Serialize:
if (node == null)
write("null")
else
wirte(str.length + str); |
